Опубликовано: 27.09.2017
Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он был разработан в году Майклом Рабином и Ричардом Карпом. Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов.
Для текста длины n и шаблона длины m , его среднее время исполнения и лучшее время исполнения это O n , но в весьма нежелательном худшем случае он имеет производительность O nm , что является одной из причин того, почему он не слишком широко используется. Однако, алгоритм имеет уникальную особенность находить любую из k строк менее, чем за время O n в среднем, независимо от размера k. Одно из простейших практических применений алгоритма Рабина — Карпа состоит в определении плагиата.
Скажем, например, что студент пишет работу по Моби Дику. Коварный профессор находит различные исходные материалы по Моби Дику и автоматически извлекает список предложений в этих материалах. Затем, алгоритм Рабина — Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для устранения чувствительности алгоритма к небольшим различиям, можно игнорировать детали, такие как регистр или пунктуация при помощи их удаления. Поскольку количество строк, которые мы ищем, k , очень большое, обычные алгоритмы поиска одиночных строк становятся неэффективными.
Основной проблемой алгоритма является нахождение постоянной строки длины m , называемой образцом , в тексте длины n ; например, нахождение строки "sun" в предложении "Hello sunshine in this vale of tears". Один из простейших алгоритмов для этой задачи просто ищет подстроку во всех возможных местах:. Этот алгоритм хорошо работает во многих практических случаях, но совершенно не эффективен например на поиске строки из "a", за которыми следует "b" в строке из 10 миллионов букв "a".