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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм решения)
(Алгоритм решения)
Строка 3: Строка 3:
  
 
==Алгоритм решения==
 
==Алгоритм решения==
Построим строку <tex>P = T\#S</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>S</tex> и <tex>T</tex>. Посчитаем на ней [[Префикс-функция|префикс-функцию]] <tex>\pi()</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>, это и будет ответ.
  
 
==Псевдокод==
 
==Псевдокод==

Версия 19:20, 15 апреля 2012

Постановка задачи

Дана цепочка [math]S[/math] и образец [math]T[/math]. Требуется найти все позиции, начиная с которых [math]T[/math] входит в [math]S[/math].

Алгоритм решения

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

Псевдокод

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

 <вычисление префикс-функции для цепочки P>
 count = 0
 for (i = 0 .. (s - 1)) {
   if ([math]\pi[/math](t + i + 1) == t) {
     answer[count] = i + 1 - t
     count = count + 1
   }
 }

Время работы

[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]).