Реализация алгоритма Рабина-Карпа поиска в строках

Abstract

Объектом исследования является задача поиска подстроки в строке. Предметом исследования являются методы и алгоритмы поиска подстроки, а также способы их распараллеливания на примере алгоритма Рабина – Карпа. Целью выпускной квалификационной работы является разработка параллельной программной реализации алгоритма Рабина – Карпа поиска в строках. В работе рассмотрена задача поиска подстроки в строке, выполнен обзор существующих алгоритмов её решения (прямой алгоритм, Кнута – Морриса – Пратта, Бойера – Мура) и выбран алгоритм Рабина – Карпа в качестве основы для разработки. Проведён анализ возможностей распараллеливания данного алгоритма и разработана параллельная версия, в которой множество стартовых позиций проверяемых подстрок распределяется между несколькими потоками. Программная реализация последовательной и параллельной версий алгоритма выполнена на языке C++ с применением технологии OpenMP. Для проверки корректности работы программы проведено функциональное тестирование, включая обработку граничных случае