275
правок
Изменения
м
→Линейный алгоритм
|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>
}}