Изменения

|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки(обозначается <tex>\pi(s,i)</tex>) {{--- }} длина наибольшего префикса [[Период_и_бордер,_их_связь#Определения|бордера]] этой строки }}Здесь и далее считаем, что символы в строках нумеруются с <tex>S[1..i]</tex>, который не совпадает с этой строкой и одновременно является ее суффиксом}}.

ПрефиксОпределим префикс-функция функцию от строки <tex>s</tex> {{---}} функция в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 1..i - 1} \{ 0, k : </tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>.

Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.Обозначим длину строки за <tex>n</tex>

'''for''' i = 1 '''to''' s.length n

*Заметим, что <tex>\pi[i + 1] \le leqslant \pi[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>\pi[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>\pi[i + 1] - 1</tex>, следовательно неравенство <tex>\pi[i + 1] > \pi[i] + 1</tex> неверно.*Избавимся от явных сравнений строк. **Пусть мы вычислили <tex>\pi[i]</tex>, тогда, если <tex>s[i + 1] = s[\pi[i]]</tex>, то <tex>\pi[i + 1] = \pi[i] + 1</tex>. **Если окажется, что <tex>s[i + 1] \ne s[\pi[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Для Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = \pi(i) - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>\pi(i - 1)</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>\pi(k)</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>\pi(i)=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>\pi(i)=0</tex>.

k = 0 '''for''' i = 2 '''to''' s.lengthn

** <tex>p[n] > 0</tex>. По свойствам префикс-функции <tex> s'[p[n]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины <tex> p[n] </tex> продолжаются одним символом, значит, надо на текущую позицию строки <tex> s </tex> поставить символ <tex> s[p[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что <tex> p[n - 1] \geqslant p[n] - 1 </tex>. По предположению индукцию значение <tex> q[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по препдположению предположению индукции.

== Литература Источники информации ==