52
правки
Изменения
Нет описания правки
Рассмотрим две леммы, позволяющие ускорить алгоритм Укконена до <tex>O(n^2)</tex>.
<br />
===Лемма 1. Стал листом {{---}} листом и останешься ===
{{Лемма
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>j</tex> (для суффикса, начинающегося в позиции <tex>j</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
<br />
|proof=
Это верно потому, что у алгоритма нет механизма продолжения листового ребра дальше текущего листа. Если есть лист с суффиксом <tex>j</tex>, правило продолжения 1 будет применяться для продолжения <tex>j</tex> на всех последующих фазах.
|statement=
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>о</tex>, оно будет реализовываться во всех дальнейших продолжениях(от <tex>j + 1</tex> по <tex>i + 1</tex>) до конца фазы.
<br />
|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>
}}
<br />Когда используется правило 3, никакой работы делать не нужно, так как требуемый суффикс уже в дереве есть. Более того, новая суффиксная связь должна добавляться к дереву только после продолжения, в котором участвует правило 2. Поэтому можно заканчивать каждую фазу <tex>i + 1</tex> после первого же использования правила прохождения 3. Если это случится в продолжении j, то уже не требуется явно находить концы строк <tex>S[k..i]</tex> с <tex>k > j</tex>. ==Алгоритм Укконена за квадратичное время== Рассмотрим правила продолжения суффиксов. При использовании правила 1 по лемме 1 в последующих фазах будет выполняться правило 1. Поэтому скажем, что мы создаём лист не только для рассмотренной части строки, а для всей всей строки до конца. <br />При использовании правила 2 появится новый лист, который далее будет продлеваться по правилу 1. <br />При использовании правила 3 по лемме 2 никакой работы делать не нужно, поскольку суффикс в дереве уже есть. Следовательно, можно остановиться и не добавлять следующие суффиксы.
Таким образом, операция insert позволяет суффиксы не только для подстрок <tex>S[j..i]</tex>, но и сразу для всего суффикса <tex>S[j..n]</tex>.
=== Псевдокод ===
Приведенный алгоритм можно записать с помощью псевдокода:
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do'''
insert(<tex>s_{i..n}</tex>)
Поскольку операция insert по-прежнему занимает линейное время, очевидно, что время работы данного алгоритма составляет <tex>O(n^2)</tex>.
==Суффиксные ссылки==
