Изменения
Нет описания правки
|}
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
pi = 0
'''return''' pi
===Время работы===
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.
==Оптимизация==
Внесем несколько важных замечаний:
*<tex>\pi(i + 1)</tex> превосходит <tex>pi(i)</tex> не больше чем на <tex>1</tex>. Действительно, если <tex>\pi(i+1) > \pi(i) + 1</tex>, тогда <tex>\pi(i+1) - 1 > \pi(i)</tex>, получили противоречие.
*Избавимся от явных сравнений строк. Пусть мы вычислили <tex>\pi(i)</tex> и <tex>s[\pi(i) + 1] = s[i + 1]</tex>, тогда очевидно <tex>\pi(i+1) = \pi(i) + 1</tex>. Если же условие <tex>s[\pi(i) + 1] = s[i + 1]</tex> ложно, то хотелось бы найти наибольшую длину <tex> j</tex>, для которой верно <tex>\pi(i+1) = j + 1</tex>. Когда мы найдем такое <tex>j</tex> нам достаточно будет сравнить <tex>s[j + 1]</tex> и <tex>s[i + 1]</tex>, при их равенстве <tex>\pi(i+1) = j + 1</tex> будет верно. Будем искать наше <tex>j</tex> пока оно больше нуля, при равенстве нулю <tex>\pi(i+1) = 0</tex>. Общая схема алгоритма у нас есть, теперь нужно только научиться искать <tex>j</tex>.
*Для поиска <tex>j</tex> нам стоит использовать равенство <tex>j = \pi(j)</tex>, когда <tex>s[j+1] = s[i+1]</tex> ложно, взяв за исходное <tex> j = \pi(i)</tex>.
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
pi = 0
'''for''' i = 2 '''to''' n
j = pi[i - 1]
'''while''' j > 0 && s[i] != s[j + 1]
j = pi[j]
'''if''' s[i] == s[j + 1]
j++
pi[i] = j
'''return''' pi
===Время работы===
В итоге мы получили алгоритм выполняющий <tex>O(n)</tex> итераций за <tex>O(1)</tex>, что дает нам итоговое <tex>O(n)</tex>.
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
