поиск всех индексов ключевого слова в дереве суффиксов

Question

Это визуальный график дерева суффиксов для входного текста "Миссисипи".В этом примере я ищу ключевое слово "si".Я думаю, что понимаю, как получить первый индекс "si"

• , начиная с корневого узла # 1
• , первый край - "s", поэтому мы переходим к узлу # 2
• Второй край узла № 2 - это «i», поэтому мы получаем узел № 7, и этот узел сохраняет индекс в тексте.

Но теперь для второго появления"си" ... мне просто продолжить поиск в поддереве № 7 для следующего вхождения?Для меня это не имеет смысла.

Или дерево должно быть собрано по-другому, чтобы поддерживать несколько индексов?

Answer 1

Проблема в том, что у вас недостаточно информации в дереве.

Путь, ведущий к узлу, помеченному 6, указывает оба (обычно все ) вхождения в исходном слове. То, что вы хотите сделать, это когда вы обрабатываете префиксы, как описано в алгоритме, вы хотите хранить индексы в узлах. Вообще говоря, алгоритм не будет хранить такую ​​информацию, но это легко изменить.

Каждый раз, когда вы получаете доступ к узлу, напишите добавление позиции в исходной строке в список позиций совпадения.

1. (пустое дерево)
2. (путь "si", узел "6" (дополнительная информация в узле "6": 4-5), остаток дерева)
3. и т.д.
4. (путь "si", узел "6" (дополнительная информация в узле "6": 4-5, 7-8), остаток дерева)
5. и т.д. * * тысяча двадцать-одна