Строки: хеши и алгоритм КМП

Два способа быстро искать и сравнивать подстроки: полиномиальный хеш (сравнение за O(1)) и префикс-функция КМП (поиск за O(n+m)).

Полиномиальный хеш сворачивает строку в одно число так, что хеши любых подстрок сравнимы за O(1); префикс-функция — основа алгоритма КМП для поиска образца в тексте за линейное время.

Зачем это нужно

Строковые задачи — отдельный большой пласт олимпиад: поиск образца, подсчёт вхождений, поиск палиндромов, сравнение подстрок, периодичность. Наивный поиск подстроки длины m в тексте длины n — это O(n·m), что не проходит на больших данных. Два классических инструмента решают это линейно или почти линейно: хеширование (сводит сравнение строк к сравнению чисел) и КМП (использует структуру самого образца). Оба входят в обязательный канон competitive programming.

Полиномиальный хеш

Идея: воспринимаем строку как число в системе счисления по основанию base. Хеш — это s[0]·base^(n−1) + s[1]·base^(n−2) + ... + s[n−1] по модулю большого числа. Накопив префиксные хеши (как префиксные суммы из раздела 2!), мы можем получить хеш любой подстроки s[l:r] за O(1) — и сравнивать подстроки мгновенно.

def build_hash(s, base=911382323, mod=(1 << 61) - 1):
    n = len(s)
    h = [0] * (n + 1)          # префиксные хеши
    pw = [1] * (n + 1)         # степени base
    for i in range(n):
        h[i + 1] = (h[i] * base + ord(s[i])) % mod
        pw[i + 1] = pw[i] * base % mod
    return h, pw, mod

def get(h, pw, mod, l, r):     # хеш подстроки s[l:r]
    return (h[r] - h[l] * pw[r - l]) % mod

s = "abracadabra"
h, pw, mod = build_hash(s)
# найдём все вхождения "abra", сравнивая хеши
target = get(h, pw, mod, 0, 4)        # хеш "abra"
found = []
for i in range(len(s) - 3):
    if get(h, pw, mod, i, i + 4) == target:
        found.append(i)
print("'abra' найдено на позициях:", found)

Формула get — это аналог префиксных сумм для хешей: из «хеша до правой границы» вычитаем «хеш до левой», домноженный на нужную степень base. Так сравнение двух подстрок длины L — это сравнение двух чисел за O(1) вместо O(L). Заметь: "abra" встречается в начале (позиция 0) и в конце (позиция 7).

Вывод:

'abra' найдено на позициях: [0, 7]

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

Хеши быстры, но вероятностны (возможны коллизии). Детерминированный линейный поиск даёт алгоритм Кнута-Морриса-Пратта (КМП), основанный на префикс-функции. Префикс-функция pi[i] — это длина наибольшего собственного префикса строки s[0..i], который одновременно является её суффиксом. Звучит мудрёно, но смысл практический: когда при поиске происходит несовпадение, pi подсказывает, насколько можно сдвинуть образец, не теряя уже совпавшего — поэтому текст не нужно «отматывать назад».

def prefix_function(s):
    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

print("pi('abacaba') =", prefix_function("abacaba"))

Разберём pi("abacaba") = [0, 0, 1, 0, 1, 2, 3]. Например, pi[6] = 3 означает: у префикса "abacaba" наибольший собственный префикс-суффикс — это "aba" (длина 3). Алгоритм считает все pi за один проход O(n): хотя есть внутренний while, значение j суммарно увеличивается не более n раз, значит и уменьшается не более n раз (та же амортизация, что в скользящем окне).

Вывод:

pi('abacaba') = [0, 0, 1, 0, 1, 2, 3]

Поиск образца через КМП

Чтобы найти образец pat в тексте text, применяют изящный трюк: строят строку pat + "#" + text (где # — символ, которого нет ни там, ни там) и считают её префикс-функцию. Там, где pi[i] равно длине образца, — вхождение. Разделитель # не даёт префикс-функции «перепрыгнуть» через границу образца.

def prefix_function(s):
    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

def kmp_search(text, pat):
    s = pat + "#" + text
    pi = prefix_function(s)
    m = len(pat)
    res = []
    for i in range(m + 1, len(s)):
        if pi[i] == m:                  # совпал весь образец
            res.append(i - 2 * m)       # позиция начала в тексте
    return res

print("'ab' в 'abcababab':", kmp_search("abcababab", "ab"))
print("'aba' в 'ababab':  ", kmp_search("ababab", "aba"))

Алгоритм находит все вхождения за O(n + m) — линейно от суммарной длины, без отката по тексту. Это его главное преимущество над наивным поиском.

Вывод:

'ab' в 'abcababab': [0, 3, 5, 7]
'aba' в 'ababab':   [0, 2]

Хеши или КМП: что выбрать

Подводные камни

• Коллизии хешей. Антитесты могут подобрать коллизию; берут большой простой модуль (или два хеша сразу) и случайное основание.
• Разделитель в КМП должен не встречаться ни в образце, ни в тексте, иначе вхождения «склеятся».
• Префикс-функция — собственный префикс: он короче всей строки (вся строка суффиксом себя не считается).
• Линейность КМП держится на амортизации while; не пугайся вложенного цикла — суммарно он O(n).

Итог

• Полиномиальный хеш с префиксными хешами сравнивает любые подстроки за O(1) — гибкий, но вероятностный.
• Префикс-функция pi[i] — длина наибольшего собственного префикса-суффикса; считается за O(n).
• КМП ищет образец за O(n+m) через pat + "#" + text без отката по тексту — детерминированно.
• Хеши хороши для сравнения подстрок и гибких задач, КМП — для надёжного поиска и анализа периодов.