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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Замечание)
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 4 участников)
Строка 18: Строка 18:
 
     '''for''' i = 0 .. tl - 1
 
     '''for''' i = 0 .. tl - 1
 
       '''if''' p[pl + i + 1] == pl
 
       '''if''' p[pl + i + 1] == pl
           answer[count++] = i
+
           answer[count++] = i - pl
 
     '''return''' answer
 
     '''return''' answer
  
Строка 25: Строка 25:
  
 
==Оценка по памяти==
 
==Оценка по памяти==
Предложенная реализация имеет оценку по памяти <tex>O(P+T)</tex>. Оценки <tex>O(P)</tex> можно добиться за счет отказа от запоминания значений префикс-функции для позиций в <tex>S</tex>, меньших <tex>|P| + 1</tex> (то есть до начала цепочки <tex>T</tex>). Это возможно, так как значение префикс-функции не может превысить длину образца, благодаря разделительному символу <tex>\#</tex>.
+
Предложенная реализация имеет оценку по памяти <tex>O(P+T)</tex>. Оценки <tex>O(P)</tex> можно добиться за счет запоминания значений префикс-функции для позиций в <tex>S</tex>, меньших <tex>|P| + 1</tex> (то есть до начала цепочки <tex>T</tex>). Это возможно, так как значение префикс-функции не может превысить длину образца, благодаря разделительному символу <tex>\#</tex>.
  
 
==Замечание==
 
==Замечание==
Вместо [[Префикс-функция|префикс-функции]] в алгоритме Кнута-Морриса-Пратта можно использовать [[Z-функция|Z-функция]]. Оценки времени работы и памяти при этом не изменятся.
+
Вместо [[Префикс-функция|префикс-функции]] в алгоритме Кнута-Морриса-Пратта можно использовать [[Z-функция|Z-функцию]]. Оценки времени работы и памяти при этом не изменятся.
  
 
==См. также==
 
==См. также==

Текущая версия на 19:25, 4 сентября 2022

Алгоритм Кнута — Морриса — Пратта (англ. 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] p [/math]. Благодаря разделительному символу [math]\#[/math], выполняется [math]\forall i: p[i] \leqslant |P|[/math]. Заметим, что по определению префикс-функции при [math]i \gt |P|[/math] и [math]p[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]p[i]=|P|[/math], то в этой позиции начинается очередное вхождение образца в цепочку.


Kmp pict2.png

Псевдокод

int[] kmp(string P, string T):
   int pl = P.length
   int tl = T.length
   int[] answer
   int[] p = prefixFunction(P + "#" + T)
   int count = 0
   for i = 0 .. tl - 1
      if p[pl + i + 1] == pl
         answer[count++] = i - pl
   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(P+T)[/math]. Оценки [math]O(P)[/math] можно добиться за счет запоминания значений префикс-функции для позиций в [math]S[/math], меньших [math]|P| + 1[/math] (то есть до начала цепочки [math]T[/math]). Это возможно, так как значение префикс-функции не может превысить длину образца, благодаря разделительному символу [math]\#[/math].

Замечание

Вместо префикс-функции в алгоритме Кнута-Морриса-Пратта можно использовать Z-функцию. Оценки времени работы и памяти при этом не изменятся.

См. также

Источники информации