Блог

На странице Википедии говорится, что используются уникальные строки-терминаторы $0 , $1 , …, $n-1 для дерева со n строками, s1 , …, sn .

Мой вопрос: как справляться с ситуациями, в которых есть буквальный суффикс $i для строки i 1 ? Например, моя первая строка s1 example$0 . Каков разумный способ сделать это?

Кроме того, реализация дерева суффиксов, которую я нашел, в основном предназначена для одной строки, а не для обобщенной версии. Учитывая реализацию для одной строки, как можно легко ее расширить?

Спасибо!

1-й вопрос: если вы используете Unicode, вы можете использовать коды PUA (http://en.wikipedia.org/wiki/Mapping_of_Unicode_characters#Private_use_characters ), которые не назначены в вашей среде. Достаточно начинать с U E000. Если вы используете 8-разрядный ascii, используйте байтовый код, которого, как вы знаете, нет в ваших строках — 003 (конец текста) звучит уместно — вместо этого ‘$’.

2-й вопрос: просто начните сначала, только начиная с текущего дерева, а не с пустого. Уникальные терминаторы гарантируют, что вы никогда не будете пытаться разделить конечный узел.