Строковые алгоритмы: KMP, Z-функция, Ахо–Корасик, хеширование

Строки — это единственная структура данных, с которой вы гарантированно работаете каждый день: логи, HTTP-заголовки, ДНК, исходный код, тексты сообщений, сигнатуры вирусов, поисковые запросы. И почти всегда задача сводится к одному вопросу: где здесь встречается вот это?

Наивный ответ на этот вопрос — двойной цикл — работает и укладывается в четыре строки. Проблема в том, что он работает за O(n·m), и на определённых входах эта оценка достигается не «теоретически», а буквально: файл из миллиона нулей и паттерн из тысячи нулей с единицей на конце превратят поиск подстроки в миллиард сравнений. В 2019 году такие входы получили общее имя — ReDoS-подобные атаки на разбор строк, и они реально роняли продакшн.

Эта статья — про четыре инструмента, которые убирают этот квадрат:

• префикс-функция и KMP — один образец, детерминированно, O(n + m);
• Z-функция — тот же результат другим языком, часто короче и удобнее для сравнения суффиксов;
• Ахо–Корасик — тысячи образцов одновременно за один проход по тексту;
• полиномиальное хеширование — сравнение любых двух подстрок за O(1), ценой вероятностной ошибки.

Мы разберём не только «как написать», но и «почему это O(n)» (амортизация — тонкое место во всех четырёх), а также где каждый подход ломается на практике.

Карта области

Слева направо здесь идёт рост «подготовительной работы»: наивный поиск не готовится вовсе, KMP препроцессит образец, Ахо–Корасик — множество образцов, а суффиксные структуры препроцессят текст, чтобы потом отвечать на произвольные запросы. Выбор между ними — это всегда вопрос «что у нас фиксировано и что меняется чаще»: если текст один и запросов много, платите за индекс по тексту; если текст — поток, а образцы фиксированы, стройте автомат по образцам.

Почему наивный поиск плох и когда он всё-таки хорош

def naive_search(text: str, pat: str) -> list[int]:
    """Возвращает все позиции вхождения pat в text. O(n·m) в худшем случае."""
    n, m = len(text), len(pat)
    res = []
    for i in range(n - m + 1):          # каждое возможное выравнивание
        j = 0
        while j < m and text[i + j] == pat[j]:
            j += 1
        if j == m:
            res.append(i)
    return res

Худший случай: text = "a" * n, pat = "a" * (m - 1) + "b". Каждое выравнивание проходит m − 1 успешных сравнений и падает на последнем. Итого (n − m + 1)·m операций.

Ключевая потеря информации здесь вот в чём: сравнив "aaaa" и убедившись, что первые четыре символа совпали, наивный алгоритм выбрасывает это знание и начинает следующее выравнивание с нуля. Все умные алгоритмы поиска — это разные способы не выбрасывать уже добытую информацию.

При этом на «обычных» текстах наивный поиск ведёт себя прекрасно: на случайном тексте над алфавитом размера σ ожидаемое число сравнений на одно выравнивание равно примерно 1/(1 − 1/σ) ≈ 1, то есть общая работа ~O(n). Поэтому в стандартных библиотеках наивный проход не выкинут — он используется как быстрый путь для коротких образцов, а тяжёлая артиллерия включается, только когда наивный цикл начал деградировать (см. FASTSEARCH в CPython: Objects/stringlib/fastsearch.h).

Бордеры: центральное понятие

Бордер (border, «граница», в русской литературе часто «префикс-суффикс») строки s — это такая её собственная подстрока, которая одновременно является префиксом и суффиксом s. Собственная — значит короче самой s.

Примеры:

• "abab" → бордеры: "ab", "". Максимальный — "ab", длина 2.
• "aaaa" → "aaa", "aa", "a", "". Максимальный длины 3.
• "abc" → только "". Максимальный длины 0.

Почему это центральное понятие поиска? Представьте, что мы сопоставили образец P с текстом и совпали первые j символов, а на (j+1)-м сломались. Мы знаем, что в тексте только что прошёл кусок P[0..j−1]. Куда можно сдвинуть образец, чтобы гарантированно не пропустить вхождение? Ровно туда, где новый префикс P совпадёт с суффиксом уже прочитанного P[0..j−1], — то есть на максимальный бордер. Всё остальное — реализация этой мысли.

Есть красивое следствие, которое стоит запомнить отдельно: множество всех бордеров строки — это цепочка. Максимальный бордер b, максимальный бордер этого бордера, и так далее до пустой строки. Эта цепочка называется border chain, её длина O(n), и по ней мы будем «откатываться» при несовпадении.

Префикс-функция

Определение: для строки s длины n префикс-функция π[i] — это длина наибольшего бордера префикса s[0..i]. По соглашению π[0] = 0 (у строки из одного символа собственных бордеров, кроме пустого, нет).

Для s = "ABABABC":

i     0  1  2  3  4  5  6
s     A  B  A  B  A  B  C
π[i]  0  0  1  2  3  4  0

Вычисление за O(n)

Наивно π считается за O(n³) (для каждого префикса перебрать все длины бордеров и сравнить). Быстрый алгоритм опирается на два наблюдения:

1. π[i+1] ≤ π[i] + 1. Действительно, если бордер префикса длины i+2 имеет длину k+1, то, убрав последний символ с обоих концов, получим бордер длины k префикса длины i+1, значит k ≤ π[i]. Отсюда — за один шаг значение растёт максимум на единицу.
2. Если s[i+1] ≠ s[π[i]], то следующий кандидат на бордер — это бордер бордера, то есть π[π[i] − 1]. Мы идём по border chain вниз, пока не найдём подходящий символ или не упрёмся в 0.

def prefix_function(s: str) -> list[int]:
    """π[i] — длина максимального бордера префикса s[0..i]. O(n) время, O(n) память."""
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]                     # кандидат: продолжаем предыдущий бордер
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]                 # спуск по цепочке бордеров
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

Почему это O(n), а не O(n²) — это амортизационный аргумент того же типа, что мы разбирали в статье про анализ алгоритмов. Введём потенциал Φ = j (текущее значение переменной j). Каждая итерация внешнего цикла увеличивает j не более чем на 1, значит суммарный рост потенциала за весь алгоритм ≤ n. Каждая итерация внутреннего while строго уменьшает j минимум на 1. Так как j ≥ 0 всегда, суммарное число итераций while не превосходит суммарного роста, то есть n. Итого ≤ 2n операций.

Это тот случай, когда «в цикле есть цикл» не означает квадрат — и именно здесь чаще всего ошибаются, оценивая сложность KMP на собеседовании.

KMP: собственно поиск

Классическая формулировка Кнута–Морриса–Пратта (Knuth, Morris, Pratt, 1977) использует ту же логику, но применяет π образца к тексту:

KMP(T, P):
    π ← prefix_function(P)
    j ← 0                              # сколько символов P уже совпало
    для i от 0 до |T|-1:
        пока j > 0 и T[i] ≠ P[j]:
            j ← π[j-1]                 # сдвигаем P, i НЕ откатывается
        если T[i] = P[j]:
            j ← j + 1
        если j = |P|:
            вывести вхождение в позиции i - |P| + 1
            j ← π[j-1]                 # готовимся искать пересекающиеся вхождения

def kmp_search(text: str, pat: str) -> list[int]:
    """Все (в том числе пересекающиеся) вхождения pat в text. O(n + m)."""
    if not pat:
        return list(range(len(text) + 1))
    pi = prefix_function(pat)
    res, j = [], 0
    for i, ch in enumerate(text):
        while j > 0 and ch != pat[j]:
            j = pi[j - 1]
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            res.append(i - j + 1)
            j = pi[j - 1]               # НЕ j = 0 — иначе потеряем "aaa" в "aaaa"
    return res

Сложность: O(n + m) время, O(m) дополнительная память. Важнейшее свойство: указатель i по тексту никогда не уменьшается. Это делает KMP пригодным для потоковой обработки — можно скармливать текст по кускам, храня только j. Никакого буфера длиной m не нужно.

Альтернативный трюк, который многие предпочитают писать на олимпиадах: посчитать префикс-функцию строки P + '\x00' + T (разделитель — символ, не встречающийся ни в P, ни в T) и найти все позиции, где π = |P|. Работает, но требует O(n + m) памяти вместо O(m) и потому не годится для потока.

KMP-автомат

Внутренний while можно вообще убрать, предпосчитав таблицу переходов δ[state][c] — куда перейти из состояния «совпало state символов», прочитав символ c:

def kmp_automaton(pat: str, alphabet: str) -> list[dict[str, int]]:
    """δ[state][c] — новое состояние. O(m·|Σ|) время и память."""
    m = len(pat)
    pi = prefix_function(pat)
    delta: list[dict[str, int]] = [dict() for _ in range(m + 1)]
    for state in range(m + 1):
        for c in alphabet:
            if state < m and c == pat[state]:
                delta[state][c] = state + 1          # продвинулись
            elif state == 0:
                delta[state][c] = 0                  # некуда откатываться
            else:
                delta[state][c] = delta[pi[state - 1]][c]   # уже посчитано: pi[state-1] < state
    return delta

Теперь обработка каждого символа — ровно один просмотр таблицы, без циклов. Это ценно, когда нужен предсказуемый worst-case на символ (сетевое оборудование, парсеры в реальном времени), но плата — O(m·σ) памяти. Для σ = 256 и образца в 10 000 символов это 2.5 млн ячеек. Тот же приём в чистом виде появится ниже в Ахо–Корасике.

Что ещё умеет префикс-функция

Префикс-функция — не только про поиск. Несколько классических следствий, которые стоит знать:

1. Минимальный период строки. Строка s длины n периодична с периодом p = n − π[n−1], и это минимальный период. Строка целиком состоит из повторений блока длины p тогда и только тогда, когда n % p == 0. Отсюда — задача «сколько раз надо повторить строку» решается в две строки.

def min_period(s: str) -> int:
    """Минимальный период: s[i] == s[i+p] для всех допустимых i. O(n)."""
    return len(s) - prefix_function(s)[-1]

assert min_period("abcabcabc") == 3
assert min_period("aabaab") == 3
assert min_period("abcd") == 4          # апериодичная строка

2. Все бордеры строки. Цепочка π[n−1], π[π[n−1]−1], … даёт полный список длин бордеров.

3. Число различных подстрок при добавлении символов, сжатие, подсчёт вхождений каждого префикса — всё это стандартные упражнения на π. Подробный список с доказательствами — cp-algorithms: prefix function.

Z-функция

z[i] — длина наибольшего общего префикса строки s и её суффикса, начинающегося в позиции i. z[0] обычно доопределяют как n (или оставляют неопределённым).

i     0  1  2  3  4  5  6  7
s     a  a  b  c  a  a  b  x
z[i]  8  1  0  0  3  1  0  0

z[4] = 3, потому что суффикс "aabx" совпадает с префиксом "aab" на трёх символах.

Z-функция и префикс-функция несут одну и ту же информацию — из одной за O(n) выводится другая, — но говорят на разных языках. π отвечает на вопрос «насколько я могу продолжить совпадение назад», z — «насколько далеко я совпадаю вперёд». Второе часто удобнее.

Алгоритм с Z-блоком

Идея: поддерживаем самый правый по правому концу отрезок [l, r), который совпадает с префиксом строки. Он называется Z-блоком (Z-box). Оказавшись в позиции i внутри блока, мы уже знаем, что s[i..r) = s[i−l..r−l), а значит можем скопировать ответ из зеркальной позиции i − l.

(На схеме r — включительный правый конец, чтобы было нагляднее; в коде удобнее полуинтервал.)

def z_function(s: str) -> list[int]:
    """z[i] — длина наибольшего общего префикса s и s[i:]. O(n) время, O(n) память."""
    n = len(s)
    z = [0] * n
    z[0] = n
    l = r = 0                              # текущий Z-блок [l, r), r — исключительно
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])    # копируем ответ из зеркала, но не выходим за r
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1                      # «доигрываем» наивно
        if i + z[i] > r:
            l, r = i, i + z[i]             # блок сдвинулся вправо
    return z

Амортизация ровно того же сорта, что в префикс-функции: потенциал — это r. Он монотонно не убывает и ограничен n, а каждая итерация внутреннего while увеличивает r минимум на единицу (потому что срабатывает только тогда, когда мы вышли за границу блока). Значит, суммарное число «доигрываний» — O(n).

Тонкий момент, на котором ловятся почти все: min(r - i, z[i - l]). Если написать просто z[i] = z[i - l], алгоритм сломается, когда зеркальный ответ упирается в границу блока — дальше границы никакой информации у нас нет, там могут быть любые символы.

Поиск через Z-функцию

def z_search(text: str, pat: str) -> list[int]:
    """Поиск через конкатенацию. O(n + m) время и O(n + m) памяти."""
    sep = '\x00'                          # символ, не встречающийся в данных
    z = z_function(pat + sep + text)
    m = len(pat)
    return [i - m - 1 for i in range(m + 1, len(z)) if z[i] >= m]

Проще KMP по коду, но требует конкатенации, то есть O(n + m) памяти и невозможности работать с потоком. Практический вывод: Z-функция — для оффлайн-задач и анализа строк, KMP — для потоков.

Связь Z ↔ π

Из z в π за O(n) (амортизированно — внутренний цикл прерывается на первой заполненной ячейке):

def z_to_pi(z: list[int]) -> list[int]:
    n = len(z)
    pi = [0] * n
    for i in range(1, n):
        for j in range(z[i] - 1, -1, -1):
            if pi[i + j] > 0:
                break                      # дальше всё уже заполнено бо́льшими значениями
            pi[i + j] = j + 1
    return pi

Обратное преобразование ещё проще и делается через тот же приём с Z-блоком. Практический смысл: если вы уверенно владеете одной из функций, вторая вам формально не нужна — но читать чужой код придётся на обеих.

Полиномиальное хеширование

Совсем другой подход. Вместо того чтобы аккуратно эксплуатировать структуру строки, сопоставим каждой строке число так, чтобы равные строки давали равные числа, а разные — с высокой вероятностью разные.

Полиномиальный хеш строки s длины m по базе B и модулю M:

H(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + … + s[m-1]·B^0) mod M

Это просто «число, записанное в системе счисления с основанием B, где цифры — коды символов».

Главное свойство — префиксные хеши дают O(1) на любую подстроку. Если h[i] = H(s[0..i−1]), то

H(s[l..r-1]) = (h[r] − h[l]·B^(r−l)) mod M

Это ровно то же самое, что префиксные суммы, только вместо сложения — «сдвиг по позиции».

import random

MOD = (1 << 61) - 1                  # простое Мерсенна: быстрый mod, огромное пространство

class PolyHash:
    """Префиксные хеши. Построение O(n), запрос подстроки O(1)."""

    def __init__(self, s: str) -> None:
        # База выбирается СЛУЧАЙНО в рантайме — так против нас нельзя подготовить тест
        self.base = random.randrange(256, MOD - 1)
        n = len(s)
        self.h = [0] * (n + 1)
        self.p = [1] * (n + 1)
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * self.base + ord(ch)) % MOD
            self.p[i + 1] = (self.p[i] * self.base) % MOD

    def sub(self, l: int, r: int) -> int:
        """Хеш s[l:r] за O(1)."""
        return (self.h[r] - self.h[l] * self.p[r - l]) % MOD


# Пример: сравнить две подстроки за O(1)
H = PolyHash("abracadabra")
assert H.sub(0, 4) == H.sub(7, 11)   # "abra" == "abra"

Рабин–Карп: скользящий хеш

Для поиска одного образца хеш можно катить по окну, не храня префиксов (Karp & Rabin, 1987):

def rabin_karp(text: str, pat: str, verify: bool = True) -> list[int]:
    """Скользящий хеш. O(n + m) ожидаемо; O(n·m) в патологическом худшем случае с verify=True."""
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    base = random.randrange(256, MOD - 1)
    power = pow(base, m - 1, MOD)        # вес старшего символа окна

    hp = 0
    for ch in pat:
        hp = (hp * base + ord(ch)) % MOD

    h = 0
    for k in range(m):
        h = (h * base + ord(text[k])) % MOD

    res = []
    if h == hp and (not verify or text[0:m] == pat):
        res.append(0)
    for i in range(m, n):
        # выкидываем text[i-m], добавляем text[i]
        h = ((h - ord(text[i - m]) * power) * base + ord(text[i])) % MOD
        if h == hp and (not verify or text[i - m + 1:i + 1] == pat):
            res.append(i - m + 1)
    return res

Заметьте флаг verify. С ним алгоритм — Las Vegas: ответ всегда правильный, время вероятностное. Без него — Monte Carlo: время всегда O(n), ответ правильный с высокой вероятностью. Эта дихотомия подробно разбирается в статье про рандомизированные алгоритмы.

Насколько велика вероятность коллизии

Это место, где чаще всего врут себе. Для одного сравнения двух разных строк вероятность совпадения хешей ≈ 1/M. Но если вы сравниваете q пар (например, кладёте q хешей в множество и ищете дубликат), работает парадокс дней рождения: вероятность хотя бы одной коллизии ≈ q²/(2M).

Практическое правило: один хеш по модулю порядка 10⁹ — это баг, а не оптимизация. Берите 2⁶¹ − 1 (быстрый модуль через сдвиги) либо пару независимых модулей ~10⁹, что эквивалентно ~10¹⁸.

Атаки на хеш и как защищаться

Полиномиальный хеш с фиксированной базой и модулем ломается злонамеренно:

• Хеш по 2⁶⁴ (переполнение unsigned long long). Существует построение Thue–Morse, дающее коллизию на строках длиной ~2048 символов для любой базы. Просто не используйте mod 2^64.
• Известные база и модуль. Против фиксированных констант коллизию строят перебором за минуты (birthday attack). Отсюда единственная надёжная защита — случайная база в рантайме (random.randrange, не srand(42)). Подробный разбор: Codeforces, «Anti-hash tests».
• Hash-flooding в проде. Тот же класс проблем убил дефолтные хеш-таблицы в вебе в 2011-м (28C3 «Efficient Denial of Service Attacks on Web Application Platforms»), после чего в Python, Ruby, Rust и др. появилась рандомизация seed (PYTHONHASHSEED) и SipHash. Мораль одна и та же: детерминированная хеш-функция, известная атакующему, — это уязвимость.

Последняя ветка важна отдельно: полиномиальный хеш не криптографический. Если вы дедуплицируете пользовательские файлы и злоумышленник может подобрать коллизию, чтобы подменить чужой файл, — нужен настоящий криптографический хеш.

Где хеши незаменимы

Хеш выигрывает не в поиске одного образца (там KMP лучше и детерминирован), а там, где нужна гибкость:

• сравнение произвольных подстрок за O(1) → бинарный поиск по длине общего префикса двух суффиксов за O(log n) (полезно вместе с бинарным поиском по ответу);
• поиск наибольшей общей подстроки двух строк за O((n+m)·log n) — бинпоиск по длине + множество хешей;
• проверка палиндромности подстроки за O(1) (хеш прямой строки + хеш развёрнутой);
• дедупликация и rolling-hash chunking в системах хранения — content-defined chunking в rsync, borgbackup, restic, Git-подобных хранилищах. Здесь скользящий хеш решает, где резать поток на блоки, чтобы вставка байта в середину не сдвигала все границы.

Ахо–Корасик: много образцов за один проход

Задача меняется: у нас не один образец, а словарь из k образцов (сигнатуры вирусов, стоп-слова, правила IDS, словарь морфологии). Наивно — запустить KMP k раз, получив O(k·n). При k = 50 000 и потоке в гигабайт это неприемлемо.

Ахо–Корасик (Aho & Corasick, CACM 1975) — это обобщение KMP на множество образцов. Идея прямая:

1. Сложить все образцы в бор (trie). Путь от корня — это префикс какого-то образца.
2. Достроить суффиксные ссылки (fail links): fail[v] указывает на вершину, соответствующую наибольшему собственному суффиксу строки v, который тоже является вершиной бора. Это ровно то же, что π — только на дереве вместо строки.
3. Идти по тексту, при несовпадении спускаясь по fail-ссылкам.

Вот автомат для словаря {he, she, his, hers} — классический пример из оригинальной статьи. Пунктиром показаны суффиксные ссылки (ссылки в корень для наглядности опущены):

Обратите внимание на состояние she: попав в него, мы обязаны сообщить не только о вхождении "she", но и о вхождении "he" — потому что "he" является суффиксом "she". Это и есть смысл fail-цепочки при выводе результатов, и именно здесь чаще всего теряют вхождения.

Реализация

from collections import deque
from typing import Iterator


class AhoCorasick:
    """Мультипаттерн-поиск. Построение O(Σ|p_i|), поиск O(n + число вхождений)."""

    def __init__(self, patterns: list[str]) -> None:
        self.next: list[dict[str, int]] = [{}]   # goto-переходы бора
        self.fail: list[int] = [0]               # суффиксные ссылки
        self.out: list[list[int]] = [[]]         # индексы образцов, кончающихся здесь
        self.out_link: list[int] = [0]           # ближайший терминал вверх по fail-цепочке

        for idx, p in enumerate(patterns):
            v = 0
            for ch in p:
                nxt = self.next[v].get(ch)
                if nxt is None:
                    nxt = len(self.next)
                    self.next.append({})
                    self.fail.append(0)
                    self.out.append([])
                    self.out_link.append(0)
                    self.next[v][ch] = nxt
                v = nxt
            self.out[v].append(idx)

        self._build_links()

    def _build_links(self) -> None:
        """BFS по бору: fail-ссылка вершины строится из уже готовой fail-ссылки родителя."""
        q = deque()
        for u in self.next[0].values():
            self.fail[u] = 0                     # дети корня падают в корень
            q.append(u)
        while q:
            v = q.popleft()
            f = self.fail[v]
            # сжатая цепочка терминалов: пропускаем нетерминальные звенья
            self.out_link[v] = f if self.out[f] else self.out_link[f]
            for ch, u in self.next[v].items():
                w = self.fail[v]
                while w and ch not in self.next[w]:
                    w = self.fail[w]
                self.fail[u] = self.next[w].get(ch, 0)
                q.append(u)

    def find(self, text: str) -> Iterator[tuple[int, int]]:
        """Отдаёт пары (позиция конца вхождения, индекс образца)."""
        v = 0
        for i, ch in enumerate(text):
            while v and ch not in self.next[v]:
                v = self.fail[v]
            v = self.next[v].get(ch, 0)
            u = v if self.out[v] else self.out_link[v]
            while u:
                for idx in self.out[u]:
                    yield i, idx
                u = self.out_link[u]


ac = AhoCorasick(["he", "she", "his", "hers"])
print(list(ac.find("ushers")))   # [(3, 1), (3, 0), (5, 3)] — "she", "he", "hers"

Почему BFS, а не DFS? Потому что fail[u] для ребёнка u вычисляется через fail[v] родителя, а глубина fail[v] строго меньше глубины v. Обход в ширину гарантирует, что все вершины меньшей глубины уже обработаны. Это тот же порядок «сначала более короткие суффиксы», что в обходах графов.

Сложность и оптимизации

Наивная реализация find использует while по fail-ссылкам — амортизированно это O(1) на символ (тот же потенциал: глубина текущей вершины). Но worst-case на отдельный символ равен O(глубины), что для сетевого оборудования неприемлемо — там строят полный автомат, где goto определён для всех пар (состояние, символ), и переход всегда ровно один. Цена — память O(L·σ).

Отдельная ловушка — вывод вхождений. Если наивно идти по всей fail-цепочке на каждом символе, получите O(n·L) на словаре вроде {a, aa, aaa, …} на тексте aaaa…. Спасают два приёма: out_link (сжатая цепочка только по терминалам, как в коде выше) и — если нужен лишь факт совпадения, а не все вхождения — предпосчёт булева флага has_match на каждой вершине. Заметьте: если вхождений действительно Θ(n·k), то никакой алгоритм быстрее не выведет их все; O(n + occ) — это оптимум.

Ахо–Корасик в проде

• Сетевые IDS. Snort и Suricata используют Ахо–Корасик (в терминах Suricata — mpm, multi-pattern matcher) для первичного отбора пакетов по тысячам сигнатур; полные regex-правила запускаются только на прошедших фильтр. Суть — дешёвый префильтр перед дорогим движком.
• Антивирусы. ClamAV матчит десятки тысяч сигнатур одним проходом по файлу (документация по сигнатурам).
• Rust-крейт aho-corasick от автора ripgrep — эталонная промышленная реализация: несколько представлений автомата (NFA/DFA), выбор в зависимости от размера словаря, SIMD-префильтр Teddy для маленьких словарей. Читать её исходники полезнее, чем ещё одну статью. См. также разбор устройства в блоге BurntSushi про ripgrep.
• Токенизация и морфология. Словарные токенизаторы для японского/китайского (MeCab, Kuromoji) и WordPiece-подобные схемы — это бор + суффиксные ссылки в том или ином виде.
• Фильтры контента, DLP, скан секретов (обнаружение утёкших ключей в коммитах) — все строятся на мультипаттерн-матчере плюс проверке.

Другие алгоритмы, которые стоит знать

Boyer–Moore и Horspool. KMP читает каждый символ текста ровно один раз, то есть делает Ω(n) работы. Boyer–Moore (1977) сравнивает образец справа налево и при несовпадении может прыгнуть сразу на m символов вперёд, то есть работает сублинейно: O(n/m) в лучшем случае. На естественных текстах и длинных образцах это в разы быстрее KMP, поэтому именно семейство BM живёт в реальных grep.

Two-way (Crochemore–Perrin). Комбинирует сублинейность BM с линейной гарантией худшего случая и O(1) дополнительной памятью. Именно он стоит в glibc (string/str-two-way.h) и в CPython для длинных образцов (начиная с 3.10). Знать наизусть не нужно — нужно знать, что стандартный strstr/str.find уже умнее вашего KMP, и переписывать его вручную обычно не надо.

Манакер. Все палиндромные подстроки за O(n) тем же приёмом «правого блока», что в Z-функции. Хешем ту же задачу решают за O(n log n) — короче кодом, дороже асимптотически.

Суффиксные структуры. Когда текст фиксирован, а запросов много, правильный ответ — индекс по тексту: суффиксный массив + LCP (O(n) построение алгоритмом SA-IS), суффиксное дерево или суффиксный автомат. Это фундамент полнотекстового поиска и биоинформатики (BWT/FM-индекс в bwa, bowtie). Каноническое изложение — Gusfield, Algorithms on Strings, Trees, and Sequences.

Как выбирать: сводная таблица

История вопроса, чтобы держать в голове контекст:

Типичные ошибки

1. j = 0 вместо j = π[j−1] после найденного вхождения в KMP. Пропустятся пересекающиеся вхождения: "aaa" в "aaaa" найдётся один раз вместо двух.
2. Оценка KMP как O(n·m) из-за вложенного while. Разберитесь с потенциалом один раз — пригодится и в Z-функции, и в Ахо–Корасике, и в скользящем окне.
3. z[i] = z[i−l] без min(r − i, …). Классический баг Z-функции: за границей Z-блока гарантий нет.
4. Разделитель в P + sep + T, встречающийся в данных. Если sep есть в тексте, найдутся ложные вхождения. Берите символ вне алфавита или храните длины явно.
5. Хеш по mod 2^64 / фиксированной базе. Ломается детерминированной анти-тест-строкой.
6. Один модуль ~10⁹ при q ≈ 10⁶ сравнений. Коллизия почти гарантирована парадоксом дней рождения, а найдёте вы её в проде.
7. Отрицательный результат % в C++/Java. (h[r] − h[l]·p) % M может быть отрицательным — нужно ((x % M) + M) % M. В Python эта ловушка отсутствует.
8. Обход всей fail-цепочки на каждом символе в Ахо–Корасике. Даёт квадрат на «вложенных» словарях. Нужен out_link.
9. Работа с байтами как с символами в UTF-8. Поиск по байтам найдёт вхождение, начинающееся в середине многобайтового символа. Либо работайте с кодовыми точками, либо проверяйте выравнивание границ (в UTF-8 самосинхронизация помогает: продолжающие байты имеют вид 10xxxxxx).
10. Написание своего strstr без замера. В 90% случаев библиотечный быстрее: он использует SIMD (memchr на первом символе) и хорошо оптимизирован. Свой KMP пишите, когда нужна потоковость или нестандартная семантика.

Мини-итог

• Все быстрые алгоритмы поиска — это способы не выбрасывать уже добытую информацию о частичном совпадении.
• Бордер (префикс = суффикс) — общее ядро KMP и Ахо–Корасика; префикс-функция считает бордеры на строке, fail-ссылки — на боре.
• Z-функция — то же знание в другой системе координат; удобнее для анализа строк, хуже для потоков.
• Линейность KMP, Z-функции и Ахо–Корасика доказывается одним и тем же аргументом потенциала. Выучите его один раз.
• Хеширование покупает гибкость (сравнение любых подстрок за O(1)) ценой вероятностной ошибки. Случайная база в рантайме и модуль ~10¹⁸ — не паранойя, а норма.
• Ахо–Корасик — правильный ответ на «много образцов, один поток». В проде он живёт как дешёвый префильтр перед дорогим движком.
• Если текст фиксирован, а запросов много, стройте индекс по тексту, а не автомат по образцу.

Источники

• T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4th ed., глава 32 «String Matching» — mitpress.mit.edu.
• D. Gusfield. Algorithms on Strings, Trees, and Sequences — каноническое изложение Z-алгоритма и суффиксных структур, Cambridge University Press.
• D. Knuth, J. Morris, V. Pratt. «Fast Pattern Matching in Strings», SIAM J. Computing, 1977 — doi:10.1137/0206024.
• A. Aho, M. Corasick. «Efficient String Matching: An Aid to Bibliographic Search», CACM, 1975 — dl.acm.org/doi/10.1145/360825.360855.
• R. Boyer, J. Moore. «A Fast String Searching Algorithm», CACM, 1977 — dl.acm.org/doi/10.1145/359842.359859.
• R. Karp, M. Rabin. «Efficient randomized pattern-matching algorithms», IBM J. Res. Dev., 1987 — doi:10.1147/rd.312.0249.
• cp-algorithms: prefix function, Z-function, Aho–Corasick, string hashing.
• Codeforces: «Anti-hash tests» и Thue–Morse против mod 2^64.
• A. Gallant (BurntSushi). aho-corasick и «ripgrep is faster than…» — промышленный взгляд.
• X. Wang et al. «Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs», NSDI 2019 — usenix.org; код: github.com/intel/hyperscan.
• CPython: Objects/stringlib/fastsearch.h — реальный гибрид наивного поиска, Bloom-фильтра по символам и two-way.

Что дальше

Мы разобрали задачи, где данные одномерны — это строка символов. Дальше переходим в плоскость: как считать пересечения отрезков, строить выпуклые оболочки и почему в геометрии главный враг — не асимптотика, а числа с плавающей точкой.

Вычислительная геометрия: примитивы, выпуклая оболочка, sweep line