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

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

То есть, в начале подстроки длины нужно найти такой префикс максимальной длины , который был бы суффиксом данной подстроки .

Обозначается ; где  — строка;  — длина подстроки в S. Считают, что .

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

Пре́фикс-фу́нкция от строки есть вектор , каждый -ый элемент которого равен .

Например, для строки префикс-функция будет такой: .

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

Алгоритм вычисления
Символы строк нумеруются с 1.

Пусть . Попробуем вычислить префикс-функцию для .

Если , то, естественно, . Если нет — пробуем меньшие суффиксы. Перебирать все суффиксы линейным поиском нет необходимости. Можно воспользоваться уже посчитанными значениями префикс-функции. Можно заметить, что также будет суффиксом строки , так как  — длина префикса-суффикса в данной точке. Для любого строка суффиксом не будет. Таким образом, получается алгоритм:

  1. При  — положить .
  2. Иначе при  — положить .
  3. Иначе — установить и перейти к пункту 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 представляет собой внутренний цикл, время вычисления префикс-функции оценивается как . Докажем это.

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

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

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

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.