Изменения

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

'''int'''[] prefixFunction('''string''' s): <tex>\pi</tex> p[1] = 0 '''for''' i = 2 '''to''' n k = <tex>\pi</tex>p[i-1] '''while''' k > 0 '''and''' s[i] != s[k + 1] k = <tex>\pi</tex>p[k] '''if''' s[i] == s[k + 1] k++ <tex>\pi</tex> p[i] = k '''return''' <tex>\pi</tex>p