Введение Цель курсовой работы: Изучить и проанализировать алгоритмы поиска подстроки в строке, и рассмотреть ряд практических задач на данную тематику.
Задачи курсовой работы: изучить задачи связанные с проблемой поиска подстроки в строке, дать основные определения; рассмотреть применение различных алгоритмов поиска подстроки в строке на практике; написать программный код, реализующий один из алгоритмов поиска подстроки в строке.
Тема моей курсовой работы является актуальной и на сегодняшний день, те, кому приходиться часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если разрабатывать подобную программу, пользователь вправе ожидать, что в его распоряжении будут соответствующие команды.
Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня, поэтому чтобы найти строчку в небольшом тексте используется встроенная функция. Но если такого рода поиск является ключевой задачей программы, знать принципы организации функций поиска будет полезным. В готовых подпрограммах далеко не всегда все написано лучшим образом. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html. Работа простейшего спам–фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Это всё говорит об актуальности проблемы поиска.
Работа содержит три основных главы. В первой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй главе будет рассмотрена практическая часть курсовой работы. Реализован программный код поиска подстроки в строке при помощи алгоритма последовательного поиска. В третьей главе работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме.
Глава 1. Теоретические сведения об алгоритмах поиска подстроки в строке 1.1. Основные понятия
Определение. Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.
Определение . Длина строки – количество знаков в строке.
Слова обозначаются буквами латинского алфавита, напр. X=x[1]x[2]…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)==n – обозначение длины строки.
Определение . Слово не содержащее ни одной буквы называется пустым.
Пустое слово обычно обозначается буквой L. Length(L)=0.
Определение . Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. ............
