Изменения

Важно помнить, что алгоритм скорее теоретический, чем практический, а основная ценность его заключается в том, что размер алфавита может быть произвольным.

Основная идея алгоритма заключается в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы сходной строки на пары и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.

В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.

* [[Сжатое суффиксное дерево]]

* [[Алгоритм Укконена]]

* [[Суффиксный массив]]

*[http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]

*[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y Computing Patterns in Strings]

*[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree Chris Parjaszewski's implementation]