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

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

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

Здесь объясняется, как префикс-функция образца помогает не начинать сравнение заново после каждого несовпадения. Раздел раскрывает принцип вычисления этой функции, переходы между состояниями и поиск всех вхождений. Приводятся оценка времени O(n+m), требования к памяти и пример, показывающий повторное использование уже проверенной информации.

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

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

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

Раздел содержит таблицы или графики эксперимента и объяснение полученных различий. Результаты сопоставляются с теоретическими оценками, но не трактуются как универсальные: скорость зависит от данных и реализации. Обсуждаются случаи, в которых простой поиск достаточен, а предварительная обработка КМП или сдвиги Бойера — Мура дают преимущество.

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

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