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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оценка по памяти)
м (rollbackEdits.php mass rollback)
 
(не показано 75 промежуточных версий 10 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
'''Алгоритм Кнута — Морриса — Пратта''' (англ. ''Knuth–Morris–Pratt algorithm'') — алгоритм [[Наивный алгоритм поиска подстроки в строке#Постановка задачи|поиска подстроки в строке]].
Дана цепочка <tex>S</tex> и образец <tex>T</tex>. Требуется найти все позиции, начиная с которых <tex>T</tex> входит в <tex>S</tex>.
 
  
==Алгоритм решения==
+
==Описание алгоритма==
Построим строку <tex>P = T\#S</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>S</tex> и <tex>T</tex>. Посчитаем на ней префикс-функцию <tex>\pi()</tex>.
+
Дана цепочка <tex>T</tex> и образец <tex>P</tex>. Требуется найти все позиции, начиная с которых <tex>P</tex> входит в <tex>T</tex>.
 +
<br>
 +
Построим строку <tex>S = P\#T</tex>, где <tex>\#</tex> — любой символ, не входящий в алфавит <tex>P</tex> и <tex>T</tex>. Посчитаем на ней значение [[Префикс-функция|префикс-функции]] <tex> p </tex>. Благодаря разделительному символу <tex>\#</tex>, выполняется <tex>\forall i: p[i] \leqslant |P|</tex>. Заметим, что по определению [[Префикс-функция|префикс-функции]] при <tex>i > |P|</tex> и <tex>p[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>i</tex> выполняется условие <tex>p[i]=|P|</tex>, то в этой позиции начинается очередное вхождение образца в цепочку.
  
 +
 +
[[Файл:kmp_pict2.png|640px]]
  
 
==Псевдокод==
 
==Псевдокод==
Пусть <tex>t = |T|</tex>, <tex>s = |S|</tex>.
+
'''int'''[] kmp('''string''' P, '''string''' T):
  <вычисление префикс-функции для цепочки P>
+
    '''int''' pl = P.length
  count = 0
+
    '''int''' tl = T.length
  for (i = 0 .. (s - 1)) {
+
    '''int'''[] answer
    if (<tex>\pi</tex>(t + i + 1) == t) {
+
    '''int'''[] p = [[Префикс-функция#Эффективный_алгоритм|prefixFunction(P + "#" + T)]]
      answer[count] = i + 1 - t
+
    '''int''' count = 0
      count = count + 1
+
    '''for''' i = 0 .. tl - 1
     }
+
      '''if''' p[pl + i + 1] == pl
  }
+
          answer[count++] = i - pl
==Корректность работы==
+
     '''return''' answer
Отметим, что из-за символа <tex>\$</tex> значение <tex>\pi(k) \leq t</tex> для всех <tex>k</tex>.
+
 
По определению <tex>\pi()</tex>, если <tex>\pi(k) = t</tex>, то <tex>P[0..t - 1] = P[k - t + 1..k]</tex>, то есть <tex>T = S[k - t - t..k - t - 1]</tex>, то есть <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>k - t - t</tex>.
 
Пусть теперь <tex>T</tex> входит в <tex>S</tex>, начиная с позиции <tex>i</tex>. Тогда <tex>S[i..i + t - 1] = T[0..t - 1]</tex>. Иными словами, <tex>P[0..t - 1] = P[t + 1 + i..t + i + t]</tex>, что эквивалентно <tex>\pi(t + i + t) = t</tex>.
 
 
==Время работы==
 
==Время работы==
<tex>O(s + t)</tex> (время подсчета <tex>\pi()</tex> для <tex>P</tex>) + <tex>O(s)</tex> (последующий <tex>for</tex>) <tex>= O(s + t)</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(S+T)</tex>. Оценки <tex>O(S)</tex> можно добиться за счет незапоминания значений <tex>\pi()</tex> для позиций в <tex>P</tex>, меньших <tex>t + 1</tex> (до начала цепочки <tex>S</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-функция]]
 +
 
 +
==Источники информации==
 +
*[[wikipedia:en:Knuth–Morris–Pratt algorithm | Wikipedia {{---}} Knuth–Morris–Pratt algorithm]]
 +
*[[wikipedia:ru:Алгоритм Кнута — Морриса — Пратта | Википедия {{---}} Алгоритм Кнута — Морриса — Пратта]]
 +
*Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн — Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е — М.: Издательский дом «Вильямс», 2009. — с.1036. — ISBN 978-5-8459-0857-5.
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Поиск подстроки в строке]]
 +
[[Категория:Точный поиск]]

Текущая версия на 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-функцию. Оценки времени работы и памяти при этом не изменятся.

См. также

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