313
правок
Изменения
→Использование сжатого суффиксного дерева
==Использование сжатого суффиксного дерева==
Суффиксное дерево позволяет за линейное время найти:
# Количество различных подстрок данной строки.# Наибольшую общую подстроку двух строк.# [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (''longest common prefix'') исходной строки.# Строку максимальной длины, ветвящуюся влево и вправо за <tex>ST + O(n)</tex>.
===Построение суффиксного массива и массива lcp из суффиксного дерева===
