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

Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер — собственный префикс, одновременно являющийся собственным суффиксом.

vector<int> prefixFunction(const string &s) {
    vector<int> p(s.size());
    for (int i = 1; i < s.size(); i++) {
        int border = p[i - 1];
        while (border > 0 && s[i] != s[border])
            border = p[border - 1];
        p[i] = border + (s[i] == s[border]);
    }
    return p;
}

Применения:

• Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == |s|.
• Определение минимального периода m строки s за O(N). m = |s| - p[|s| - 1].
• Определение числа различных подстрок n строки s за O(N^2). Пусть известен ответ n' для s' = s[1 .. |s| - 1], за O(N) вычислим ответ для s. Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию s. Пусть m = max(p[i]). В s' уже встречались все префиксы s длиной ≤ m, поэтому n = n' + (|s| - m).

Ссылки

Теория:

• e-maxx.ru — Префикс-функция. Алгоритм Кнута-Морриса-Пратта
• neerc.ifmo.ru/wiki — Префикс-функция
• neerc.ifmo.ru/wiki — Алгоритм Кнута-Морриса-Пратта
• Brestprog — Префикс-функция. Алгоритм Кнута-Морриса-Пратта
• Algorithmica — Префикс- и Z-функция
• Brilliant.org — Knuth-Morris-Pratt Algorithm

Код:

• github.com/indy256/codelibrary/blob/master/cpp/strings/kmp.cpp
• github.com/ADJA/algos/blob/master/Strings/PrefixFunction.cpp

Задачи:

• informatics.mccme.ru — Курс «Алгоритмы на строках» — часть 1
• Задачи: Префикс-функция