52
правки
Изменения
добавлено две леммы
==Оптимизация алгоритма Укконена==
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
===Лемма 1. Стал листом {{---}} листом и останешься ===
{{Лемма
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>j</tex> (для суффикса, начинающегося в позиции <tex>j</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>j</tex>, правило продолжения 1 будет применяться для продолжения <tex>j</tex> на всех последующих фазах.
}}
===Лемма 2. правило 3 заканчивает дело ===
{{Лемма
|statement=
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>о</tex>, оно будет реализовываться во всех дальнейших продолжениях(от <tex>j + 1</tex> по <tex>i + 1</tex>) до конца фазы.
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>S[j..i]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>, и точно так же продолжается путь, помеченный <tex>S[j + 1..i]</tex>, поэтому правило 3 применяется в продолжениях <tex>j + 1, j + 2, ..., i + 1</tex>
}}
Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Более того, новая суффиксная связь должна добавляться к дереву только после продолжения, в котором участвует правило 2. Поэтому можно заканчивать каждую фазу <tex>i + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк <tex>S[k..i]</tex> с <tex>k > j</tex>.
==Суффиксные ссылки==
{{Определение
