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

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

for (int i = 1; i < n; i++) {
    int border = p[i - 1];
    while (border > 0 && s[i] != s[border])
        border = p[border - 1];
    p[i] = border + (s[i] == s[border]);
}

Применения:

• Поиск подстроки 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.neocities.org — Префикс-функция. Алгоритм Кнута-Морриса-Пратта
• Brilliant.org — Knuth-Morris-Pratt Algorithm

Код:

• CodeLibrary — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function
• Algos — Prefix function

Задачи:

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