Федеральне міністерство з освіти
Державна освітня установа вищої професійного навчання
В«Вятський державний гуманітарний університетВ»
Факультет інформатики
Кафедра інформатики та методики навчання інформатики
Курсова робота
Алгоритми пошуку підрядка в рядку
Виконав
студент III курсу математичного факультету
Бєлов Денис Володимирович
Перевірив викладач кафедри інформатики і методики навчання інформатики
Іванов С. Ю.
Кіров, 2006
Зміст.
Введення. 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
Введення
Ті, кому доводитися часто працювати з текстовими редакторами, знають ціну функції знаходження потрібних слів у тексті, істотно полегшує редагування документів і пошук потрібної інформації. Дійсно, сучасні програми обробки тексту привчили нас до такої зручної можливості, як пошук і заміна фрагментів, і якщо ви розробляєте подібну програму, користувач має право очікувати, що ви надасте в його розпорядження відповідні команди.
Звичайно, зараз функції пошуку інкапсульовані в багато мов програмування високого рівня - Щоб знайти рядок у невеликому тексті ви, напевно, використовуєте вбудовану функцію. Але якщо такого роду пошук є ключовою завданням вашій програми, знати принципи організації функцій пошуку буде зовсім не зайве. При цьому. в готових підпрограма далеко не завжди все написано кращим чином. По-перше, в стандартних функціях не завжди використовуються найефективніші алгоритми, а по-друге, цілком можливо, що вам знадобиться змінити стандартну поведінку цих функцій (наприклад, передбачити можливість пошуку за шаблоном). Нарешті, область застосування функції пошуку не обмежується одними лише текстовими редакторами. Слід відзначити використання алгоритмів пошуку при індексації сторінок пошуковим роботом, де актуальність інформації безпосередньо залежить від швидкості знаходження ключових слів у тексті html - сторінки [9, с. 10]. Робота найпростішого спам - фільтра, полягає в знаходженні в тексті листа фраз таких, як В«Мільйон за годинуВ» або В«Розкрутка сайту В». Все вищесказане говорить про актуальність проблеми, зачепленої роботою.
Поставимо завдання пошуку підрядка в рядку. Нехай у нас є рядок, що складається з деякого кількості символів. Нам потрібно перевірити, чи входить інша задана рядок в даний текст, і якщо входить, то починаючи з якого символу тексту. p> У даній роботі ми ставимо мету, виявити найбільш оптимальний алгоритм, вирішальний поставлену завдання пошуку.
Завдання даної роботи:
В· розглянути основні алгоритми, що вирішують завдання пошуку;
В· систематизувати алгоритми згідно використовуваним в них прийомів;
В· виявити ефективні, з точки зору часу виконання, алгоритми.
Робота містить дві основних частини. У першій будуть розглянуті алгоритми, їх теоретичне обгрунтування, алгоритмічна модель, буде проведена спроба їх класифікації. У другій частині роботи будуть наведені дані про практичне застосування алгоритмів. У висновку буде зроблено висновок про найбільш ефективне (з тимчасової точки зору) алгоритмі.
В
Частина 1. Теоретичні відомості про алгоритми пошуку підрядка в рядку.
1.1. Основні поняття.
1.1.1 Рядок, її довжина, підрядок.
Тут ми наводимо ряд визначень, які будемо використовувати у викладі матеріалу [5, 11]. p> Ухвала 1 . Рядок (слово) - це послідовність знаків (званих літерами) з деякого кінцевого безлічі, званого алфавітом. p> Визначення 2 . Довжина рядка - кількість знаків у рядку.
Слова будемо позначати літерами латинського алфавіту, напр. X = x [1] x [2] ... x [n] - слово довгою n, де x [i] (i-ая літера слова) належить алфавіту. Lentgh (X) == n - позначення довжини рядки. p> Визначення 3 . Слово не містить ні однієї букви нази...
