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

Новости

Где купить гибкий штатив для фотоаппарата

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

Где выбрать дверную ручку
Приступая к ремонту своей квартиры или офиса, мы задумываемся прежде всего о глобальных вопросах. О том, как будут выглядеть стены, потолок, какие обои или покрытие для пола выбрать. Немаловажную роль

Битбокс обучение на русском языке видео
Вы знаете что такое битбокс? А ведь им может заниматься кто угодно и даже вы. Единственное, что вам для этого понадобиться это ваш рот, ну и микрофон тоже не будет лишним. Первыми битбоксерами были французские

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

Профессиональные бизнес тренинги
Тысяча долларов прибыли в день на человека? Неплохая рентабельность. Примерно такими соображениями руководствуются те, кто открывает свои тренинговые компании. Однако большинство тренинговых компаний

Форум про биткоин
Bitcoin, самая популярная цифровая валюта, продолжает интриговать обывателей. На волне роста стоимости этой валюты многие пытаются выяснить, как добывать Bitcoin (майнинг биткоинов) и стоит ли вообще

Эст тренинг видео
Девушки, у кого из вас не возникало недовольства своими волосами? То секутся, то лезут, то каждое утро жирнеют, как на ночь наевшись. Сколько средств было использовано: и бабушкины, и дедушкины, и ультрамодные

Видеоуроки по основным предметам школьной
ВИДЕОУРОКИ по предметам школьной программы. Бесплатно и без рекламы. • Интернет-урок - http://interneturok.ru — видеоуроки по основным школьным предметам за 1-11 классы в открытом доступе.

Массаж простаты видеоурок
Вместе с врачом можно определить границы ощущений, понять, какие чувства говорят о том, что массаж нужно прекращать, а какие вполне допустимы во время процесса. Еще специалист подскажет, какими инструментами

Тренинги по продажам
Для чего нужны тренинги по продажам Профессиональные продажи предполагают комплексный подход – с ощущением безопасности, комфорта и удобства сотрудничестве, с уверенностью клиента в прибыли и актуальности

*/?>



Сделано в Сибири

Все тренинги 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