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

Дана строка \(s[0 \ldots n-1]\). Требуется вычислить для неё префикс-функцию, т.е. массив чисел \(\pi[0 \ldots n-1]\), где \(\pi[i]\) определяется следующим образом: это такая наибольшая длина наибольшего собственного суффикса подстроки \(s[0 \ldots i]\), совпадающего с её префиксом (собственный суффикс — значит не совпадающий со всей строкой). В частности, значение \(\pi[0]\) полагается равным нулю.

Например, для строки «abcabcd» префикс-функция равна: [0, 0, 0, 1, 2, 3, 0], что означает:

строка	совпадает с суффиксом		префикс длины
a	❌		0
ab	❌		0
abc	❌		0
abca	✔		1
abcab	✔		2
abcabc	✔		3
abcabcd	❌		0

❌ Тривиальный алгоритм \(O(n ^ 3)\)

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=0; i<n; ++i)
        for (int k=0; k<=i; ++k)
            if (s.substr(0,k) == s.substr(i-k+1,k))
                pi[i] = k;
    return pi;
}

✔ Итоговый аггоритм \(O(n)\)

• Считать значения префикс-функции \(\pi[i]\) будем по очереди: от \(i=1\) к \(i=n-1\) (значение \(\pi[0]\) просто присвоим равным нулю).
• Для подсчёта текущего значения \(\pi[i]\) мы заводим переменную \(j\), обозначающую длину текущего рассматриваемого образца. Изначально \(j = \pi[i-1]\).
• Тестируем образец длины \(j\), для чего сравниваем символы \(s[j]\) и \(s[i]\). Если они совпадают — то полагаем \(\pi[i] = j+1\) и переходим к следующему индексу \(i+1\). Если же символы отличаются, то уменьшаем длину j, полагая её равной \(\pi[j-1]\), и повторяем этот шаг алгоритма с начала.
• Если мы дошли до длины \(j=0\) и так и не нашли совпадения, то останавливаем процесс перебора образцов и полагаем \(\pi[i] = 0\) и переходим к следующему индексу \(i+1\).

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

---

Применения

Поиск подстроки в строке. Алгоритм Кнута-Морриса-Пратта \(O(n + m)\)

\(O(n + m)\) времени и \(O(n)\) памяти.

Эта задача является классическим применением префикс-функции (и, собственно, она и была открыта в связи с этим).

Дан текст \(t\) и строка \(s\), требуется найти и вывести позиции всех вхождений строки \(s\) в текст \(t\).

Обозначим для удобства через \(n\) длину строки \(s\), а через \(m\) — длину текста \(t\).

1. Образуем строку \(s + \# + t\), где символ \(\#\) — это разделитель, который не должен нигде более встречаться.
2. Посчитаем для этой строки префикс-функцию.
3. 1. Теперь рассмотрим её значения, кроме первых \(n+1\) (которые, как видно, относятся к строке \(s\) и разделителю).
   2. Но в нашем случае это \(\pi[i]\) — фактически длина наибольшего блока совпадения со строкой \(s\) и оканчивающегося в позиции \(i\). Больше, чем \(n\), эта длина быть не может — за счёт разделителя. А вот равенство \(\pi[i] = n\) (там, где оно достигается), означает, что в позиции \(i\) оканчивается искомое вхождение строки s (только не надо забывать, что все позиции отсчитываются в склеенной строке \(s+\#+t\)).

Таким образом, если в какой-то позиции \(i\) оказалось \(\pi[i] = n\), то в позиции \(i - (n + 1) - n + 1 = i - 2 n\) строки \(t\) начинается очередное вхождение строки \(s\) в строку \(t\).

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> pf(string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s, t;
    cin >> s >> t;
    auto pfv = pf(s + "#" + t);
    vector<ll> ans;
    for (int i = s.size() + 1; i < pfv.size(); i++) {
        if (pfv[i] == s.size()) {
            ans.push_back(i - 2 * s.size() + 1);
        }
    }
    cout << ans.size() << "\n";
    for (auto i : ans) {
        cout << i << " ";
    }
    return 0;
}