Алгоритмы поиска подстроки в строке (стр. 4 из 4)
Такой случай соответствует успешным этапам поиска. Иначе,
(q,a) 
q. Например, для префикса Р[0..5] = ababa и символа b максимальным суффиксом строки Р[0..5]b=ababab, который одновременно является префиксом Р, будет abab. Его длина равна 4, поэтому значение функции переходов (5, b) = 4.Запишем построенную таким образом функцию переходов в виде таблицы (Табл. 1):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| a | 1 | 1 | 3 | 1 | 5 | 1 | 7 | 1 |
| b | 0 | 2 | 0 | 4 | 0 | 4 | 0 | 2 |
| c | 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 |
Строки соответствуют входным символам, столбцы — состояниям автомата. Ячейки, соответствующие успешным этапам поиска (входной символ совпадает со следующим символом образца), выделены серым цветом.
Построим по таблице граф переходов автомата (Рис. 1), распознающего образец ababaca. Находясь в состоянии q и прочитав очередной символ а, автомат переходит в состояние
(q,a). Обратим внимание, что его остов помечен символами образца (эти переходы выделены жирными стрелками). 
(Тi)) (Табл. 2). 
| Алгоритм | Время выполнения | ||
| Длина ≤10 | Длина ≤100 | Длина ≤250 | |
| Послед. поиск | 15 | 93 | 234 |
| Алгоритм Рабина (Хеш – сумма кодов) | 15 | 63 | 93 |
| КМП | 5 | 30 | 50 |
| БМ | 31 | 31 | 32 |
Алгоритм Рабина, при его схожести с последовательным работает быстрее, а его простота и малые трудозатраты на реализацию, делают его привлекательным для использования в неспециальных программах.
Наихудший результат показал алгоритм последовательного поиска. Как предполагалось лишь при небольшом увеличении длины строки, он работает в разы медленнее остальных алгоритмов.
В данный эксперимент не включен алгоритм поиска с помощью конечного автомата, т.к. мы используем алфавит, состоящий из 66 букв русского алфавита, и построенный автомат был бы слишком громоздок. Эффективность этого алгоритма возрастает при малом количестве букв в алфавите.
Заключение.
Мы рассмотрели различные алгоритмы поиска подстроки в строке, сделали их анализ. Результаты можно представить в таблице (Табл. 4).
| Алгоритм | Время на пред. обработку | Среднее время поиска | Худшее время поиска | Затраты памяти | Время работы (мс) при длине строки ≤250 | Примечания |
| Алгоритмы основанные на алгоритме последовательного поиска | ||||||
| Алгоритм прямого поиска | Нет | O((m-n+1)*n+1)/2 | O((m-n+1)*n+1) | Нет | 234 | Mалые трудозатраты на программу, малая эффективность. |
| Алгоритм Рабина | Нет | O(m+n) | O((m-n+1)*n+1) | Нет | 93 | |
| Алгоритм Кнута-Морриса-Пратта | ||||||
| КМП | O(m) | O(n+m) | O(n+m) | O(m) | 31 | Универсальный алгоритм, если неизвестна длина образца |
| Алгоритм Бойера-Мура | ||||||
| БМ | O(m+s) | O(n+m) | O(n*m) | O(m+s) | 32 | Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита. |
Исходя из полученных результатов, видно, что алгоритм Бойера – Мура является ведущим по всем параметрам, казалось бы, найден самый эффективный алгоритм. Но, как показывает эксперимент, алгоритм Кнута – Мориса - Пратта, превосходит алгоритм БМ на небольших длинах образца. Поэтому я не могу сделать вывод, что какой-то из алгоритмов является самым оптимальным. Каждый алгоритм позволяет эффективно действовать лишь для своего класса задач, об этом еще говорят различные узконаправленные улучшения. Алгоритм поиска подстроки в строке следует выбирать только после точной постановки задачи, которые должна выполнять программа.
Сделав такой вывод, мы выполнили цель данной работы, т.к. для различных классов задач был выделен свой эффективный алгоритм.
Библиографический список.
1). Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching System [Текст]. – Bielefeld:. Universität Bielefeld, 1995. – 238 с.
2). Lecro, T. Exact string matching algorithms [Электронныйресурс]. Режим доступа http://algolist.manual.ru/
3). Ахметов И. Поиск подстрок с помощью конечных автоматов [Текст]: Курсовая работа.- С-П государственный университет информационных технологий, механики и оптики.
4). Ахо, Альфред Структура данных и алгоритмы [Текст]. – М.: Издательский дом «Вильямс», 2000. - 384 с.
5). Белоусов А. Дискретная математика [Текст]. – М.: Издательство МГТУ им. Н.Э. Баумана, 2001. – 744 с.
6). Брайан, К. Практика программирования [Текст].- СПб:. Невский диалект, 2001. - 381 с.
7). Вирт, Н. Алгоритмы и структуры данных [Текст].– М:. Мир, 1989. – 360 с.
8). Гилл, Арт. Введение в теорию конечных автоматов [Текст]. – М., 1966. - 272 с.
9). Глушаков С. Программирование Web – страниц [Текст]. – М.: ООО «Издательство АСТ», 2003. – 387 с.
10). Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. – М:. Мир, 1978. – 356 с.
11). Матрос Д. Элементы абстрактной и компьютерной алгебры: Учеб. пособие для студ. педвузов [Текст]. – М.: Издательский центр «Академия», 2004. – 240 с.
12). Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. – М.: Наука, 1987. – 288 с.
13). Шень, А. Программирование: теоремы и задачи [Текст]. – М.: Московский центр непрерывного математического образования, 1995.
14). Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М.: МЦНМО, 2002.