Содержание
Содержание.
Введение 3
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 5
1.1. Основные понятия. 5
1.1.1 Строка, её длина, подстрока. 5
1.1.2. Понятие о сложности алгоритма. 6
1.2. Алгоритмы основанные на методе последовательного поиска. 7
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm). 7
1.2.2. Алгоритм Рабина. 7
1.3. Алгоритм Кнута — Морриса — Пратта (КМП). 10
1.4. Алгоритм Бойера – Мура и некоторые его модификации. 13
1.4.1. Алгоритм Боейера – Мура. 13
1.4.2. Модификации БМ. 15
1.5. Поиск подстрок с помощью конечного автомата. 17
1.5.1. Структура автомата. 17
1.5.2. Пример построения конечного автомата 19
Часть 2. Экспериментальный анализ алгоритмов. 21
2.1. Суть эксперимента. 21
2.2. Результаты и анализ эксперимента. 22
Заключение. 24
Библиографический список. 25
Выдержка из текста
Содержание.
Введение 3
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 5
1.1. Основные понятия. 5
1.1.1 Строка, её длина, подстрока. 5
1.1.2. Понятие о сложности алгоритма. 6
1.2. Алгоритмы основанные на методе последовательного поиска. 7
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm). 7
1.2.2. Алгоритм Рабина. 7
1.3. Алгоритм Кнута — Морриса — Пратта (КМП). 10
1.4. Алгоритм Бойера – Мура и некоторые его модификации. 13
1.4.1. Алгоритм Боейера – Мура. 13
1.4.2. Модификации БМ. 15
1.5. Поиск подстрок с помощью конечного автомата. 17
1.5.1. Структура автомата. 17
1.5.2. Пример построения конечного автомата 19
Часть 2. Экспериментальный анализ алгоритмов. 21
2.1. Суть эксперимента. 21
2.2. Результаты и анализ эксперимента. 22
Заключение. 24
Библиографический список. 25
Список использованной литературы
Содержание.
Введение 3
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 5
1.1. Основные понятия. 5
1.1.1 Строка, её длина, подстрока. 5
1.1.2. Понятие о сложности алгоритма. 6
1.2. Алгоритмы основанные на методе последовательного поиска. 7
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm). 7
1.2.2. Алгоритм Рабина. 7
1.3. Алгоритм Кнута — Морриса — Пратта (КМП). 10
1.4. Алгоритм Бойера – Мура и некоторые его модификации. 13
1.4.1. Алгоритм Боейера – Мура. 13
1.4.2. Модификации БМ. 15
1.5. Поиск подстрок с помощью конечного автомата. 17
1.5.1. Структура автомата. 17
1.5.2. Пример построения конечного автомата 19
Часть 2. Экспериментальный анализ алгоритмов. 21
2.1. Суть эксперимента. 21
2.2. Результаты и анализ эксперимента. 22
Заключение. 24
Библиографический список. 25