3622
правки
Изменения
м
→Линейный алгоритм
В любой фазе, если правило продления 3 применяется в продолжении суффикса, начинающего в позиции <tex>j</tex>, оно же и будет применяться во всех дальнейших продолжениях (от <tex>j+1</tex> по <tex>i</tex>) до конца фазы.
|proof=
При использовании правила продолжения 3 путь, помеченный <tex>s[j..i-1]</tex> в текущем дереве, должен продолжаться символом <tex>i+1</tex>, и точно так же продолжается путь, помеченный <tex>s[j+1..i-1]</tex>, поэтому правило 3 применяется в продолжениях <tex>j+1, \ j+2, ...\ldots, i+1</tex>.
}}
