Алгоритм Кнута

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм, осуществляющий поиск подстроки в строке.

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

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

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

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

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

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

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

См. также

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

Примечания

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

Ссылки

Имеется викиучебник по теме
«Примеры реализации алгоритма КМП»

• http://algolist.manual.ru/search/esearch/kmp.php