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

Префикс-функция от строки равна массиву , где обозначает длину максимального префикса строки , совпадающего с её суффиксом. Тривиальные случаи (префикс равен суффиксу и равен всей строке) не учитываются.

Префикс-функция строки "abacaba"

На изображении обозначены равные подстроки, длина которых равна значению префикс-функции в данной позиции. Префикс-функция от всей строки “abacaba” равна . так как строки “a” и “ab” являются тривиальными, и поэтому не учитываются.

В определённых случаях префикс и суффикс могут перекрываться:

Префикс-функция строки "abababa"

Наивный алгоритм нахождения префикс-функции имеет сложность , что неприемлемо для большинства случаев. Существует гораздо более эффективный алгоритм, работающий за .

Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (КМП) позволяет находить префикс-функцию от строки за линейное время, и имеет достаточно лаконичную реализацию, по длине не превышающую наивный алгоритм.

Для начала заметим важное свойство: . То есть префикс-функция от следующего элемента не более чем на превосходит префикс-функцию от текущего. Случай легко изобразить:

Префикс-функция строки "abacaba"

То есть верно следующее утверждение (в 0-индексации):

Этот случай достаточно тривиален. Но что если ? Хотелось бы найти такую длину , что , но при этом . Если , то . На самом деле, длина уже была найдена в процессе нахождения префикс-функции. А именно, . Графически это выглядит так:

Префикс-функция строки "aabaaxxxxaabaab"

Если же длина также не подходит (), просто ещё раз уменьшим её по такой же формуле: . Таким образом будем пытаться продолжить префикс длины , пока не станет равно . В таком случае просто сравним с , и в зависимости от результата присвоим или .

Реализация

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> prefix_function(const string& s) {
    vector<int> pi(s.length(), 0);

    for (int i = 1; i < s.length(); i++) {
        int j = pi[i - 1];  //текущая длина префикса, который мы хотим продолжить
                            //гарантируется, что s[0..j-1] = s[i-j..i-1].

        while (j > 0 && s[i] != s[j]) {     //пока мы не можем продолжить текущий префикс
            j = pi[j - 1];  //уменьшаем его длину до следующей возможной
        }

        //Теперь j - максимальная длина префикса, который мы можем продолжить,
        //или 0, если такового не существует.

        if (s[i] == s[j]) {
            pi[i] = j + 1;
        } else {    //такое может произойти только при j = 0
            pi[i] = j;
        }
    }

    return pi;
}

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

Префикс-функция - необычайно мощная структура, с помощью которой решается значительная часть задач про строки. Классической задачей на префикс-функцию является задача на поиск подстроки в строке (алгоритм КМП был изначально разработан именно для решения этой задачи). Разберём её в качестве примера.

Пусть нам нужно найти подстроку в строке . С помощью префикс-функции это делается тривиально: найдём префикс-функцию от строки (решётка обозначает символ, гарантированно не встречающийся ни в одной из строк). Если эта префикс-функция содержит значения равные длине , значит входит в . А именно, пусть . Значит - последний символ вхождения в .

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;

vector<int> prefix_function(const string& s) {
    vector<int> pi(s.length(), 0);

    for (int i = 1; i < s.length(); i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            pi[i] = j + 1;
        } else {
            pi[i] = j;
        }
    }

    return pi;
}

int main() {
    string s, t;
    cin >> s >> t;

    vector<int> pi = prefix_function(t + '#' + s);

    int t_len = t.length();

    for (int i = 0; i < s.length(); i++) {
        if (pi[t_len + 1 + i] == t_len) {
            cout << "s[" << i - t_len + 1 << ".." << i << "] = t" << endl;
        }
    }
}