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

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

Пример кода на языке Python:

def rabin_karp_search(text: str, pattern: str) -> list:
    """
       Функция находит все вхождения подстроки (pattern) в текст (text)
       с использованием алгоритма Рабина-Карпа.
       
       Аргументы:
       text: str - текст, в котором ищем подстроку
       pattern: str - подстрока, которую ищем
       
       Возвращает:
       list - список индексов, где найдена подстрока
    """
    len_text = len(text) # длина текста
    len_pattern = len(pattern) # длина подстроки
    hash_pattern = hash(pattern) # вычисляем хэш подстроки
    hash_text = hash(text[0:len_pattern]) # вычисляем хэш первого "окна"
    res = [] # список для хранения индексов вхождений подстроки
    for i in range(len_text - len_pattern + 1): # проходимся по всем "окнам"
        if hash_pattern == hash_text: # если хэш совпадает, то проверяем подстроку
            if text[i:i+len_pattern] == pattern: # если подстрока найдена, то добавляем индекс в список
                res.append(i)
        if i < len_text - len_pattern: # если не выходим за пределы текста
            hash_text = hash_text - ord(text[i]) + ord(text[i+len_pattern]) # вычисляем новый хэш
    return res

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

text = "абвгдеабвгдеабвгде"
pattern = "де"
res = rabin_karp_search(text, pattern)
print(res)

Результат:

[3, 9, 15]

Алгоритм Рабина-Карпа имеет сложность O(n+m), где n - длина текста, а m - длина подстроки. Он достаточно быстр, особенно, когда нужно находить много вхождений одной подстроки в текст. Недостаток алгоритма заключается в том, что хэш-функции могут давать коллизии (то есть разные подстроки могут иметь одинаковый хэш), что может приводить к неправильным результатам.