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

Префикс-функция строки 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;
}

Применения:

• Поиск подстроки pattern в тексте text за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка pattern#text, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == pattern.size().
• Определение минимального периода period строки s за O(N). period = s.size() - p.back().
• Определение числа различных подстрок строки s за O(N^2). Пусть известен ответ prevRes для строки prevSuffix = s.substr(i + 1), за O(N) вычислим ответ res для строки suffix = s.substr(i). Новые подстроки — те, которые начинаются в начале строки и не встречаются далее. Вычисляем префикс-функцию для suffix, пусть maxP = *max_element(p.begin(), p.end()). В prevSuffix уже встречались все префиксы длиной ≤ maxP, поэтому res = prevRes + (suffix.size() - maxP).

Ссылки

Теория:

• 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
• Задачи: Префикс-функция