Изменения

Перейти к: навигация, поиск

Алгоритм Укконена

197 байт добавлено, 22:33, 17 марта 2015
Нет описания правки
<br />
{{Лемма|id=l1
|about= Стал листом — листом и останешься
|statement=
Если в какой-то момент работы алгоритма Укконена будет создан лист с меткой <tex>i</tex> (для суффикса, начинающегося в позиции <tex>i</tex> строки <tex>S</tex>), он останется листом во всех последовательных деревьях, созданных алгоритмом.
{{Лемма|id=l2
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продолжения 3 применяется в продолжении <tex>i</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>i + 1</tex> по <tex>j + 1</tex>) до конца фазы.
{{Лемма|id=l3
|about= Существование суффиксных ссылок
|statement=
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
Анонимный участник

Навигация