Алгоритм Кнута-Морриса-Пратта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Описание алгоритма)
Строка 4: Строка 4:
 
Дана цепочка <tex>T</tex> и образец <tex>P</tex>. Требуется найти все позиции, начиная с которых <tex>P</tex> входит в <tex>T</tex>.
 
Дана цепочка <tex>T</tex> и образец <tex>P</tex>. Требуется найти все позиции, начиная с которых <tex>P</tex> входит в <tex>T</tex>.
 
<br>
 
<br>
Построим строку <tex>S = P\#T</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>P</tex> и <tex>T</tex>. Посчитаем на ней [[Префикс-функция|префикс-функцию]] <tex>\pi()</tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: \pi(i) \le |T|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |P|</tex> и <tex>\pi(i) = |P|</tex> подстроки длины <tex>P</tex>, начинающиеся с позиций <tex>0</tex> и <tex>i - |P| + 1</tex>, совпадают. Соберем все такие позиции <tex>i - |P| + 1</tex> строки <tex>S</tex>, вычтем из каждой позиции <tex>|P| + 1</tex>, это и будет ответ.
+
Построим строку <tex>S = P\#T</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>P</tex> и <tex>T</tex>. Посчитаем на ней [[Префикс-функция|префикс-функцию]] <tex>\pi()</tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: \pi(i) \le |P|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |P|</tex> и <tex>\pi(i) = |P|</tex> подстроки длины <tex>P</tex>, начинающиеся с позиций <tex>0</tex> и <tex>i - |P| + 1</tex>, совпадают. Соберем все такие позиции <tex>i - |P| + 1</tex> строки <tex>S</tex>, вычтем из каждой позиции <tex>|P| + 1</tex>, это и будет ответ.
 
<br>
 
<br>
 
[[Файл:kmp_pict.png|600px]]
 
[[Файл:kmp_pict.png|600px]]

Версия 12:53, 21 июня 2012

Алгоритм Кнута — Морриса — Пратта — алгоритм поиска подстроки в строке.

Описание алгоритма

Дана цепочка [math]T[/math] и образец [math]P[/math]. Требуется найти все позиции, начиная с которых [math]P[/math] входит в [math]T[/math].
Построим строку [math]S = P\#T[/math], где [math]\#[/math] — любой символ, не входящий в алфавит [math]P[/math] и [math]T[/math]. Посчитаем на ней префикс-функцию [math]\pi()[/math]. Благодаря разделительному символу [math]\#[/math], выполняется [math]\forall i: \pi(i) \le |P|[/math]. Заметим, что по определению префикс-функции при [math]i \gt |P|[/math] и [math]\pi(i) = |P|[/math] подстроки длины [math]P[/math], начинающиеся с позиций [math]0[/math] и [math]i - |P| + 1[/math], совпадают. Соберем все такие позиции [math]i - |P| + 1[/math] строки [math]S[/math], вычтем из каждой позиции [math]|P| + 1[/math], это и будет ответ.
Kmp pict.png

Псевдокод

Пусть [math]t = |T|[/math], [math]s = |S|[/math].

count = 0
for (i = 0 .. (s - 1))
   if ([math]\pi[/math](t + i + 1) == t)
      answer[count++] = i + 1 - t

Время работы

[math]O(s + t)[/math] (время подсчета [math]\pi()[/math] для [math]P) + O(s)[/math] (последующий [math]for[/math]) [math]= O(s + t)[/math].

Оценка по памяти

Предложенная реализация имеет оценку по памяти [math]O(S+T)[/math]. Оценки [math]O(S)[/math] можно добиться за счет незапоминания значений [math]\pi()[/math] для позиций в [math]P[/math], меньших [math]t + 1[/math] (до начала цепочки [math]S[/math]).

Источники

Knuth–Morris–Pratt algorithm
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн — Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.1036. — ISBN 978-5-8459-0857-5.