розглянули різні алгоритми пошуку підрядка в рядку, зробили їх аналіз. Результати можна представити в таблиці (Табл. 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
Алгоритми цієї групи найбільш ефективні в звичайних ситуаціях. Швидкодія підвищується при збільшенні зразка або алфавіту. /Td>
Виходячи з отриманих результатів, видно, що алгоритм Бойєр - Мура є провідним по всіма параметрами, здавалося б, знайдено найбільший ефективний алгоритм. Але, як показує експеримент, алгоритм Кнута - Моріса - Пратта, перевершує алгоритм БМ на невеликих довжинах зразка. Тому я не можу зробити висновок, що якийсь з алгоритмів є найоптимальнішим. Кожен алгоритм дозволяє ефективно діяти лише для свого класу задач, про це ще говорять різні вузьконаправлені поліпшення. Алгоритм пошуку підрядка в рядку слід вибирати тільки після точної постановки завдання, які повинна виконувати програма.
Зробивши такий висновок, ми виконали мета даної роботи, тому для різних класів задач був виділений свій ефективний алгоритм.
В
Бібліографічний список.
1). Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching System [Текст]. - Bielefeld:. UniversitГ¤t Bielefeld, 1995. - 238 с. p> 2). Lecro, T. Exact string matching algorithms [Електронний ресурс]. Режим доступу
3). Ахметов І. Пошук підрядків за допомогою кінцевих автоматів [Текст]: Курсова робота. - С-П державний університет інформаційних технологій, механіки й оптики.
4). Ахо, Альфред Структура даних та алгоритми [Текст]. - М.: Видавничий дім «³льямсВ», 2000. - 384 с. p> 5). Бєлоусов А. Дискретна математика [Текст]. - М.: Видавництво МГТУ ім. Н.Е. Баумана, 2001. - 744 с. p> 6). Брайан, К. Практика програмування [Текст]. - СПб:. Невський діалект, 2001. - 381 с. p> 7). Вірт, М. Алгоритми та структури даних [Текст]. - М:. Світ, 1989. - 360 с. p> 8). Гілл, Арт. Введення в теорію кінцевих автоматів [Текст]. - М., 1966. - 272 с. p> 9). Глушаков С. Програмування Web - сторінок [Текст]. - М.: ТОВ В«Видавництво АСТ В», 2003. - 387 с. p> 10). Кнут, Д. Мистецтво програмування на ЕОМ [Текст]: Том 3. - М:. Світ, 1978. - 356 с. p> 11). Матрос Д. Елементи абстрактної та комп'ютерної алгебри: Учеб. посібник для студ. педвузів [Текст]. - М.: Видавничий центр В«АкадеміяВ», 2004. - 240 с. p> 12). Успенський У. Теорія алгоритмів: основні відкриття і додатку [Текст]. - М.: Наука, 1987. - 288 с. p> 13). Шень, А. Програмування: теореми і задачі [Текст]. - М.: Московський центр безперервної математичної освіти, 1995. p> 14). Кормен, Т. Алгоритми: побудова та аналіз [Текст]/Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002. М. МЦНМО, 2002. br/>
