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

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

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

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

Постановка задачи[править | править код]

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

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

Алгоритм Ахо — Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за 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}
      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.

Ссылки[править | править код]