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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
           answer[count++] = i + 1 - p
 
           answer[count++] = i + 1 - p
 
     '''return''' answer
 
     '''return''' answer
 +
 +
==Множественный поиск образцов==
 +
Если мы хотим произвести множественный поиск образцов в тексте, то нам необходимо хранить значение префикс-функции символа текста для каждого образца. Перед этим нужно построить префикс-функции для всех образцов.
  
 
==Время работы==
 
==Время работы==
Префикс-функция от строки <tex>S</tex> строится за <tex>O(S) = O(P + T)</tex>. Проход цикла по строке <tex>S</tex> содержит <tex>O(T)</tex> итераций. Итого, время работы алгоритма оценивается как <tex>O(P + T)</tex>. Если мы хотим произвести множественный поиск образцов в тексте, то необходимо построить префикс-функцию для каждого из образцов в отдельности, тогда, учитывая, что длина образца обычно много меньше, чем длина текста, то общее время работы оценивается как <tex>O(mT)</tex>, где <tex>m</tex>{{---}} количество образцов.
+
Префикс-функция от строки <tex>S</tex> строится за <tex>O(S) = O(P + T)</tex>. Проход цикла по строке <tex>S</tex> содержит <tex>O(T)</tex> итераций. Итого, время работы алгоритма оценивается как <tex>O(P + T)</tex>. Для множественного поиска общее время работы оценивается как <tex>O(Q + mT)</tex>, где <tex>m</tex>{{---}} количество образцов, а <tex>Q</tex> {{---}} суммарное время построения префикс-функций для всех образцов.
  
 
==Оценка по памяти==
 
==Оценка по памяти==

Версия 21:52, 30 мая 2014

Алгоритм Кнута — Морриса — Пратта (англ. Knuth–Morris–Pratt algorithm) — алгоритм поиска подстроки в строке.

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

Дана цепочка [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) \leqslant |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], это и будет ответ. Другими словами, если в какой-то позиции [math]i[/math] выполняется условие [math]\pi(i)=|P|[/math], то в этой позиции начинается очередное вхождение образца в цепочку.
Kmp pict2.png

Псевдокод

int[] kmp(string T, string P)
   int p = P.length
   int t = T.length
   int[] answer
   count = 0
   for i = 0 .. (t - 1)
      if [math]\pi[/math](p + i + 1) == p
         answer[count++] = i + 1 - p
   return answer

Множественный поиск образцов

Если мы хотим произвести множественный поиск образцов в тексте, то нам необходимо хранить значение префикс-функции символа текста для каждого образца. Перед этим нужно построить префикс-функции для всех образцов.

Время работы

Префикс-функция от строки [math]S[/math] строится за [math]O(S) = O(P + T)[/math]. Проход цикла по строке [math]S[/math] содержит [math]O(T)[/math] итераций. Итого, время работы алгоритма оценивается как [math]O(P + T)[/math]. Для множественного поиска общее время работы оценивается как [math]O(Q + mT)[/math], где [math]m[/math]— количество образцов, а [math]Q[/math] — суммарное время построения префикс-функций для всех образцов.

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

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

См. также

Источники