Изменения

==Определение==Префикс-функцией цепочки функция строки <tex>Ss</tex> называется {{---}} функция <tex>\pi(k) = max \{ j | j \leq k,</tex> и <tex>s[0..j - 1] = s[k - j + 1..k] \}</tex>.

==Алгоритм вычисления==<tex> n Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.===Пример== |S|</tex>*'''Псевдокод''' k = 0 Рассмотрим строку abcabcd, для которой префикс-функции равно <tex>\pi</tex>([0,0) = ,0 for (i = ,1 .. (n - 1)) { while (k > ,2,3,0 && s[i] <tex>\ne</tex> s[k]). k {| class= <tex>\pi</tex>(k - 1)"wikitable" if (s[i] == s[k])! Шаг || Строка || Значение функции k = k + 1|- | <tex>\pi1</tex>(i) = k|| a || 0 }|-*'''Корректность работы'''[[Файл:Prefix1.jpg|center]]Как видно из рисунка, при совпадении символов <tex>S[k]2</tex> и || ab || 0|-| <tex>S[i]3</tex> длина наибольшего общего префикса увеличивается на 1. В случае, когда символы || abc || 0|-| <tex>S[k]4</tex> и <tex>S[i]</tex> не совпадают, <tex>\pi(k-|| abca || 1)</tex> - следующая по максимальности длина потенциального наибольшего общего префикса *'''Время работы''' Сперва отметим очевидный из определения факт: <tex>\pi(k + 1) |- \pi(k) \leq 1</tex> для любого <tex>k</tex>. В самом деле, в противном случае <tex>\pi(k)</tex> не максимально. Теперь рассмотрим произвольную итерацию внешнего цикла | <tex>for5</tex>. Возможно одно из трёх:|| abcab || 2 1) <tex>s[i] = s[k]</tex>. Тогда значение <tex>k</tex> увеличивается на 1, цикл <tex>while</tex> не итерируется|- 2) | <tex>k = 06</tex> <tex>\&</tex> <tex>s[i] \ne s[k]</tex>. Тогда значение <tex>k</tex> не изменяется, цикл <tex>while</tex> не итерируется || abcabc || 3) <tex>while</tex> итерируется хотя бы раз. При каждой итерации <tex>while</tex> значение <tex>k</tex> может, очевидно, лишь уменьшаться, при этом, в силу отмеченного выше очевидного наблюдения, общее число итераций <tex>while</tex> для всех итераций <tex>for</tex> не превышает <tex>n</tex> Таким образом, общее время работы |- | <tex>O(n)7</tex>.|| abcabcd || 0|}