36
правок
Изменения
Нет описания правки
{{Определение
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} длина наибольшего массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордерабордеров]] для каждой позиции этой строки}}
Здесь и далее считаем, что символы в строках нумеруются с <tex>1</tex>.
===Псевдокод===
'''Prefix_functionint''' [] Prefix_function(<tex>string s</tex>)
fill(<tex>\pi</tex>, 0)
'''for''' i = 1 '''to''' n
'''for''' k = 1 '''to''' i
'''if''' s[1..k] == s[i - k + 1..i])
<tex>\pi</tex>[i] = k
'''return''' <tex>\pi</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>.
[[Файл:PrfxxUntitled-1.pngjpg|800px]]
===Псевдокод===
'''Prefix_functionint''' [] Prefix_function(<tex>string s</tex>)
<tex>\pi</tex>[1] = 0
'''for''' i = 2 '''to''' n
k = <tex>\pi</tex>[i-1]
'''while''' k > 0 && '''and''' s[i] != s[k + 1]
k = <tex>\pi</tex>[k]
'''if''' s[i] == s[k + 1]
** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.
** <tex>p[n] > 0</tex>. По свойствам префикс-функции <tex> s'[p[n]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины <tex> p[n] </tex> продолжаются одним символом, значит, надо на текущую позицию строки <tex> s </tex> поставить символ <tex> s[p[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что <tex> p[n - 1] \geqslant p[n] - 1 </tex>. По предположению индукцию значение <tex> q[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.
== См. также ==
*[[Z-функция|Z-функция]]
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
== Источники информации ==
*[http://e-maxx.ru/algo/prefix_function Префикс-функция — e-maxx]
*[http[wikipedia://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
