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

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

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

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

От состояния и здоровья зубов в жизни человека зависит очень многое. Это не только настроение и отсутствие болей, но и здоровье всех остальных систем, обеспечивающих жизнедеятельности организма. Естественно, стоимость лечения зубов не имеет значения, когда речь идет о таких важных вещах. Поэтому, перейдя по ссылке http://xn----9sbbolkn1e8c.xn--p1ai/price/ и обнаружив цены на лечение зубов в Новосибирске, вы не расстроитесь, особенно, если вас при этом мучают невыносимые зубные боли.

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

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

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

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

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

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

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

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

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