PYTHON АЛГОРИТМ РАБИНА КАРПА

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

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

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

def rabin_karp(text, pattern):    n, m = len(text), len(pattern)    if n < m:        return -1    hpattern, htext, d, q = 0, 0, 256, 101    for i in range(m):        hpattern = (d * hpattern + ord(pattern[i])) % q        htext = (d * htext + ord(text[i])) % q    dm = pow(d, m - 1) % q    for i in range(n - m + 1):        if hpattern == htext:            for j in range(m):                if text[i + j] != pattern[j]:                    break            if j == m - 1:                return i        if i < n - m:            htext = (d * (htext - ord(text[i]) * dm) + ord(text[i + m])) % q    return -1

Этот код реализует алгоритм Рабина-Карпа для поиска подстроки в строке.

Лекція 16. Алгоритм пошуку в тексті. Алгоритм Рабина-Карпа

Лучшая книга про алгоритмы для начинающих. Грокаем алгоритмы.

Алгоритмы и структуры данных 5. Хеширование строк. Алгоритм Рабин-Карпа

Собеседование C# Junior developer, что спрашивают в 2021 году?! Техподдержка идет программировать.

Алгоритмы на Python 3. Лекция №11

Алгоритмы и структуры данных(Алгоритм Рабина-Карпа,Бор,алгоритм Ахо-Корасик), Мацкевич С.Е. 25.04.22

Алгоритм Рабина-Карпа. Создаем умный поиск информации (Ctrl + F).

BLGPG-B51FF35AFD3D-24-09-19-20

Новые материалы: