Алгоритм Кнута — Морриса — Пратта

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.

Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году.

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

Даны образец (строка) [math]\displaystyle{ \displaystyle S }[/math] и строка [math]\displaystyle{ \displaystyle T }[/math]. Требуется определить индекс, начиная с которого образец [math]\displaystyle{ \displaystyle S }[/math] содержится в строке [math]\displaystyle{ \displaystyle T }[/math]. Если [math]\displaystyle{ \displaystyle S }[/math] не содержится в [math]\displaystyle{ \displaystyle T }[/math] — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Идея

Алгоритм Ахо — Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.

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

если haystack[i] = needle[state]
  то state = state + 1
  иначе state = побочный_переход(state, haystack[i])

Легко заметить, что суффиксные ссылки алгоритма Ахо — Корасик представляют собой префикс-функцию искомого шаблона.

Описание алгоритма и оценка времени работы

Рассмотрим сравнение строк на позиции [math]\displaystyle{ \displaystyle i }[/math], где образец [math]\displaystyle{ \displaystyle S[ 0, m - 1 ] }[/math] сопоставляется с частью текста [math]\displaystyle{ \displaystyle \displaystyle T[ i, i + m - 1 ] }[/math]. Предположим, что первое несовпадение произошло между [math]\displaystyle{ \displaystyle \displaystyle T[ i + j ] }[/math] и [math]\displaystyle{ \displaystyle S[ j ] }[/math], где [math]\displaystyle{ \displaystyle 1 \lt j \lt m }[/math]. Тогда [math]\displaystyle{ \displaystyle T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P }[/math] и [math]\displaystyle{ \displaystyle a = T[ i + j ] \ne S[ j ] = b }[/math].

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца [math]\displaystyle{ \displaystyle S }[/math] сойдется с каким-нибудь суффиксом (конечные символы) текста [math]\displaystyle{ \displaystyle P }[/math]. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки [math]\displaystyle{ \displaystyle S }[/math] для индекса [math]\displaystyle{ \displaystyle j }[/math].

Это приводит нас к следующему алгоритму: пусть [math]\displaystyle{ \displaystyle \rm{\pi}[ j ] }[/math] — значение префикс-функции от строки [math]\displaystyle{ \displaystyle S[ 0, m - 1 ] }[/math] для индекса [math]\displaystyle{ \displaystyle j }[/math]. Тогда после сдвига мы можем возобновить сравнения с места [math]\displaystyle{ \displaystyle T[ i + j ] }[/math] и [math]\displaystyle{ \displaystyle S[ \rm{\pi}[ j ] ] }[/math] без потери возможного местонахождения образца. Можно показать, что таблица [math]\displaystyle{ \displaystyle \rm{\pi} }[/math] может быть вычислена (амортизационно) за [math]\displaystyle{ \displaystyle \Theta( m ) }[/math] сравнений перед началом поиска. А поскольку строка [math]\displaystyle{ \displaystyle T }[/math] будет пройдена ровно один раз, суммарное время работы алгоритма будет равно [math]\displaystyle{ \displaystyle \Theta(m + n) }[/math], где [math]\displaystyle{ n }[/math] — длина текста [math]\displaystyle{ \displaystyle T }[/math].

Псевдокод для алгоритма

function KMP(S, T) 
  k ← 0
  A ← ø   // A - пустое множество
  π ← Prefix_Function(S)    // считается префикс-функция от образца S
  for i = 1 to |T| do    // |T| - длина строки T
    while k > 0 and T[i] ≠ S[k + 1] do
      k ←  π[k]
    end while
    if T[i] = S[k + 1] then
      k ← k + 1
    end if
    if k = |S| then
      A ← A ⋃ {i - |S| + 1} // это если мы в начале считали префикс-функцию
      A ← A ⋃ {i}           // это если мы в начале считали z-функцию
      k ← π[k]
    end if
  end for
  return A  
end function

Функция возвращает [math]\displaystyle{ \displaystyle A }[/math] — множество номеров элементов строки [math]\displaystyle{ \displaystyle T }[/math], которыми оканчиваются найденные вхождения [math]\displaystyle{ \displaystyle S }[/math] в [math]\displaystyle{ \displaystyle T }[/math].

См. также

• Z-функция
• Алгоритм Бойера — Мура

Ссылки

• Алгоритм Кнута-Морриса-Пратта на сайте Algolist, перевод работы Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algorithm // Цикл лекций Exact String Matching Algorithms, Université de Rouen, 1997