Изменения

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

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

Нет изменений в размере, 21:26, 28 апреля 2015
м
Линейный алгоритм
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продления 3 применяется в продолжении <tex>ij</tex>, оно будет реализовываться во всех дальнейших продолжениях (от <tex>ij+1</tex> по <tex>ji+1</tex>) до конца фазы.
<br>
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>s[ij..ji]</tex> в текущем дереве, должен продолжаться символом <tex>ji+1</tex>, и точно так же продолжается путь, помеченный <tex>s[ij+1..ji]</tex>, поэтому правило 3 применяется в продолжениях <tex>ij+1, ij+2, ..., ji+1</tex>
}}
275
правок

Навигация