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

Алгоритм Кнута — Морриса — Пратта (КМП, англ. Knuth–Morris–Pratt algorithm, KMP) — это алгоритм поиска подстроки (образца) в строке (тексте), основанный на предварительной обработке образца с целью построения префикс-функции. Относится к классу алгоритмов линейного времени (O(n+m), где n — длина текста, m — длина образца) и является одним из фундаментальных методов в области обработки строк. Алгоритм был разработан в 1970 году Дональдом Кнутом и Воном Праттом, а также независимо Джеймсом Моррисом, и впервые опубликован в 1977 году.

История

До появления алгоритма КМП основным методом поиска подстроки был «наивный» алгоритм, который в худшем случае требовал O(n*m) операций. В 1970 году Дональд Кнут (Стэнфордский университет) и Вон Пратт (Массачусетский технологический институт) независимо друг от друга разработали алгоритм, который позволял выполнять поиск за линейное время. В том же году Джеймс Моррис (Корнеллский университет) создал аналогичный алгоритм для решения задачи поиска в текстовом редакторе. В 1977 году Кнут, Моррис и Пратт совместно опубликовали работу «Fast Pattern Matching in Strings», в которой формально описали алгоритм и его теоретическое обоснование. Алгоритм стал первым в истории методом поиска подстроки с линейной временной сложностью, что сделало его важным вкладом в теорию алгоритмов и комбинаторику строк.

Основная идея

Основная идея алгоритма КМП заключается в том, чтобы избежать повторного сравнения символов текста, которые уже были сопоставлены с образцом, при возникновении несовпадения. В наивном алгоритме при неудачном сравнении образец сдвигается на одну позицию вправо, и сравнение начинается заново с первого символа образца. Алгоритм КМП использует информацию о структуре самого образца, чтобы определить, на сколько позиций можно безопасно сдвинуть образец, не теряя уже проделанной работы.

Для этого строится префикс-функция (англ. prefix function) образца — массив π, где π[i] — длина наибольшего собственного префикса подстроки образца, оканчивающейся в позиции i, который одновременно является её суффиксом. Собственный префикс — это префикс, не равный всей подстроке. Например, для образца «ababaca» префикс-функция будет иметь вид [0, 0, 1, 2, 3, 0, 1].

Описание алгоритма

Предварительная обработка: построение префикс-функции

Префикс-функция вычисляется за линейное время O(m) с помощью итеративного алгоритма. Для каждого индекса i от 1 до m-1 (индексация с 0) определяется значение π[i] на основе предыдущих значений. Алгоритм использует указатель j, который отслеживает длину текущего совпадающего префикса:

1. Если символ образца в позиции i равен символу в позиции j, то π[i] = j + 1, и j увеличивается на 1.
2. Если символы не равны, а j > 0, то j устанавливается равным π[j-1], и сравнение повторяется.
3. Если j = 0, то π[i] = 0.

Поиск подстроки

После построения префикс-функции выполняется поиск образца в тексте. Алгоритм использует два указателя: i — индекс в тексте, j — индекс в образце. Начальные значения: i = 0, j = 0.

1. Сравниваются символы text[i] и pattern[j].
2. Если они равны, то i и j увеличиваются на 1. Если j достигает m (длины образца), то найдено вхождение образца, начиная с позиции i - m. После этого j устанавливается равным π[j-1] для поиска следующих вхождений.
3. Если символы не равны, а j > 0, то j устанавливается равным π[j-1] (без увеличения i). Если j = 0, то i увеличивается на 1.

Алгоритм завершается, когда i достигает n (длины текста). Временная сложность поиска — O(n).

Пример работы

Рассмотрим текст «abcababcd» и образец «ababc». Префикс-функция для образца: [0, 0, 1, 2, 0].

Пошаговое выполнение:

• i=0, j=0: text[0]='a' == pattern[0]='a' → i=1, j=1
• i=1, j=1: text[1]='b' == pattern[1]='b' → i=2, j=2
• i=2, j=2: text[2]='c' != pattern[2]='a' → j=π[1]=0
• i=2, j=0: text[2]='c' != pattern[0]='a' → i=3
• i=3, j=0: text[3]='a' == pattern[0]='a' → i=4, j=1
• i=4, j=1: text[4]='b' == pattern[1]='b' → i=5, j=2
• i=5, j=2: text[5]='a' == pattern[2]='a' → i=6, j=3
• i=6, j=3: text[6]='b' == pattern[3]='b' → i=7, j=4
• i=7, j=4: text[7]='c' == pattern[4]='c' → i=8, j=5 → найдено вхождение на позиции 3 (i-m=8-5=3). j=π[4]=0
• i=8, j=0: text[8]='d' != pattern[0]='a' → i=9 → конец.

Сложность и свойства

• Временная сложность: O(n + m) в худшем случае. Каждый символ текста сравнивается не более одного раза, а каждый символ образца — не более одного раза при построении префикс-функции.
• Пространственная сложность: O(m) для хранения префикс-функции.
• Свойство: Алгоритм не требует возврата в тексте — указатель i всегда движется вперёд. Это делает его пригодным для обработки потоковых данных.
• Корректность: Алгоритм находит все вхождения образца в текст, включая перекрывающиеся.

Применение

Алгоритм Кнута — Морриса — Пратта широко применяется в областях, где требуется быстрый поиск подстроки:

• Текстовые редакторы: функция поиска и замены (например, в редакторах vi, emacs, а также в современных IDE).
• Биоинформатика: поиск последовательностей ДНК или белков в геномных базах данных.
• Сетевые технологии: анализ пакетов данных, поиск сигнатур в системах обнаружения вторжений (например, в Snort).
• Компиляторы и интерпретаторы: лексический анализ, поиск ключевых слов.
• Поисковые системы: индексация и поиск по текстовым документам.

Сравнение с другими алгоритмами

• Наивный алгоритм: O(n*m) в худшем случае. КМП значительно эффективнее при больших текстах и образцах с повторяющимися структурами.
• Алгоритм Бойера — Мура: в среднем быстрее КМП, так как использует эвристики для пропуска больших участков текста. Однако в худшем случае его сложность может быть O(n*m), тогда как КМП гарантирует линейное время.
• Алгоритм Рабина — Карпа: использует хеширование, имеет среднюю сложность O(n+m), но в худшем случае O(n*m) из-за коллизий. КМП не подвержен коллизиям.
• Алгоритм Ахо — Корасик: обобщение КМП для поиска множества образцов одновременно. Строит автомат на основе префикс-функций.

Интересные факты

• Алгоритм КМП был одним из первых алгоритмов, для которого была строго доказана линейная временная сложность.
• Дональд Кнут описывал алгоритм как «первый действительно важный алгоритм для поиска подстроки».
• В 1977 году Кнут, Моррис и Пратт получили премию ACM за лучшую статью в области алгоритмов.
• Префикс-функция, используемая в КМП, также применяется в других задачах, таких как построение Z-функции и алгоритм Манакера для поиска палиндромов.

Источники

• Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323–350.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). М.: Вильямс.
• Седжвик, Р. (2014). Алгоритмы на Java (4-е изд.). М.: Вильямс.
• Ахо, А., Хопкрофт, Дж., Ульман, Дж. (2000). Структуры данных и алгоритмы. М.: Вильямс.