Изменения
Нет описания правки
{{Определение|definition = '''Префикс-функция''' ''(prefix-function)'' от строки(обозначается <tex>\pi(s,i)</tex>) - длина наибольшего префикса строки <tex>S[1..i]</tex>, который не совпадает с этой строкой и одновременно является ее суффиксом}} Префикс-функция строки <tex>s</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>1</tex>.
==АлгоритмНаивный алгоритм==
Наивный алгоритм вычисляет префикс функцию непосредственно по определению, сравнивая префиксы и суффиксы строк.
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.
==ОптимизацияЭффективный алгоритм==
Вносятся несколько важных замечаний:
*Следует заметить, что <tex>\pi(i) \le \pi(i-1) + 1</tex>. По определению префикс функции верно, что <tex>s[1..\pi(i)] = s[i - \pi(i) + 1..i]</tex>. В частности, получается, что <tex>s[1..\pi(i) - 1] = s[i - \pi(i) + 1..i - 1]</tex>. Поскольку <tex>\pi</tex> это наибольший префикс равный суффиксу, то <tex>\pi(i - 1) \ge \pi(i) - 1</tex>.
== Литература ==
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.ISBN 978-5-8459-0857-5
[[Категория:Алгоритмы и структуры данных]][[Категория:Поиск подстроки в строке]]
