Изменения

Перейти к: навигация, поиск

Алгоритм Кнута-Морриса-Пратта

14 байт убрано, 15:12, 9 мая 2012
Нет описания правки
==Постановка задачи==Дана цепочка <tex>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, начиная с которых <tex>T</tex> входит Алгоритм Кнута — Морриса — Пратта — алгоритм [[Наивный алгоритм поиска подстроки в <tex>S</tex>строке|поиска подстроки в строке]].
==Алгоритм решенияОписание алгоритма==
Построим строку <tex>P = T\#S</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>S</tex> и <tex>T</tex>. Посчитаем на ней [[Префикс-функция|префикс-функцию]] <tex>\pi()</tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: \pi(i) \le |T|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |T|</tex> и <tex>\pi(i) = |T|</tex> подстроки длины <tex>T</tex>, начинающиеся с позиций <tex>0</tex> и <tex>i - |T| + 1</tex>, совпадают. Соберем все такие позиции <tex>i - |T| + 1</tex> строки <tex>P</tex>, вычтем из каждой позиции <tex>|T| + 1</tex>, это и будет ответ.
Анонимный участник

Навигация