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"
<details>
<summary>💡 Подсказка</summary>
Иди символ за символом, ищи совпадающие префиксы и суффиксы
</details>
<details>
<summary>✅ Ответ</summary>
π = [0, 0, 0, 1, 2]
- "A": нет собственных префиксов → 0
- "AB": нет совпадений → 0
- "ABC": нет совпадений → 0
- "ABCA": префикс "A" = суффикс "A" → 1
- "ABCAB": префикс "AB" = суффикс "AB" → 2
</details>
Задание 2: Найди все вхождения "ABA" в "ABABABABA" наивным алгоритмом
Задание 3: Сколько сравнений символов сделает KMP для поиска "AAAA" в строке "AAAAAAAAB"?
Продвинутый уровень 🟡
Задание 4: Модифицируй KMP для поиска всех циклических сдвигов строки
Задание 5: Реализуй алгоритм Ахо-Корасик для поиска множества паттернов
Задание 6: Используя Z-алгоритм, найди все палиндромы в строке за O(n²)
Челлендж 🔴
Задание 7: Найди наименьший период строки, используя префикс-функцию
Задание 8: Подсчитай количество различных подстрок строки за O(n²) с помощью суффиксного массива
⚠️ Частые ошибки
❌ Ошибка: Забываем обновлять j после нахождения паттерна
code
Python
if j == m:
    matches.append(i - m + 1)  
    # j = pi[j - 1]  ← ЗАБЫЛИ!
✅ Правильно: Всегда откатываемся для поиска перекрывающихся вхождений
💡 Почему: Паттерн может встречаться с перекрытием (например, "AA" в "AAA")
❌ Ошибка: Неправильно вычисляем префикс-функцию для первого элемента
code
Python
pi[0] = 1  # НЕПРАВИЛЬНО!
✅ Правильно: π[0] всегда равно 0 по определению
💡 Почему: У одного символа нет собственных префиксов
❌ Ошибка: Путаем Z-функцию и префикс-функцию
code
Python
# Z[i] - длина общего префикса с s[i:]
# π[i] - длина border'а для s[0:i+1]
✅ Правильно: Это разные структуры данных для разных задач!
💡 Почему: Z-алгоритм лучше для некоторых задач, KMP - для поиска подстрок
🎓 Главное запомнить
✅ KMP избегает лишних сравнений, используя префикс-функцию
✅ Временная сложность: O(n + m) вместо O(nm)
✅ Применяется везде: от Ctrl+F до анализа ДНК
🔗 Связь с другими темами
Предыдущий урок (273): Базовые алгоритмы на строках заложили фундамент
Хэширование: Rolling hash - другой подход к быстрому поиску
Автоматы: KMP можно представить как конечный автомат
Суффиксные структуры: Более мощные инструменты для сложных задач