Алгоритм Кнута-Морриса-Пратта: поиск подстроки за O(n+m)

Алгоритм Кнута-Морриса-Пратта (KMP) - классический способ искать подстроку длины $m$ в тексте длины $n$ за гарантированное $O(n+m)$ без единого возврата по тексту. Опубликован в 1977 году Дональдом Кнутом, Джеймсом Моррисом и Воганом Праттом, но открыт двумя независимыми путями раньше: Моррис придумал основную идею в 1970-м, работая над текстовым редактором, а Кнут и Пратт получили тот же алгоритм в 1973-м, отталкиваясь от теории конечных автоматов. Объединённая статья 1977 года и закрепила тройное имя.

Идея - префикс-функция

Наивный поиск при несовпадении возвращает позицию в тексте назад и начинает сравнивать паттерн с следующей позиции с нуля. Это и есть источник $O(nm)$ в худшем случае: на каждом сдвиге заново пересматривается уже прочитанный кусок текста. KMP избавляется от возвратов, заранее зная о паттерне всё, что нужно: для каждого префикса паттерна вычисляется длина наибольшего собственного префикса, который одновременно является суффиксом. Эта величина и называется префикс-функцией (failure function).

Зачем она нужна. Допустим, мы сопоставили первые $k$ символов паттерна с текстом, а $(k+1)$-й уже не совпал. Если внутри уже сопоставленного префикса есть собственный суффикс, совпадающий с префиксом паттерна длины $\ell < k$ - мы «сдвигаем» паттерн так, чтобы этот префикс встал на место суффикса, и продолжаем сравнение со следующего символа в тексте. Позиция в тексте при этом не уменьшается.

Префикс-функция (failure function)

Формально префикс-функция $\pi$ паттерна $P$ длины $m$ - это массив длины $m$, где

$\pi[i] = \max\{\ell : 0 \le \ell < i + 1,\ P[0..\ell{-}1] = P[i{-}\ell{+}1..i]\}.$

То есть $\pi[i]$ - длина наибольшего собственного префикса подстроки $P[0..i]$, который совпадает с её суффиксом. По соглашению $\pi[0] = 0$.

Алгоритм вычисления - амортизированно $O(m)$:

pi[0] = 0
k = 0
for i in 1..m-1:
    while k > 0 and P[k] != P[i]:
        k = pi[k - 1]
    if P[k] == P[i]:
        k += 1
    pi[i] = k

Почему это $O(m)$. Переменная $k$ растёт максимум на 1 за итерацию (всего $m$ раз) и никогда не падает ниже нуля; во внутреннем while она строго уменьшается. Значит, суммарное число шагов while за весь прогон не превосходит числа инкрементов - то есть $m$. Итого $O(m)$ операций, как ни считай.

Пример вычисления для паттерна $P = \text{ABABAC}$:

$\pi[4] = 3$, потому что $P[0..4] = \text{ABABA}$ имеет собственный префикс $\text{ABA}$, совпадающий с суффиксом $\text{ABA}$. $\pi[5] = 0$, потому что $P[0..5] = \text{ABABAC}$ заканчивается на $\text{C}$, а паттерн начинается с $\text{A}$ - ни один непустой собственный префикс с суффиксом не совпадает.

Сам поиск

Имея $\pi$, основной цикл двигается по тексту только вперёд. Заводим указатели $i$ (позиция в тексте) и $j$ (длина уже сопоставленного префикса паттерна), оба стартуют с нуля:

j = 0
for i in 0..n-1:
    while j > 0 and P[j] != T[i]:
        j = pi[j - 1]
    if P[j] == T[i]:
        j += 1
    if j == m:
        report match at i - m + 1
        j = pi[j - 1]

При несовпадении мы не возвращаем $i$, а только уменьшаем $j$ согласно префикс-функции - то есть «выбираем» из уже сопоставленного префикса максимальный безопасный сдвиг. Тот же аргумент, что и для построения $\pi$, даёт суммарное $O(n)$ операций основного цикла. Вместе с построением - $O(n + m)$.

Подробный пример

Поищем паттерн $P = \text{ABABAC}$ ($m = 6$) в тексте $T = \text{ABABABCABABAC}$ ($n = 13$). Префикс-функция $\pi = [0, 0, 1, 2, 3, 0]$ - вычислена выше.

Шаг $i = 0..3$. Совпали $\text{ABAB}$ → $j = 4$.

Шаг $i = 4$. $T[4] = \text{A}$, $P[4] = \text{A}$ - совпало, $j = 5$.

Шаг $i = 5$. $T[5] = \text{B}$, $P[5] = \text{C}$ - не совпало. Берём $j = \pi[4] = 3$. Сравниваем $P[3] = \text{B}$ с $T[5] = \text{B}$ - совпало, $j = 4$.

Шаг $i = 6$. $T[6] = \text{C}$, $P[4] = \text{A}$ - не совпало. $j = \pi[3] = 2$, $P[2] = \text{A}$ ≠ $\text{C}$. $j = \pi[1] = 0$, $P[0] = \text{A}$ ≠ $\text{C}$. $j$ остался 0, идём дальше.

Шаги $i = 7..11$. Совпали $\text{ABABA}$ → $j = 5$.

Шаг $i = 12$. $T[12] = \text{C}$, $P[5] = \text{C}$ - совпало, $j = 6 = m$. Совпадение на позиции $12 - 6 + 1 = 7$. Откатываемся $j = \pi[5] = 0$.

Итого одно вхождение, указатель $i$ ни разу не возвращался назад - это и есть ключевое свойство KMP. Наивный алгоритм на той же задаче сделал бы около $13 \cdot 6 = 78$ сравнений, KMP справился примерно за $20$.

Сложность и сравнение с Бойером-Муром

KMP - детерминированно $O(n + m)$ в любом случае, без зависимости от данных. Предобработка $O(m)$, поиск $O(n)$, дополнительная память $O(m)$ под массив $\pi$. Никаких таблиц размера алфавита.

Бойер-Мур (1977, та же эпоха) сравнивает паттерн справа налево и при несовпадении сдвигает на большие шаги по двум эвристикам - плохого символа и хорошего суффикса. В лучшем случае Бойер-Мур работает за $O(n/m)$ - сублинейно, не читая большинство символов текста. На английском тексте при паттерне длины 10-20 это типичное поведение, поэтому grep и быстрый поиск в редакторах построены именно на нём.

Когда что выбирать:

• Большой алфавит, длинный паттерн, естественный текст - Бойер-Мур быстрее в среднем за счёт сублинейности.
• Малый алфавит (ДНК, бинарные данные) или важна гарантия в худшем случае - KMP. У него нет патологических входов; Бойер-Мур без модификации Galil деградирует до $O(nm)$ на конструкциях вроде паттерна $\text{aaab}$ в тексте из одних $\text{a}$.

Применения

• Текстовые редакторы и strstr(). Реализация String.indexOf в OpenJDK для длинных паттернов использует KMP; memmem в некоторых libc-вариантах построена на нём же. Vim для /pattern выбирает между KMP и Бойером-Муром по длине паттерна.
• Поиск в DNA-последовательностях. Алфавит из 4 символов - Бойер-Мур теряет преимущество, KMP с гарантированным линейным временем удобнее. В индустриальных пайплайнах чаще берут индексные структуры (суффиксные массивы, FM-индекс), но KMP остаётся опорным алгоритмом в обучении и в быстрых однократных проходах.
• Поиск patterns в логах. Когда текст течёт потоком и не помещается в индекс, KMP даёт стабильную пропускную способность вне зависимости от содержимого.
• Парсинг. Любой синтаксический разбор, где нужно найти конец конструкции - закрывающий тег HTML, разделитель multipart-формы, маркер границы протокола - может опираться на KMP. Префикс-функция строится один раз при инициализации парсера.
• Анализ периодичности. $\pi[m-1]$ напрямую даёт длину наименьшего периода паттерна: $m - \pi[m-1]$, если это число делит $m$. Побочный результат построения, используется в задачах сжатия.

Расширения

Алгоритм Ахо-Корасик (1975) обобщает KMP на множество паттернов сразу. Все паттерны укладываются в префиксное дерево (trie); поверх строится аналог префикс-функции - suffix link, указывающий на узел самого длинного собственного суффикса, который сам является префиксом какого-то паттерна. Поиск всех вхождений суммарной длины $M$ в тексте длины $n$ занимает $O(n + M + z)$, где $z$ - число совпадений. Так работает fgrep со множеством шаблонов и многие антивирусные сканеры сигнатур.

Z-функция - родственная конструкция: $z[i]$ - длина наибольшей подстроки с позиции $i$, совпадающей с префиксом всей строки. Строится тоже за $O(m)$, двойственна префикс-функции и часто проще в реализации. Вхождения паттерна ищутся через конкатенацию P\T$: позиции$i$, где$z[i] = m$, - начала вхождений в$T$.

Частые ошибки

• Возвращают $i$ назад при несовпадении. Тогда теряется главное свойство KMP - линейность; получается замаскированный наивный алгоритм.
• Откатывают $j$ к нулю вместо $\pi[j-1]$. То же самое: сдвиг становится единичным, и предобработка теряет смысл.
• Считают $\pi$ как «длину суффикса, который является префиксом» без слова "собственного". В этом случае $\pi[i] = i + 1$ всегда - алгоритм зацикливается.
• Путают $\pi$ с failure function в смысле конечных автоматов. В литературе встречаются обе формы - в варианте «автомат» хранится таблица переходов $m \times \sigma$ размера; для KMP это лишнее, достаточно одного массива длины $m$.
• Применяют KMP там, где Бойер-Мур или Two-Way быстрее. Для одноразового поиска короткого паттерна в большом тексте на естественном языке Бойер-Мур заметно быстрее в среднем; для повторяющегося поиска одного паттерна - оба хороши, и выбор сводится к деталям реализации.

FAQ

Чем алгоритм Кнута-Морриса-Пратта отличается от наивного? Наивный при несовпадении возвращает позицию в тексте назад и начинает сравнивать паттерн заново - отсюда $O(nm)$. KMP заранее строит префикс-функцию паттерна и при несовпадении сдвигает только указатель в паттерне, не трогая указатель в тексте. Каждый символ текста читается максимум константное число раз - суммарно $O(n+m)$.

Что такое префикс-функция простыми словами? Для каждого префикса паттерна - длина наибольшего собственного префикса, который одновременно является суффиксом. Например, для $\text{ABABA}$ это 3 (префикс и суффикс $\text{ABA}$), для $\text{ABCD}$ - 0 (общих префиксов-суффиксов нет). Она показывает, на сколько символов «откатить» сравнение, если паттерн начал совпадать, а потом не сошёлся.

Когда брать KMP, а когда Бойер-Мур? KMP - когда нужна гарантия $O(n+m)$ в худшем случае, алфавит маленький (ДНК, биты), паттерн короткий, или важна простота кода. Бойер-Мур - когда алфавит большой (естественный язык), паттерн длинный, и средняя скорость важнее гарантий: он даёт сублинейное $O(n/m)$ за счёт пропуска символов.

Коротко

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