==Оптимизация==
В начале приводится псевдокод Внесем несколько важных замечаний:*<tex>\pi(i)</tex> превосходит <tex>\pi(i-1)</tex> не больше, чем на <tex>1</tex>. Действительно, если <tex>\pi(i) > \pi(i-1) + 1</tex>, тогда <tex>\pi(i) - 1 > \pi(i-1)</tex>, значит в <tex>\pi(i-1)</tex> не максимально возможное значение, получили противоречие.*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i-1)</tex> и <tex>s[\pi(i-1) + 1] = s[i]</tex>, тогда очевидно <tex>\pi(i) = \pi(i-1) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> k</tex>, для которой верно <tex>\pi(i) = k + 1</tex>. Когда мы найдем такое <tex>k</tex> нам достаточно будет сравнить <tex>s[k + 1]</tex> и <tex>s[i]</tex>, при их равенстве <tex>\pi(i) = k + 1</tex> будет верно. Будем искать наше <tex>k</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i) = 1</tex>, если <tex>s[i] = s[1]</tex>, иначе нулю. Общая схема алгоритмау нас есть, а затем его обоснованиетеперь нужно только научиться искать <tex>k</tex>.*Для поиска <tex>k</tex> нам стоит использовать равенство <tex>k = \pi(k)</tex>, когда <tex>s[k+1] = s[i]</tex> ложно, взяв за исходное <tex> k = \pi(i -1)</tex>, это позволит выбирать <tex>k</tex> по убыванию вплоть до нуля, так как очевидно, что <tex>\pi(x) \geq \pi(\pi(x))</tex> для любых <tex>x</tex>.Последние два пункта наглядно проиллюстрированы на рисунке: [[Файл:Prefix2.jpg]]
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</tex>
===Корректность работы===
Начнем с рассмотрения леммы, в которой показано, что путем итерации префиксной функции <tex>\pi</tex> можно перечислить все префиксы длины <tex> k</tex> <tex>s_k</tex>, которые являются истинными суффиксами заданного префикса длины <tex>i</tex> <tex>s_i</tex>. Введем обозначение <tex> \pi ' [i] = (\pi[i], \pi^{2}[i], ..., \pi^{t}[i])</tex>, где величина <tex>\pi^{j}[i]</tex> обозначает <tex>j</tex>-ю итерацию префиксной функции, т.е. <tex>\pi^{0}[i] = i</tex> и при <tex> i \ge 1</tex> <tex>\pi^{j}[i] = \pi[\pi^{j-1}[i]]</tex>. Кроме того, понятно, что последовательность <tex>\pi'[i]</tex> обрывается, когда в ней будет достигнуто значение <tex>\pi^t[i] = 0</tex>.
{{Лемма
|about=
Лемма об итерации префиксной функции
|statement=
Пусть <tex>s</tex> - строка длиной <tex>n</tex> с префиксной функцией <tex>\pi</tex>. Тогда для всех <tex> i = 0,1,..,n</tex> имеем <tex>\pi'[i] = (k : k < q</tex> и <tex>s_k s_i</tex>.
===Время работы===
