Русская Википедия:Алгоритм Кнута — Морриса — Пратта
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.
Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно в 1977 году[2].
Постановка задачи
Даны образец (строка) <math>\displaystyle S</math> и строка <math>\displaystyle T</math>. Требуется определить индекс, начиная с которого образец <math>\displaystyle S</math> содержится в строке <math>\displaystyle T</math>. Если <math>\displaystyle S</math> не содержится в <math>\displaystyle T</math> — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
Идея
Алгоритм Ахо — Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.
Если искать всего одну строку, каждое состояние будет иметь только один «прямой» переход. Побочные же переходы будем вычислять динамически, никак их не кэшируя.
если haystack[i] = needle[state] то state = state + 1 иначе state = побочный_переход(state, haystack[i])
Легко заметить, что суффиксные ссылки алгоритма Ахо — Корасик представляют собой префикс-функцию искомого шаблона.
Описание алгоритма и оценка времени работы
Рассмотрим сравнение строк на позиции <math>\displaystyle i</math>, где образец <math>\displaystyle S[ 0, m - 1 ]</math> сопоставляется с частью текста <math>\displaystyle \displaystyle T[ i, i + m - 1 ]</math>. Предположим, что первое несовпадение произошло между <math>\displaystyle \displaystyle T[ i + j ]</math> и <math>\displaystyle S[ j ]</math>, где <math>\displaystyle 1 < j < m</math>. Тогда <math>\displaystyle T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P</math> и <math>\displaystyle a = T[ i + j ] \ne S[ j ] = b</math>.
При сдвиге вполне можно ожидать, что префикс (начальные символы) образца <math>\displaystyle S</math> сойдется с каким-нибудь суффиксом (конечные символы) текста <math>\displaystyle P</math>. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки <math>\displaystyle S</math> для индекса <math>\displaystyle j</math>.
Это приводит нас к следующему алгоритму: пусть <math>\displaystyle \rm{\pi}[ j ]</math> — значение префикс-функции от строки <math>\displaystyle S[ 0, m - 1 ]</math> для индекса <math>\displaystyle j</math>. Тогда после сдвига мы можем возобновить сравнения с места <math>\displaystyle T[ i + j ]</math> и <math>\displaystyle S[ \rm{\pi}[ j ] ]</math> без потери возможного местонахождения образца. Можно показать, что таблица <math>\displaystyle \rm{\pi}</math> может быть вычислена (амортизационно) за <math>\displaystyle \Theta( m )</math> сравнений перед началом поиска. А поскольку строка <math>\displaystyle T</math> будет пройдена ровно один раз, суммарное время работы алгоритма будет равно <math>\displaystyle \Theta(m + n)</math>, где <math>n</math> — длина текста <math>\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 A</math> — множество номеров элементов строки <math>\displaystyle T</math>, которыми оканчиваются найденные вхождения <math>\displaystyle S</math> в <math>\displaystyle T</math>.
См. также
Примечания
Ссылки
- Алгоритм Кнута-Морриса-Пратта на сайте Algolist, перевод работы Thierry Lecroq, Christian Charras, Knuth-Morris-Pratt algorithm // Цикл лекций Exact String Matching Algorithms, Université de Rouen, 1997
Шаблон:Перевести Шаблон:RqШаблон:СтрокиШаблон:Дональд Кнут
