108
правок
Изменения
Нет описания правки
<tex>\pi</tex>(0) <- 0
for (i <- 1..n - 1) {
while (k > 0 && s[i] != <tex>\ne</tex> s[k])
k <- <tex>\pi</tex>(k - 1)
if (s[i] = s[k])
Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:
# <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется
# <tex>k = 0 \& s[i] != \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется# <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>|S|n</tex>Таким образом, общее время работы - <tex>O(|S|n)</tex>.
