Русская Википедия:Префикс-функция
Пре́фикс-фу́нкция от строки <math>S</math> и позиции <math>i</math> в ней — длина <math>k</math> наибольшего собственного (не равного всей подстроке) префикса подстроки <math>S[1..i]</math>, который одновременно является суффиксом этой подстроки.
То есть в начале подстроки <math>S[1..i]</math> длины <math>i</math> нужно найти такой префикс максимальной длины <math>k < i</math>, который был бы суффиксом данной подстроки <math>\left(S[1..k] = S\left[(i-k+1)..i\right]\right)</math>.
Обозначается <math>\pi(S,i)</math>; где <math>S \in \Sigma^+</math> — строка; <math>1 \leqslant i \leqslant \left| S \right|</math> — длина подстроки в S. Считают, что <math>\pi(S,1)=0</math>.
Часто префикс-функцию определяют в векторной форме:
Пре́фикс-фу́нкция от строки <math>S \in \Sigma^+</math> есть вектор <math>\pi(S) \in \mathbb{Z}^{\left| S \right|}</math>, каждый <math>i</math>-ый элемент которого равен <math>\pi(S,i)</math>.
Например, для строки <math>\texttt{abcdabscabcdabia}</math> префикс-функция будет такой: <math>\pi(\texttt{abcdabscabcdabia})=[0,0,0,0,1,2,0,0,1,2,3,4,5,6,0,1]</math>.
Эта функция используется, например, в алгоритме Кнута — Морриса — Пратта.
Алгоритм вычисления
- Поиск повторяющихся слогов не в слове, а в тексте, строке начиная с первых символов? Символы строк нумеруются с 1.
Пусть <math>\pi (S,i)=k</math>. Попробуем вычислить префикс-функцию для <math>i+1</math>.
Если <math>S[i+1]=S[k+1]</math>, то, естественно, <math>\pi(S,i+1)=k+1</math>. Если нет — пробуем меньшие суффиксы. Перебирать все суффиксы линейным поиском нет необходимости. Можно воспользоваться уже посчитанными значениями префикс-функции. Можно заметить, что <math>S[1 \ldots \pi(S,k)]</math> также будет суффиксом строки <math>S[1 \ldots i]</math>, так как <math>k</math> — длина максимального префикса-суффикса в данной точке. Для любого <math>j \in (k,i)</math> строка <math>S[1 \ldots j]</math> суффиксом не будет. Таким образом, получается алгоритм:
- При <math>S[i+1]=S[k+1]</math> — положить <math>\pi(S,i+1)=k+1</math>.
- Иначе при <math>k=0</math> — положить <math>\pi(S,i+1)=0</math>.
- Иначе — установить <math>k:=\pi(S,k)</math>и перейти к пункту 1.
Для строки 'abcdabcabcdabcdab' вычисление будет таким:
1 S[1]='a', k=π=0; 2 S[2]='b'!=S[k+1] => k=π=0; 3 S[3]='c'!=S[1] => k=π=0; 4 S[4]='d'!=S[1] => k=π=0; 5 S[5]='a'==S[1] => k=π=1; 6 S[6]='b'==S[2] => k=π=2; 7 S[7]='c'==S[3] => k=π=3; 8 S[8]='a'!=S[4] => k:=π(S, 3)=0, S[8]==S[1] => k=π=1; 9 S[9]='b'==S[2] => k=π=2; 10 S[10]='c'==S[3] => k=π=3; 11 S[11]='d'==S[4] => k=π=4; 12 S[12]='a'==S[5] => k=π=5; 13 S[13]='b'==S[6] => k=π=6; 14 S[14]='c'==S[7] => k=π=7; 15 S[15]='d'!=S[8] => k:=π(S, 7)=3, S[15]==S[4] => k=π=4; 16 S[16]='a'==S[5] => k=π=5; 17 S[17]='b'==S[6] => k=π=6;
И результат таков: [0,0,0,0,1,2,3,1,2,3,4,5,6,7,4,5,6].
Скорость работы
Несмотря на то, что пункт 3 представляет собой внутренний цикл, время вычисления префикс-функции оценивается как <math>O(|S|)</math>. Докажем это.
Все <math>i</math> делятся на:
- Увеличивающие <math>k</math> на единицу. Цикл проходит одну итерацию.
- Не изменяющие нулевое <math>k</math>. Цикл также проходит одну итерацию. Случаев 1 и 2 в сумме не более <math>\left|S\right|-1</math> штук.
- Не изменяющие или уменьшающие положительное <math>k</math>. Поскольку внутри цикла значение <math>k</math> может только уменьшаться, а увеличение <math>k</math> возможно лишь на единицу, то суммарно значение <math>k</math> не может уменьшиться более, чем <math>\left|S\right|-2</math> раза, что и ограничивает количество срабатываний внутреннего цикла.
Итого алгоритм требует не более <math>2\left|S\right|</math> итераций, что доказывает порядок скорости <math>O(\left|S\right|)</math>. «Худшим» для алгоритма является случай обработки строки вида 'aa…ab'.
Пример реализации на Python
def prefix(s):
p = [0] * len(s)
for i in range(1, len(s)):
k = p[i - 1]
while k > 0 and s[k] != s[i]:
k = p[k - 1]
if s[k] == s[i]:
k += 1
p[i] = k
return p
Ссылки
- Поиск подстроки и смежные вопросы Шаблон:Wayback — статья на хабрe
Шаблон:СтрокиШаблон:Нет ссылок
