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

Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — алгоритм поиска образца (подстроки) в строке.

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

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

Поставим следующую задачу: имеется образец $\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-функция
• Алгоритм Бойера — Мура
• Алгоритм Ахо — Корасик

Ссылки

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