Кнут — Моррис — Пратт: поиск подстроки, который не возвращается назад

Наивный поиск слова в тексте всё время отступает назад и перечитывает; КМП читает каждый символ ровно один раз и не оглядывается.

Дональд Кнут увидел идею в чужой работе по теории автоматов и вместе с коллегами довёл её до строкового алгоритма — одного из первых с доказанной линейностью.

Почему наивный поиск медленный

Ищем образец AAAB в тексте AAAAAAAAB. Прикладываем образец к началу, сравниваем посимвольно. Три A совпали, на четвёртом — B против A — провал. Что делает наивный алгоритм? Сдвигает образец на одну позицию вправо и начинает сравнение заново с первого символа, снова перечитывая почти всё, что уже читал. На «злом» тексте это даёт до $O(n \cdot m)$ операций, где $n$ — длина текста, $m$ — длина образца. Для длинных строк с повторами — катастрофа.

Прозрение: мы уже знаем то, что прочитали

Главная мысль КМП: при несовпадении не нужно возвращаться в тексте. Если часть образца уже совпала с текстом, мы знаем эти символы — они есть и в образце. Зачем перечитывать их в тексте? Достаточно сдвинуть образец на максимальную безопасную величину, опираясь только на структуру самого образца. Указатель по тексту движется строго вперёд, символ за символом, и никогда не откатывается.

Префикс-функция — сердце алгоритма

Чтобы знать, насколько сдвигать образец, КМП заранее анализирует сам образец (текст ещё не нужен). Для каждой позиции считается длина самого длинного собственного префикса, который одновременно является суффиксом начала образца. Звучит мудрёно, но смысл прост: «если мы совпали до сюда и сорвались, какой кусок начала образца уже гарантированно совпадает с концом совпавшего участка — и значит, его можно не перепроверять».

Например, для образца ABABC префикс-функция на позиции перед C равна 2: префикс AB совпадает с суффиксом AB. Сорвавшись на C, мы не откатываемся к началу, а продолжаем, зная, что два символа AB уже на месте.

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]      # откатываемся по уже посчитанным префиксам
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    pi = prefix_function(pattern)
    found, k = [], 0
    for i in range(len(text)):      # i по тексту — только вперёд!
        while k > 0 and text[i] != pattern[k]:
            k = pi[k - 1]           # сдвигаем образец без отката текста
        if text[i] == pattern[k]:
            k += 1
        if k == len(pattern):
            found.append(i - k + 1) # нашли вхождение
            k = pi[k - 1]           # ищем следующее, возможно с нахлёстом
    return found

print(prefix_function("ABABC"))            # [0, 0, 1, 2, 0]
print(kmp_search("ABABDABACDABABCABAB", "ABABC"))  # [10]
print(kmp_search("aaaaa", "aa"))           # [0, 1, 2, 3]

Линейность: каждый символ — один раз

И построение префикс-функции, и сам поиск работают за линейное время. Указатель по тексту проходит ровно $n$ шагов вперёд. Откаты по образцу через префикс-функцию в сумме не превышают числа продвижений — это доказывается через амортизированный анализ: сколько раз указатель образца увеличился, столько раз он суммарно может уменьшиться. Итог — честные $O(n + m)$ независимо от «злости» входных данных.

Где это нужно

КМП и его идеи живут в grep, в поиске по тексту в редакторах, в анализе ДНК (поиск генетических последовательностей в геноме — это поиск подстроки в строке из миллиардов букв), в системах обнаружения вторжений, где сигнатуры атак ищутся в трафике. Префикс-функция сама по себе — мощный инструмент: через неё решаются задачи на периодичность строк и сжатие.

Мораль

КМП — гимн идее «не выбрасывай уже проделанную работу». Наивный поиск каждый раз начинает с нуля, будто ничего не помнит. КМП один раз изучает образец и потом всю дорогу пользуется этим знанием. В программировании это повторяющийся мотив: предобработка ради того, чтобы основной проход стал линейным и без возвратов.