Алгоритм Рабина-Карпа: эффективный поиск подстроки в строке

Алгоритм Рабина-Карпа - это один из эффективных алгоритмов поиска подстроки в строке, который сочетает в себе идеи хэширования и проверки на совпадение. Он был разработан Майклом Рабином и Ричардом Карпом в 1987 году.

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

Преимущество алгоритма Рабина-Карпа заключается в том, что он имеет линейную сложность (O(n + m)), где n - длина строки, m - длина искомой подстроки. Также алгоритм хорошо справляется с поиском нескольких подстрок в строке.

Применение алгоритма Рабина-Карпа требует определения хэш-функции для строк. Хэш-функция должна быть быстрой и иметь малую вероятность коллизий (совпадений) для различных строк. Одним из примеров хэш-функции, которая обычно используется в алгоритме Рабина-Карпа, является хэш-функция на основе полиномиального хэширования. Эта хэш-функция вычисляет хэш строки s следующим образом:

def polynomial_hash(s, p, x):
    """
    Функция для вычисления хэша строки s на основе полиномиального хэширования.
    p - простое число (желательно большое)
    x - некоторое число от 1 до p-1
    """
    h = 0
    for i in range(len(s)):
        h = (h + ord(s[i]) * (x ** i)) % p
    return h

В этой функции используется ASCII-код символов строки s для вычисления хэша. Параметр p - это простое число, желательно выбрать его как можно больше, чтобы уменьшить вероятность коллизий. Параметр x - это число от 1 до p-1, которое также влияет на хэш.

Теперь, когда у нас есть хэш-функция, мы можем реализовать сам алгоритм Рабина-Карпа. Вот пример реализации на языке Python:

def rabin_karp_search(pattern, text):
    """
    Функция для поиска подстроки pattern в строке text с помощью алгоритма Рабина-Карпа.
    """
    p = 31  # простое число для хэширования
    x = 53  # число от 1 до p-1
    pattern_hash = polynomial_hash(pattern, p, x)
    n = len(pattern)
    m = len(text)
    hashes = []
    for i in range(m - n + 1):
        substring = text[i:i + n]
        hash_value = polynomial_hash(substring, p, x)
        if hash_value == pattern_hash and substring == pattern:
            return True, i
        hashes.append(hash_value)
    for i in range(1, n):
        pattern_hash = (pattern_hash - ord(pattern[i - 1])) / x + ord(pattern[i + n - 1]) * (x ** (n - 1))
        for j in range(m - n + 1):
            hash_value = hashes[j]
            if hash_value == pattern_hash and text[j:j + n] == pattern:
                return True, j
            hashes[j] = (hash_value - ord(text[j]) * (x ** (n - 1))) / x + ord(text[j + n])
    return False, -1

В этой реализации функция `rabin_karp_search` принимает две строки - `pattern` (искомая подстрока) и `text` (строка, в которой ведется поиск). Алгоритм вычисляет хэш искомой подстроки и сравнивает его со значениями хэшей всех подстрок строки. Если значения хэшей совпадают, алгоритм также проверяет, что сама подстрока соответствует искомой. Если совпадение найдено, функция возвращает `True` и индекс первого вхождения искомой подстроки в строку. Если совпадения не найдено, функция возвращает `False` и `-1`.

Алгоритм Рабина-Карпа - это мощный инструмент для поиска подстроки в строке, особенно когда требуется искать несколько подстрок. Он может быть использован во многих приложениях, таких как текстовый редактор, поиск файлов, обработка языка и многое другое.