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

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

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

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

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

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

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

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

Алгоритм вычисления

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

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

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

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

Все $i$ делятся на:

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

Итого алгоритм требует не более $2\left|S\right|$ итераций, что доказывает порядок скорости $O(\left|S\right|)$. «Худшим» для алгоритма является случай обработки строки вида '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

Ссылки

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