c # — уникальные подстроки, использующие суффиксное дерево
Для данной строки S длины n—
-
Оптимальный алгоритм поиска всех уникальных подстрок
Sне может быть меньше чемO(n^2), Итак, лучший алгоритм даст нам сложностьO(n^2), Согласно тому, что я прочитал, это может быть реализовано путем создания дерева суффиксов дляS,
Дерево суффиксов для S может быть создано в O(n) время. Теперь мой вопрос-
Как мы можем использовать дерево суффиксов для S, чтобы получить все уникальные подстроки S в O(n^2)?
Решение
Попробуйте прочитать о массивах суффиксов: http://en.wikipedia.org/wiki/Suffix_array
Этот метод быстрее, чем дерево суффиксов для получения подстрок в строке.
Другие решения
Это может быть сделано оптимально с помощью попыток. Добавьте строки в три и переберите их от корня к узлу. Каждый путь от корня к узлу будет обозначать суффиксы строки. Возьмите все префиксы этих суффиксов. Это уникальные подстроки.