Алгоритмы на строках: KMP и другие паттерны

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

Каждый день ты используешь поиск строк, даже не подозревая об этом: - 🔍 Google/Яндекс: находят твой запрос среди триллионов веб-страниц за миллисекунды - 📱 WhatsApp/Telegram: поиск по истории сообщений работает мгновенно - 🧬 Биоинформатика: поиск ДНК-последовательностей в геноме человека - 🛡️ Антивирусы: ищут сигнатуры вирусов в файлах

Наивный поиск “в лоб” работает за O(nm) времени. А что если текст размером в терабайт? Нужны хитрые алгоритмы!

📚 История вопроса

В 1970 году Дональд Кнут, Джеймс Моррис и Воган Пратт решили проблему, которая мучила программистов десятилетиями: как искать подстроку быстрее, чем за O(nm)?

Их алгоритм KMP (Knuth-Morris-Pratt) стал прорывом - он работает за O(n+m) и используется везде: от текстовых редакторов до поисковых движков. Интересно, что похожий алгоритм независимо изобрел советский математик в 1973!

💡 Интуиция

Проблема наивного поиска

Представь, что ищешь слово “ABABA” в тексте “ABABCABABA”: Текст: A B A B C A B A B A Паттерн: A B A B A ^ ^ совпало не совпало code Code Наивный алгоритм сдвинет паттерн на 1 позицию и начнет сравнивать заново: Текст: A B A B C A B A B A Паттерн: A B A B A code Code [МЕДИА: image_01] Описание: Визуализация наивного поиска подстроки с лишними сравнениями Промпт: “educational illustration showing naive string search algorithm, text and pattern alignment, highlighting redundant comparisons, arrows showing character-by-character matching, clean algorithmic style”

Идея KMP: используем уже сравненную информацию!

KMP понимает: мы уже знаем, что первые 4 символа совпали! Зачем проверять их снова?

Ключевая идея: если произошло несовпадение, сдвигаем паттерн не на 1, а сразу на максимально возможное расстояние.

📐 Формальное определение

Префикс-функция π[i]

Для строки s длины n префикс-функция π[i] - это длина наибольшего собственного префикса строки s[0..i], который является также суффиксом этой строки.

Собственный префикс = префикс, не равный всей строке.

Для паттерна “ABABA”: - π[0] = 0 (у “A” нет собственных префиксов)
- π[1] = 0 (у “AB” совпадающих префикс-суффиксов нет) - π[2] = 1 (“ABA”: префикс “A” = суффикс “A”) - π[3] = 2 (“ABAB”: префикс “AB” = суффикс “AB”)
- π[4] = 3 (“ABABA”: префикс “ABA” = суффикс “ABA”)

[МЕДИА: image_02] Описание: Пошаговое вычисление префикс-функции для строки ABABA Промпт: “step-by-step computation of prefix function, string ABABA with highlighted prefixes and suffixes, arrows showing matching parts, mathematical notation, educational diagram style”

Алгоритм KMP

```python def kmp_search(text, pattern): n, m = len(text), len(pattern)

# Вычисляем префикс-функцию
pi = compute_pi(pattern)

j = 0  # индекс в паттерне
matches = []

for i in range(n):  # идем по тексту
    # "Откатываемся" пока символы не совпадают
    while j > 0 and text[i] != pattern[j]:
        j = pi[j - 1]

    # Если символы совпали
    if text[i] == pattern[j]:
        j += 1

    # Если весь паттерн найден
    if j == m:
        matches.append(i - m + 1)
        j = pi[j - 1]  # продолжаем поиск

return matches

def compute_pi(pattern): m = len(pattern) pi = [0] * m

for i in range(1, m):
    j = pi[i - 1]

    while j > 0 and pattern[i] != pattern[j]:
        j = pi[j - 1]

    if pattern[i] == pattern[j]:
        j += 1

    pi[i] = j

return pi

Временная сложность: O(n + m) - линейная! Пространственная сложность: O(m) - только для префикс-функции 🔍 Примеры с разбором Пример 1: Поиск “ABABACA” в “ABABABACABA” 1️⃣ Вычисляем π для “ABABACA”: π = [0, 0, 1, 2, 3, 0, 1] 2️⃣ Выполняем поиск: code Code i=0: text[0]=‘A’, pattern[0]=‘A’ ✓, j=1 i=1: text[1]=‘B’, pattern[1]=‘B’ ✓, j=2
i=2: text[2]=‘A’, pattern[2]=‘A’ ✓, j=3 i=3: text[3]=‘B’, pattern[3]=‘B’ ✓, j=4 i=4: text[4]=‘A’, pattern[4]=‘A’ ✓, j=5 i=5: text[5]=‘B’, pattern[5]=‘C’ ✗ Откат: j = π[4] = 3 text[5]=‘B’, pattern[3]=‘B’ ✓, j=4 i=6: text[6]=‘A’, pattern[4]=‘A’ ✓, j=5 i=7: text[7]=‘C’, pattern[5]=‘C’ ✓, j=6
i=8: text[8]=‘A’, pattern[6]=‘A’ ✓, j=7 Найдено вхождение на позиции 8-7+1=2! [МЕДИА: image_03] Описание: Трассировка выполнения алгоритма KMP на конкретном примере Промпт: “algorithm trace visualization, KMP string matching step by step, text and pattern alignment, highlighting matches and mismatches, arrows showing jumps, educational style with clear annotations” Z-алгоритм: альтернативный подход Z-алгоритм вычисляет для каждой позиции i длину наибольшего префикса строки, который начинается в позиции i. Для строки “ABABAB”: Z = [6, 0, 4, 0, 2, 0] code Python def z_algorithm(s): n = len(s) z = [0] * n l, r = 0, 0

for i in range(1, n):
    if i <= r:
        z[i] = min(r - i + 1, z[i - l])

    while i + z[i] < n and s[z[i]] == s[i + z[i]]:
        z[i] += 1

    if i + z[i] - 1 > r:
        l, r = i, i + z[i] - 1

return z

🎮 Практика Базовый уровень 🟢 Задание 1: Вычисли префикс-функцию для строки “ABCAB”

Z[i] - длина общего префикса с s[i:]

π[i] - длина border’а для s[0:i+1]

✅ Правильно: Это разные структуры данных для разных задач! 💡 Почему: Z-алгоритм лучше для некоторых задач, KMP - для поиска подстрок 🎓 Главное запомнить ✅ KMP избегает лишних сравнений, используя префикс-функцию ✅ Временная сложность: O(n + m) вместо O(nm) ✅ Применяется везде: от Ctrl+F до анализа ДНК 🔗 Связь с другими темами Предыдущий урок (273): Базовые алгоритмы на строках заложили фундамент Хэширование: Rolling hash - другой подход к быстрому поиску Автоматы: KMP можно представить как конечный автомат Суффиксные структуры: Более мощные инструменты для сложных задач