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

Материал из Олимпиадное программирование в УлГТУ
Перейти к: навигация, поиск

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

Ссылки

Теория:

Код:

Задачи: