Курсовая работа: Алгоритмы поиска подстроки в строке
· выявить эффективные, с точки зрения времени выполнения, алгоритмы.
Работа содержит две основных части. В первой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй части работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме.
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке.
1.1. Основные понятия.
1.1.1 Строка, её длина, подстрока.
Здесь мы приводим ряд определений, которые будем использовать в изложении материала [5, 11].
Определение 1 . Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.
Определение 2 . Длина строки – количество знаков в строке.
Слова будем обозначать буквами латинского алфавита, напр. X=x[1]x[2]…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)=
=n – обозначение длины строки.
Определение 3 . Слово не содержащее ни одной буквы называется пустым.
Пустое слово обычно обозначают буквой L. Length(L)=0.
Определение 4 . Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.
Пример : слово ab является префиксом слова abcfa.
Определение 5 . Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя.
Пример : слово bfg является суффиксом слова vsenfbfg.
Определение 6 .Слово X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2 , что Y=Z1 XZ2 . При этом Z1 называют левым, а Z2 - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение X
Y.
Пример : слова hrf и fhr является подстроками слова abhrfhr, gfsfdgfro.
1.1.2. Понятие о сложности алгоритма.
Целью нашей работы является найти эффективный алгоритм, однако ничего пока не было сказано о методе оценки алгоритмов.
Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой. [11, с. 38-40]
В данной работе будут рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Мы не будем обсуждать логическую сложность разработки алгоритма - сколько «человеко-дней» нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики.
Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством переменных, элементов массивов, элементов записей или просто количеством байт [6, 7, 10, 11].
Эффективность алгоритма также будет оцениваться с помощью подсчета времени выполнения алгоритмом конкретно поставленной задачи, т.е. с помощью эксперимента, подробнее об этом в части 2 данной работы.
1.2. Алгоритмы основанные на методе последовательного поиска.
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm).
Самый очевидный алгоритм. Обозначим S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующая позиция (Листинг 1). [1, 2]
|
|