Сравнение алгоритмов поиска подстроки: наивный, Кнута-Морриса-Пратта и Бойера-Мура

Теоретическая база и предельные случаи алгоритмов

Разбор начинается с механики каждого метода, работы указателей и сохранения информации о прочитанных символах. Наивный алгоритм при первом же несовпадении сдвигает шаблон вправо на одну позицию и возобновляет посимвольное сравнение с начала образца. В худшем сценарии это приводит к временной сложности порядка O(N * M), где N обозначает длину текста, а M — длину искомого шаблона. Алгоритм Кнута-Морриса-Пратта предварительно строит массив длин наибольших совпадающих собственных префиксов и суффиксов, что исключает возврат назад по основному тексту и гарантирует строго линейное время O(N + M). В алгоритме Бойера-Мура посимвольное сравнение ведется справа налево, что позволяет при обнаружении несовпадения совершать длинные прыжки вперед по тексту на основе эвристики плохого символа и эвристики хорошего суффикса. В теоретической части проекта требуется аккуратно вывести формулы временной сложности для лучшего, среднего и худшего случаев каждого метода, а также указать затраты дополнительной памяти на хранение вспомогательных таблиц сдвигов.

Подготовка тестовых наборов данных

Для получения достоверных результатов тестирование необходимо проводить на контрастных наборах входных данных. Поведение алгоритмов напрямую зависит от размера алфавита и частоты повторяемости символов.

• Скачай цельную художественную книгу на русском или английском языке размером от двух до десяти мегабайт из электронной библиотеки вроде Project Gutenberg для имитации поиска по естественному языку с широким алфавитом.
• Сгенерируй синтетический текст из нескольких сотен тысяч одинаковых символов с искомым фрагментом в самом конце файла для воспроизведения худшего теоретического случая наивного перебора.
• Подготовь реальную последовательность ДНК из открытых биологических баз данных с алфавитом ровно из четырех символов A, C, G, T, где совпадения префиксов происходят непрерывно.
• Составь список поисковых запросов разной протяженности, от коротких трехбуквенных приставок до развернутых цитат длиной более пятидесяти символов, для фиксации зависимости скорости от размера искомого образца.

Методика экспериментальных замеров

Главное требование к физическому эксперименту — изоляция чистого алгоритмического времени от сторонних системных факторов. Считывание текстовых файлов с накопителя, парсинг аргументов командной строки и вывод найденных индексов на экран должны происходить строго за пределами замеряемого блока. Для фиксации временных интервалов подходят только монотонные системные таймеры высокого разрешения, такие как функция perf_counter в стандартном модуле time языка Python или std::chrono::steady_clock в языке C++. Каждый запуск по конкретному шаблону следует повторять от тридцати до ста раз в цикле. После серии прогонов необходимо программно отсекать аномальные значения, вызванные переключением контекста операционной системы, и вычислять медианное время работы.

Критерии оценки проекта преподавателем

При проверке работы преподаватель информатики оценивает математическую выверенность выводов и чистоту исходного кода. В тексте программ должны быть реализованы собственные функции предварительной обработки шаблонов без скрытого обращения к штатным библиотечным методам вроде find или strstr. В исследовательской части оценивается наличие сводных таблиц и наглядных графиков зависимости времени поиска от длины текста и длины шаблона. Преподаватель ожидает увидеть подробное объяснение причин, по которым Бойер-Мур многократно выигрывает на естественных текстах с длинными шаблонами, но теряет преимущество на узких алфавитах с короткими запросами.