Префикс-функция Алгоритм Кнута–Морриса–Пратта

Определение

Дана строка $S$ длины $N$ , префикс-функция $\pi(i)$ в позиции $i$ $(0 \leq i < N)$ — это длина наибольшего собственного префикса подстроки

Внешние задачи

Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:

CODEFORCESPassword

Rating: 1700

CODEFORCESPrefix Function Queries

Rating: 2200

CODEFORCESAnthem of Berland

Rating: 2300

S[0 \ldots i]

который также является суффиксом этой подстроки.

Здесь собственный префикс означает префикс, который не равен всей строке целиком.

Поэтому всегда имеем:

\pi_0 = 0

и для $0 < i < N$ :

\pi_i = \max \left\{ k : 0 \le k \le i,\; S[0 \ldots k-1] = S[i-k+1 \ldots i] \right\}

Например, для строки

S = \text{"aabcaa"}

префикс-функция равна

\pi = [0, 1, 0, 0, 1, 2]

Алгоритм

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

Первое наблюдение

Для каждого $0 < i < N$ имеем:

\pi_i \le \pi_{i-1} + 1

Это означает, что значение префикса может увеличиться не более чем на единицу при переходе к следующей позиции.

Второе наблюдение

Предположим, мы уже знаем $\pi_{i-1}$ .

Пусть

j = \pi_{i-1}

Тогда мы пытаемся продлить текущее совпадение, сравнивая:

S[i]
S[j]

Если они равны, то мы можем увеличить длину префикса на единицу:

\pi_i = j + 1

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

Следующий кандидат:

j = \pi_{j-1}

Мы повторяем этот процесс, пока:

не найдём совпадение, или
$j$ не станет равным нулю.

Если совпадение не найдено, то:

\pi_i = 0

Реализация

vector<int> prefix_function(string s) {
    vector<int> p(s.size());

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

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

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

        p[i] = j;
    }

    return p;
}