3622
правки
Изменения
м
Таким образом Следовательно, на каждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до <tex>k,\ k \leqslant i</tex>, а не от <tex>1</tex> до <tex>i</tex>. Действительно, если суффикс <tex>s[j..i-2]</tex> был продлён до суффикса <tex>s[j..i-1]</tex> на прошлой фазе по правилу 1, то он и дальше будет продлеваться по правилу 1 (о чём говорит [[#l1 | лемма]]). Если он был продлён по правилу 2, то была создана новая листовая вершина, значит, на текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j..i]</tex> по листовой вершине. Поэтому после применения правила 3 на суффиксе <tex>s[k..i]</tex> текущую фазу можно завершить, а следующую начать сразу с <tex>j^* = k</tex>.
→Линейный алгоритм
Так как лист навсегда останется листом, можно задать метку ребра ведущего в этот лист как <tex>s[j..x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.
=== Итоговая оценка времени работы ===
