SuffixTree Суффиксное дерево — бор, содержащий все суффиксы некоторой строки. Позволяет выяснять, входит ли строка w в исходную строку, за время O(w). Время построения суффиксного дерева O(n); Линейность построения: Проверка на вхождение подстроки:
