Префикс-функция

Пре́фикс-фу́нкция от строки ${\displaystyle S}$ и позиции ${\displaystyle i}$ в ней — длина ${\displaystyle k}$ наибольшего собственного (не равного всей подстроке) префикса подстроки ${\displaystyle S[1..i]}$, который одновременно является суффиксом этой подстроки.

То есть в начале подстроки ${\displaystyle S[1..i]}$ длины ${\displaystyle i}$ нужно найти такой префикс максимальной длины ${\displaystyle k<i}$, который был бы суффиксом данной подстроки ${\displaystyle \left(S[1..k]=S\left[(i-k+1)..i\right]\right)}$.

Обозначается ${\displaystyle \pi (S,i)}$; где ${\displaystyle S\in \Sigma ^{+}}$ — строка; ${\displaystyle 1\leqslant i\leqslant \left|S\right|}$ — длина подстроки в S. Считают, что ${\displaystyle \pi (S,1)=0}$.

Часто префикс-функцию определяют в векторной форме:

Пре́фикс-фу́нкция от строки ${\displaystyle S\in \Sigma ^{+}}$ есть вектор ${\displaystyle \pi (S)\in \mathbb {Z} ^{\left|S\right|}}$, каждый ${\displaystyle i}$-ый элемент которого равен ${\displaystyle \pi (S,i)}$.

Например, для строки ${\displaystyle {\texttt {abcdabscabcdabia}}}$ префикс-функция будет такой: ${\displaystyle \pi ({\texttt {abcdabscabcdabia}})=[0,0,0,0,1,2,0,0,1,2,3,4,5,6,0,1]}$.

Эта функция используется, например, в алгоритме Кнута — Морриса — Пратта.

Поиск повторяющихся слогов не в слове, а в тексте, строке начиная с первых символов? Символы строк нумеруются с 1.

Пусть ${\displaystyle \pi (S,i)=k}$. Попробуем вычислить префикс-функцию для ${\displaystyle i+1}$.

Если ${\displaystyle S[i+1]=S[k+1]}$, то, естественно, ${\displaystyle \pi (S,i+1)=k+1}$. Если нет — пробуем меньшие суффиксы. Перебирать все суффиксы линейным поиском нет необходимости. Можно воспользоваться уже посчитанными значениями префикс-функции. Можно заметить, что ${\displaystyle S[1\ldots \pi (S,k)]}$ также будет суффиксом строки ${\displaystyle S[1\ldots i]}$, так как ${\displaystyle k}$ — длина максимального префикса-суффикса в данной точке. Для любого ${\displaystyle j\in (k,i)}$ строка ${\displaystyle S[1\ldots j]}$ суффиксом не будет. Таким образом, получается алгоритм:

1. При ${\displaystyle S[i+1]=S[k+1]}$ — положить ${\displaystyle \pi (S,i+1)=k+1}$.
2. Иначе при ${\displaystyle k=0}$ — положить ${\displaystyle \pi (S,i+1)=0}$.
3. Иначе — установить ${\displaystyle k:=\pi (S,k)}$и перейти к пункту 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 представляет собой внутренний цикл, время вычисления префикс-функции оценивается как ${\displaystyle O(|S|)}$. Докажем это.

Все ${\displaystyle i}$ делятся на:

1. Увеличивающие ${\displaystyle k}$ на единицу. Цикл проходит одну итерацию.
2. Не изменяющие нулевое ${\displaystyle k}$. Цикл также проходит одну итерацию. Случаев 1 и 2 в сумме не более ${\displaystyle \left|S\right|-1}$ штук.
3. Не изменяющие или уменьшающие положительное ${\displaystyle k}$. Поскольку внутри цикла значение ${\displaystyle k}$ может только уменьшаться, а увеличение ${\displaystyle k}$ возможно лишь на единицу, то суммарно значение ${\displaystyle k}$ не может уменьшиться более, чем ${\displaystyle \left|S\right|-2}$ раза, что и ограничивает количество срабатываний внутреннего цикла.

Итого алгоритм требует не более ${\displaystyle 2\left|S\right|}$ итераций, что доказывает порядок скорости ${\displaystyle O(\left|S\right|)}$. «Худшим» для алгоритма является случай обработки строки вида 'aa…ab'.

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

• Поиск подстроки и смежные вопросы Архивная копия от 15 января 2016 на Wayback Machine — статья на хабрe

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (1 ноября 2013)