Целью работы является повышение навыков разработки широкоизвестных алгоритмов.
Предпологается, во время выполнения данной работы студенту придется много взаимодействовать с отладчиком, что повысит уровень владения этим инструментом.
Для эффективной реализации алгоритмов придется использовать профайлер.
После выполнения работы студент должен понимать разные алгоритмы поиска подстроки, уметь их реализовывать, уверенно владеть отладчиком, получить базовые навыки работы с отладчиком и понимать принцип сравнения производительности кода.
- Реализуйте поиск подстроки в строке.
size_t str_find(const std::string& str, const std::string& substr);- Реализуйте поиск подстроки в строке алгоритмом Рабина—Карпа.
size_t rk_find(const std::string& str, const std::string& substr);- Реализуйте поиск подстроки в строке алгоритмом Кнута—Морриса—Пратта.
size_t kmp_find(const std::string& str, const std::string& substr);- Сравните производительность всех реализованных алгоритмов поиска и метода
std::string::find. Составьте отчет. Отчет должен включать в себя:- описание алгоритмов;
- блок схемы алгоритмов;
- зависимость времени работы алгоритмов от данных;
- вывод.
5*. Задание со звездочкой. Наивная реализация алгоритмов вряд ли будет эффективной. Для улучшения скорости работы вашего кода используйте профайлер, чтобы найти тонкие места реализации алгоритмов. После проведенного профайлинга модифицируйте код для улучшения производительности.