Алгоритм Кнута-Морриса-Пратта (KMP)

Введение и мотивация

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

Наивный подход к решению этой задачи имеет временную сложность O(n×m), где n — длина текста, m — длина образца. Однако в 1977 году Дональд Кнут, Джеймс Моррис и Воган Пратт предложили алгоритм, который выполняет поиск за O(n+m), существенно ускоряя процесс для больших текстов.

Алгоритм Кнута-Морриса-Пратта (KMP) — это один из первых линейных алгоритмов поиска подстрок, который использует информацию о совпадающих префиксах и суффиксах для оптимизации процесса поиска.

Ключевая идея алгоритма

Основное преимущество KMP перед наивным подходом заключается в том, что алгоритм никогда не возвращается назад в тексте, а использует знания о структуре образца для "умных" сдвигов.

Когда происходит несовпадение при сравнении текста и образца, наивный алгоритм начинает сравнение заново со следующей позиции в тексте. KMP же использует префикс-функцию образца, чтобы определить, насколько можно сдвинуть образец, не возвращаясь назад в тексте.

Интуитивное понимание

Представьте, что вы ищете слово "ABABAC" в тексте и обнаружили, что первые 5 символов совпадают, но шестой символ не совпадает. В наивном подходе вы бы сдвинули образец на одну позицию вправо и начали сравнение заново.

Однако KMP замечает, что префикс "ABA" образца совпадает с его суффиксом, и сдвигает образец так, чтобы этот суффикс совпал с уже проверенными символами в тексте. Это позволяет избежать повторной проверки символов, которые мы уже знаем, что они совпадают.

Префикс-функция: основа алгоритма KMP

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

Определение префикс-функции

Для строки s длины m, префикс-функция π — это массив длины m, где:

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

Собственный префикс — это любой префикс строки, кроме самой строки.

Пример построения префикс-функции

Рассмотрим образец P = "ABABAC".

1. π[0] = 0 (у первого символа нет собственных префиксов)
2. π[1] = 0 (у "AB" нет собственного префикса, который является суффиксом)
3. π[2] = 1 (у "ABA" префикс "A" совпадает с суффиксом "A")
4. π[3] = 2 (у "ABAB" префикс "AB" совпадает с суффиксом "AB")
5. π[4] = 3 (у "ABABA" префикс "ABA" совпадает с суффиксом "ABA")
6. π[5] = 0 (у "ABABAC" нет собственного префикса, который является суффиксом)

Получаем π = [0, 0, 1, 2, 3, 0].

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Реализация расчета префикс-функции на Python

def compute_prefix_function(pattern):
    m = len(pattern)
    pi = [0] * m  # Инициализируем массив префикс-функции
    
    # Для i=0 значение уже установлено как 0
    k = 0  # Длина текущего наибольшего префикс-суффикса
    
    for i in range(1, m):
        # Если текущий символ не продолжает наибольший префикс-суффикс
        while k > 0 and pattern[k] != pattern[i]:
            k = pi[k-1]  # Откат к предыдущему префикс-суффиксу
        
        # Если текущий символ продолжает наибольший префикс-суффикс
        if pattern[k] == pattern[i]:
            k += 1  # Увеличиваем длину наибольшего префикс-суффикса
        
        pi[i] = k  # Записываем результат
    
    return pi

Объяснение алгоритма расчета префикс-функции

1. Инициализируем массив π размера m и устанавливаем π[0] = 0.
2. Используем две переменные: i (текущая позиция в строке) и k (длина текущего наибольшего префикс-суффикса).
3. Для каждой позиции i от 1 до m-1: a. Если pattern[i] не совпадает с pattern[k], мы откатываемся к предыдущему префикс-суффиксу, используя π[k-1]. b. Если pattern[i] совпадает с pattern[k], увеличиваем k на 1. c. Записываем π[i] = k.

Временная сложность расчета префикс-функции — O(m), где m — длина образца.

Полная реализация алгоритма KMP на Python

Теперь, когда мы понимаем префикс-функцию, можем реализовать полный алгоритм KMP:

def kmp_search(text, pattern):
    if not pattern:
        return 0  # Пустой образец всегда найден в начале строки
    
    n = len(text)
    m = len(pattern)
    
    # Если образец длиннее текста, он не может быть найден
    if m > n:
        return -1
    
    # Вычисляем префикс-функцию для образца
    pi = compute_prefix_function(pattern)
    
    # Ищем образец в тексте
    j = 0  # Указатель на текущую позицию в образце
    
    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:
            return i - m + 1  # Возвращаем индекс начала найденного образца
    
    return -1  # Образец не найден

# Вспомогательная функция для расчета префикс-функции
def compute_prefix_function(pattern):
    m = len(pattern)
    pi = [0] * m
    
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[k] != pattern[i]:
            k = pi[k-1]
        
        if pattern[k] == pattern[i]:
            k += 1
        
        pi[i] = k
    
    return pi

Пример использования:

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"

position = kmp_search(text, pattern)
if position != -1:
    print(f"Образец найден в позиции {position}")
else:
    print("Образец не найден")

Результат:

Образец найден в позиции 10

Модификация для поиска всех вхождений

Иногда нам нужно найти все вхождения образца в текст. Модифицируем алгоритм:

def kmp_search_all(text, pattern):
    if not pattern:
        return [0]  # Пустой образец всегда найден в начале строки
    
    n = len(text)
    m = len(pattern)
    
    # Если образец длиннее текста, он не может быть найден
    if m > n:
        return []
    
    # Вычисляем префикс-функцию для образца
    pi = compute_prefix_function(pattern)
    
    positions = []  # Список для хранения всех позиций вхождений
    j = 0  # Указатель на текущую позицию в образце
    
    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:
            positions.append(i - m + 1)  # Добавляем индекс начала образца
            j = pi[m-1]  # Продолжаем поиск с учетом префикс-функции
    
    return positions

Пример использования:

text = "ABABCABABABABCABAB"
pattern = "ABAB"

positions = kmp_search_all(text, pattern)
if positions:
    print(f"Образец найден в позициях: {positions}")
else:
    print("Образец не найден")

Результат:

Образец найден в позициях: [0, 6, 8, 14]

Сравнение с наивным алгоритмом

Для полноты картины, давайте сравним KMP с наивным алгоритмом поиска подстрок:

def naive_search(text, pattern):
    n = len(text)
    m = len(pattern)
    
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        
        if j == m:
            return i  # Образец найден
    
    return -1  # Образец не найден

Эффективность алгоритмов

Давайте сравним время выполнения на синтетическом примере:

import time

def benchmark(search_func, text, pattern, iterations=100):
    start_time = time.time()
    
    for _ in range(iterations):
        search_func(text, pattern)
    
    end_time = time.time()
    return end_time - start_time

# Создаем текст, который вызовет наихудший случай для наивного алгоритма
text = "A" * 10000 + "B"
pattern = "A" * 500 + "B"

naive_time = benchmark(naive_search, text, pattern)
kmp_time = benchmark(kmp_search, text, pattern)

print(f"Наивный алгоритм: {naive_time:.6f} секунд")
print(f"Алгоритм KMP: {kmp_time:.6f} секунд")
print(f"KMP быстрее в {naive_time / kmp_time:.2f} раз")

Результаты могут варьироваться в зависимости от системы, но в целом KMP должен быть значительно быстрее на таких примерах.

Применения алгоритма KMP

Алгоритм KMP находит применение во многих областях:

1. Текстовые редакторы: Для функции "найти и заменить"
2. Системы обработки естественного языка: Для анализа текстов
3. Биоинформатика: Для поиска последовательностей ДНК и белков
4. Информационная безопасность: Для обнаружения сигнатур вредоносного ПО
5. Поисковые системы: Для индексации и поиска документов

Практические задачи для закрепления

Задача 1: Подсчет вхождений образца

Напишите функцию, которая подсчитывает количество вхождений образца в текст с использованием KMP.

def count_pattern_occurrences(text, pattern):
    positions = kmp_search_all(text, pattern)
    return len(positions)

# Пример
text = "ABABABABABA"
pattern = "ABA"
print(f"Количество вхождений: {count_pattern_occurrences(text, pattern)}")

Задача 2: Циклические сдвиги

Определите, является ли одна строка циклическим сдвигом другой, используя алгоритм KMP.

def is_rotated(s1, s2):
    if len(s1) != len(s2):
        return False
    
    # Удваиваем первую строку и ищем вторую строку в удвоенной
    return kmp_search(s1 + s1, s2) != -1

# Примеры
print(is_rotated("ABCD", "CDAB"))  # True
print(is_rotated("ABCD", "ACBD"))  # False

Задача 3: Самый длинный повторяющийся подстроки

Найдите самую длинную подстроку, которая встречается в строке хотя бы дважды.

def longest_repeated_substring(s):
    n = len(s)
    best_start = 0
    best_length = 0
    
    for length in range(1, n // 2 + 1):
        for start in range(n - 2 * length + 1):
            pattern = s[start:start + length]
            # Ищем образец в оставшейся части строки
            if kmp_search(s[start + 1:], pattern) != -1:
                if length > best_length:
                    best_length = length
                    best_start = start
    
    if best_length == 0:
        return ""
    
    return s[best_start:best_start + best_length]

# Пример
print(longest_repeated_substring("ABABABA"))  # "ABABA"

Заключение

Алгоритм Кнута-Морриса-Пратта — один из элегантных алгоритмов строковой обработки, который демонстрирует, как эффективное использование предварительных вычислений и структуры данных может значительно улучшить производительность.

Основные преимущества KMP:

• Линейное время работы O(n+m)
• Отсутствие возвратов при сканировании текста
• Эффективность на больших текстах и образцах

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