Как подсчитать число различных подстрок строки и перечислить по одной копии каждой из этих подстрок?

Question

[Paul]

Здравствуйте. Подскажите, как можно решить обозначенную в заголовке задачу за время, линейное относительно длины подаваемой на вход строки. Предполагаю, что понадобится суффиксное дерево, но только суффиксного дерева здесь явно не достаточно.

Answer 1

[AM5800]

Количество всех подстрок строки n - равно биномиальному коэффициенту (2, n + 1). Т.е. 1/2(n+1)n.
Т.е. в худшем случае у вас n^2 подстрок. А в лучшем - n. Вот только я бы не особо радовался. Так как строки лучшего случая выглядят примерно так: "aaaaaaaaaaaaaaaa". Здесь 16 символов и 16 уникальных подстрок.
Я это все к чему - за линейное время точно ничего осмысленного не выйдет.

Количество уникальных подстрок можно посчитать так:
https://www.quora.com/Given-a-string-how-do-I-find...

К сожалению, автор не дал оценки своего алгоритма. Но, похоже, что он работает за O (n log n).
Так как суффиксный массив строится за O(n log n), а LCP отрабатывает за O(n)

Answer 2

[Paul]

Думаю, что это всё - таки можно сделать и за линейное время. Для этого потребуется суффиксное дерево для входной строки, а как это сделать можно посмотреть здесь
habrahabr.ru/post/258121