По-другому
Санкт-Петербург Тюмень Казань Томск Южно-сахалинск

Все тренинги on-line

Реализация алгоритма Рабина-Карпа на C++

Опубликовано: 06.10.2017

Приветствую вас, друзья мои! Сейчас я расскажу о своей первой курсовой работе, которая была написана и сдана на далеком втором курсе. Суть заключается в реализации и тестировании алгоритма Рабина-Карпа поиска подстроки в строке, в качестве языка программирования мне был рекомендован C++. В принципе больше во вступлении добавить нечего, перейдем сразу к делу.

Суть алгоритма Рабина-Карпа

Алгоритм представляет из себя улучшенную версию последовательного поиска, улучшение заключается в использовании хэш-функции. Это объясняется тем, что сравнить два числа(два хэша) гораздо быстрее и дешевле, чем сравнивать подстроки посимвольно. Сравнивать подстроки придется только один раз, когда хэши совпали, сделать это придется для увеличения надежности и защиты от случая коллизии хэша.

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

Формула хэша подстроки

H = C 1 ­­h k-1 + C 2 h k-2 + … + C k h 0

где C1 … Ck входные символы, h константа. Удаление символов из подстроки и добавление новых производится путем вычитания последнего члена формулы и добавлением первого соответственно.

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



rss