Рубрики
Без рубрики

Алгоритм Rabin-Karp в Python

[Простое руководство] Узнайте, как в Python реализован алгоритм Rabin-Karp, чтобы найти узоры в строках.

Автор оригинала: Chris.

Алгоритм Rabin-Karb решает Проблема поиска строки Отказ Он был предложен Ричардом Карпом и Майклом Рабиным в 1987 году. Оба создателя получили самую высокую награду в области информатики: Thuring Award!

Алгоритм более эффективен, чем тривиальное решение проверки всех последовательных подстроек в исходной строке.

Во-первых, взгляните на реализацию алгоритма Rabin-Karp в Python:

def RabinKarp(string, pattern):
    n, m = len(string), len(pattern)
    hpattern = hash(pattern);
    for i in range(n-m+1):
        hs = hash(string[i:i+m])
        if hs == hpattern:
            if string[i:i+m] == pattern:
                return i
    return -1


s1 = "Ronaldo is better than Messi"

print(RabinKarp(s1, "Ronaldo"))
# 0

print(RabinKarp(s1, "Football"))
# -1

print(RabinKarp(s1, "Messi"))
# 23

Я использовал Алгоритм псевдокода из статьи Википедии Для создания версии Python предоставляется в этой статье.

Там большой тело литературы относительно эффективного поиска строк.

В Python вы можете найти строку S1 для подстроки S2, просто используя выражение S2 в S1 Отказ Однако это не говорит о том, как это на самом деле работает.

Как работает алгоритм?

Наивный алгоритм поиска строки просто итерации по всем показателям строки S1. Затем он пытается сопоставить все символы строки S2. Если это не удается, он продолжается с следующим индексом. Тем не менее, этот алгоритм имеет O (Len (S1) * Len (S2)) ухудшение сложности времени.

Алгоритм Rabin-Karb более эффективен. Улучшение происходит от использования нарезки для доступа к подстроке, начиная с индекса I и сравниваем значения хеша вместо самих подстроек. Это более эффективно, потому что расчетное значение хеша намного быстрее, чем проверка равенства двух строк. Однако две разные строки могут привести к тому же хеш-значению. Следовательно, алгоритм Rabin-Karb должен обязательно исключить этот случай.

Работая в качестве исследователя в распределенных системах, доктор Кристиан Майер нашел свою любовь к учению студентов компьютерных наук.

Чтобы помочь студентам достичь более высоких уровней успеха Python, он основал сайт программирования образования Finxter.com Отказ Он автор популярной книги программирования Python One-listers (Nostarch 2020), Coauthor of Кофе-брейк Python Серия самооставленных книг, энтузиаста компьютерных наук, Фрилансера и владелец одного из лучших 10 крупнейших Питон блоги по всему миру.

Его страсти пишут, чтение и кодирование. Но его величайшая страсть состоит в том, чтобы служить стремлению кодер через Finxter и помогать им повысить свои навыки. Вы можете присоединиться к его бесплатной академии электронной почты здесь.