Изменения

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

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

26 байт добавлено, 15:40, 9 мая 2012
Описание алгоритма
==Описание алгоритма==
[[Файл:kmp_pict.png]]
Дана цепочка <tex>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, начиная с которых <tex>T</tex> входит в <tex>S</tex>.<br>
Построим строку <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>, это и будет ответ.
Анонимный участник

Навигация