108
правок
Изменения
Нет описания правки
<tex>\pi</tex>(i) = k
}
*'''Корректность работы'''
[[Файл:Prefix1.jpg|center]]
Как видно из рисунка, при совпадении символов <tex>S[k]</tex> и <tex>S[i]</tex> длина наибольшего общего префикса увеличивается на 1. В случае, когда символы <tex>S[k]</tex> и <tex>S[i]</tex> не совпадают, <tex>pi(k-1)</tex> - следующая по максимальности длина потенциального наибольшего общего префикса
*'''Время работы'''
Сперва отметим очевидный из определения факт: <tex>\pi(k + 1) - \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально. Теперь рассмотрим произвольную итерацию внешнего цикла <tex>for</tex>. Возможно одно из трёх:# 1) <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется# 2) <tex>k = 0</tex> <tex>\&</tex> <tex>s[i] \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется# 3) <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>n</tex> Таким образом, общее время работы - <tex>O(n)</tex>.
