Курсовая работа на тему: Теоретические сведения об алгоритмах поиска подстроки в строке

Введение

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

Оглавление

- Введение.

- Теоретические сведения об алгоритмах поиска подстроки в строке.

- Основные понятия.

- Строка, её длина, подстрока.

- Понятие о сложности алгоритма.

- Алгоритмы основанные на методе последовательного поиска.

- Алгоритм последовательного прямого поиска Тhе Вrutе Fоrсе Аlgоrithm.

- Алгоритм Рабина.

- Алгоритм Кнута - Морриса - Пратта КМП.

- Алгоритм Бойера Мура и некоторые его модификации.

- Алгоритм Боейера Мура.

- Модификации БМ.

- Поиск подстрок с помощью конечного автомата.

- Структура автомата.

- Пример построения конечного автомата.

- Экспериментальный анализ алгоритмов.

- Суть эксперимента.

- Результаты и анализ эксперимента.

- Заключение.

- Библиографический список.

Заключение

Мы рассмотрели различные алгоритмы поиска подстроки в строке, сделали их анализ. Результаты можно представить в таблице (Табл. 4).

Список литературы

- ). Кurtz, St. Fundаmеntаl Аlgоrithms Fоr А Dесlаrаtivе Раttеrn Маtсhing Systеm Текст. - Вiеlеfеld:. UnivеrsitГ61t Вiеlеfеld, 1995. - 238 с.

- ). Lесrо, Т. Еxасt string mаtсhing аlgоrithms Электронный ресурс. Режим доступа.

- ). Ахметов И. Поиск подстрок с помощью конечных автоматов Текст: Курсовая работа.- С-П государственный университет информационных технологий, механики и оптики.

- ). Ахо, Альфред Структура данных и алгоритмы Текст. - М.: Издательский дом "Вильямс", 2000. - 384 с.

- ). Белоусов А. Дискретная математика Текст. - М.: Издательство МГТУ им. Н.Э. Баумана, 2001. - 744 с.

- ). Брайан, К. Практика программирования Текст.- СПб:. Невский диалект, 2001. - 381 с.

- ). Вирт, Н. Алгоритмы и структуры данных Текст.- М:. Мир, 1989. - 360 с.

- ). Гилл, Арт. Введение в теорию конечных автоматов Текст. - М., 1966. - 272 с.

- ). Глушаков С. Программирование Wеb - страниц Текст. - М.: ООО "Издательство АСТ", 2003. - 387 с.

- ). Кнут, Д. Искусство программирования на ЭВМ Текст: Том 3.