Префикс-функция: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «Префикс-функция строки s — массив длин максимальных бордеров всех префиксов s. Бордер &…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 11: | Строка 11: | ||
* Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == |s|. | * Поиск подстроки s в тексте t за O(N) (алгоритм Кнута-Морриса-Пратта). Составляется строка s#t, вычисляется её префикс-функция. Вхождения завершаются в позициях, для которых p[i] == |s|. | ||
* Определение минимального m | * Определение минимального периода 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). | * Определение числа различных подстрок 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). | ||
Версия от 14:22, 22 июля 2015
Префикс-функция строки 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 — Алгоритм Кнута-Морриса-Пратта
Код:
- CodeLibrary — Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function
- Algos — Prefix function
Задачи: