120
правок
Изменения
м
Нет описания правки
== Теоретическое обоснование ==
Рассмотрим строку <tex>s</tex> длины <tex>n</tex>, которая заканчивается специальным символом, не встречающимся больше в строке.Заметим, что если два суффикса имеют <tex>lcp</tex> (''largest common prefix'') общих символов, то в построенном суффиксном дереве они будут иметь [[Сведение задачи LCA к задаче RMQ| наименьшего общего предка]] на этой глубине. Будем рассматривать суффиксы в порядке убывания длины, тогда имеет смысл узнавать наибольшее <tex>lcp</tex> с новым суффиксом среди всех суффиксов, добавленных раньше. Обозначим как <tex>head_i</tex> {{---}} максимальный префикс <tex>s[j..\left\vert s \right\vertn]</tex> и <tex>s[i..\left\vert s \right\vertn]</tex> среди всех <tex>j < i</tex>.
Пусть мы знаем <tex>head_i</tex> и место в дереве, которое ему соответствует. Если позиция находится на ребре, разрежем его, а потом добавим новую вершину. Считать <tex>head_i</tex> по определению было бы очень затруднительно, но существует способ значительно сократить вычисления.
|proof=
* При <tex>h=0</tex>, очевидно, пустая строка является префиксом любой другой.
* Пусть <tex>h > 0</tex>. Из определения <tex>head_i</tex> существует суффикс <tex>s[j..\left\vert s \right\vertn]</tex>, имеющий <tex>h</tex> общих символов с <tex>s[i..\left\vert s \right\vertn]</tex>. Тогда <tex>s[j+1..\left\vert s \right\vertn]</tex> будет иметь с <tex>s[i+1..\left\vert s \right\vertn]</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..\left\vert s \right\vertn], j < i - 1</tex>, которые дошли до этого места, имеют совпадающие следующие символы, по определению <tex>head_{i-1}</tex> отличающиеся от символа суффикса <tex>s[i - 1..\left\vert s \right\vertn]</tex>. Тогда и <tex>s[i..\left\vert s \right\vertn]</tex> должен отличаться в этом символе, значит <tex>head_i = head_{i-1}.suf</tex>.
}}
