3622
правки
Изменения
м
→Линейный алгоритм
|about= Правило 3 заканчивает дело
|statement=
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</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>
