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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Независимо, в 1969 году, Матиясевич обнаружил аналогичный алгоритм, закодированный двумерной машиной Тьюринга, при изучении задачи распознавания соответствия строк образцу в двоичном алфавите.

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

[править | править код]

Даны образец (строка) и строка . Требуется определить индекс, начиная с которого образец содержится в строке . Если не содержится в  — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

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

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

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

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

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

[править | править код]

Рассмотрим сравнение строк на позиции , где образец сопоставляется с частью текста . Предположим, что первое несовпадение произошло между и , где . Тогда и .

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца сойдется с каким-нибудь суффиксом (конечные символы) текста . Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки для индекса .

Это приводит нас к следующему алгоритму: пусть  — значение префикс-функции от строки для индекса . Тогда после сдвига мы можем возобновить сравнения с места и без потери возможного местонахождения образца. Можно показать, что таблица может быть вычислена (амортизационно) за сравнений перед началом поиска. А поскольку строка будет пройдена ровно один раз, суммарное время работы алгоритма будет равно , где  — длина текста .

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

[править | править код]
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

Функция возвращает  — множество номеров элементов строки , которыми оканчиваются найденные вхождения в .

Примечания

[править | править код]
  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
  2. Donald Knuth; James H. Morris, Jr, Vaughan Pratt. Fast pattern matching in strings (англ.) // SIAM Journal on Computing[англ.] : journal. — 1977. — Vol. 6, no. 2. — P. 323—350. — doi:10.1137/0206024. Архивировано 4 января 2010 года.