276
правок
Изменения
м
Нет описания правки
== Теоретическое обоснование ==
Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.
Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..\ldots n]</tex> и <tex>s[i..\ldots n]</tex> среди всех <tex>j < i</tex>.
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
{{Лемма
|id=lemma_head
|statement=Пусть <tex>head_i = s[i..\ldots i+h]</tex>, тогда <tex>s[i+1..\ldots i+h]</tex> {{---}} префикс <tex>head_{i+1}</tex>.
|proof=
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..\ldots n]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..\ldots n]</tex>. Тогда <tex>s[j+1..\ldots n]</tex> будет иметь с <tex>s[i+1..\ldots n]</tex> общий префикс длины <tex>h-1</tex>. Поскольку любой общий префикс будет по определению также являться и префиксом <tex>head_{i+1}</tex>, получаем искомое утверждение.
}}
|statement=Инвариант алгоритма сохраняется
|proof=Инвариант мог бы нарушиться только в случае, если бы не существовало вершины в суффиксной ссылке для <tex>head_{i-1}</tex>, но мы продолжили бы сканирование по ребру дальше и получили две вершины <tex>head_{i-1}.suf,\ head_i</tex> с неопределенными суффиксными ссылками.
Покажем, что это невозможно. Рассмотрим, что значит, что <tex>head_{i-1}.suf</tex> остановилась посередине ребра. Это означает, что все суффиксы <tex>s[j..\ldots n],\ j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..\ldots n]</tex>. Тогда и <tex>s[i..\ldots n]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
}}
В вершинах дерева <tex>Node</tex> будем хранить следующую информацию:
* <tex>parent</tex> {{---}} предок
* <tex>start, end</tex> {{---}} метка подстроки <tex> s[start..\ldots end] </tex> на ребре от предка
* <tex>length = end - start + 1</tex> {{---}} длина ребра до предка
* <tex>depth</tex> {{---}} глубина вершины в символах
