36
правок
Изменения
Нет описания правки
Вносятся несколько важных замечаний:
*Заметим, что <tex>\pi[i + 1] \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>.
[[Файл:PrfxPrfxx.jpgpng]]
===Псевдокод===
'''Prefix_function''' (<tex>s</tex>)
== Источники информации ==
*[http://e-maxx.ru/algo/prefix_function Префикс-функция — e-maxx]
*[http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Префикс-функция — Википедия]
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296 ISBN 978-5-8459-0857-5
== См. также ==
*[[Z-функция|Z-функция]]
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
