заполнение в обобщенном дереве суффиксов и ресурс реализации

Question

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

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

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

Спасибо!

Answer 1

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

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