120
правок
Изменения
→Использование сжатого суффиксного дерева: добавлен алгоритм построения суффиксного массива и lcp
* Наибольшую общую подстроку двух строк
* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix) исходной строки
===Построение суффиксного массива и массива lcp из суффиксного дерева===
Пусть к строке дописан специальный символ для сохранения инварианта.
Рассмотрим лексикографический по ребрам порядок обхода сжатого суффиксного дерева.
Пусть два суффикса имеют общее начало, но различаются в <tex>i</tex>-ом символе.
Первым будет рассмотрено поддерево по ребру с меньшим символом, значит и лист, соответствующий этому суффиксу, будет посещен первым.
Тогда суффиксный массив строится из суффиксного дерева [[Обход в глубину, цвета вершин| обходом в глубину]] в указанном порядке.
Пусть длина строки <tex>length</tex>, глубина листа в символах <tex>depth</tex>, тогда номер суффикса <tex>i = length - depth</tex>.
Для заполнения массива <tex>lcp</tex> нам понадобится вершина <tex>minNode</tex>, которая будет означать вершину с минимальной глубиной, в которую мы поднимались при переходе между суффиксами. Поскольку мы точно поднимались туда, но не поднимались выше, это будет [[Сведение задачи LCA к задаче RMQ| наименьший общий предок]] этих узлов. Из этого следует, что у рассматриваемых суффиксов совпадает ровно <tex>lcp = minNode.depth</tex> символов.
<code>
'''int''' length
'''int[]''' suf
'''int[]''' lcp
'''int''' curPos = 0
Node minNode = root
<font color=green>//Для заполнения нужно вызвать dfs(root) </font>
dfs(Node n)
'''if''' children.size == 0
suf[curPos] = length - n.depth
lcp[curPos] = minNode.depth
curPos++
minNode = n
'''else'''
'''foreach''' Node c '''from''' n.children
'''if''' n.depth < minNode.depth
minNode = n
dfs(c)
</code>
Асимптотика алгоритма совпадает с асимптотикой обхода в глубину и составляет <tex>O(n)</tex>.
==Источники==
