14]
З викладеного слід, що завдання пошуку підрядка складається з двох частин:
побудова автомата за зразком (визначення функції переходів для заданого зразка);
застосування цього автомата для пошуку входжень зразка в заданий текст.
1.5.2. Приклад побудови кінцевого автомата
Побудуємо кінцевий автомат, що допускає рядок ababaca. Оскільки довжина зразка m = 7 символів, те в автоматі буде m + 1 = 8 станів. p> Знайдемо функцію переходів. Відповідно до визначення (1), (q, a) = (Р q а), де - префікс-функція, а - довільний символ з алфавіту, q - номер стану. Таким чином, необхідно для кожного префікса P q = P [0 .. q], q = 0 .. m зразка Р і для всіх символів а вхідного алфавіту знайти довжину максимального префікса Р, який буде суфіксом рядки Р q а. Довжина цього префікса і буде значенням функції переходів (q, a). Якщо а = P [q + 1] (черговий символ тексту збігся з наступним символом зразка), то Р q а = Р q +1 і (q , a) = q +1. p> Такий випадок відповідає успішним етапам пошуку. Інакше, (q, a) q. Наприклад, для префікса Р [0 .. 5] = ababa і символу b максимальним суфіксом рядка Р [0 .. 5] b = ababab, який одночасно є префіксом Р, буде abab. Його довжина дорівнює 4, тому значення функції переходів (5, b) = 4. p> Запишемо побудовану таким чином функцію переходів у вигляді таблиці (Табл. 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). Звернемо увагу, що його остов позначений символами зразка (ці переходи виділені жирними стрілками).
Рис. 1
p> Тут 0 - початковий стан, 7 - єдине допускає стан (Зачерне). Якщо з вершини i у вершину j веде стрілка, позначена буквою а, то це означає, що (i, a) = j. Зазначимо, що переходи, для яких (i, a) = 0, на графі переходів для його спрощення не позначені. Жирні стрілки, що йдуть зліва направо, відповідають успішним етапам пошуку підрядка Р - наступний вхідний символ збігається з черговим символом зразка. Стрілки, що йдуть праворуч наліво, відповідають невдач - наступний вхідний символ відрізняється від чергового символу зразка.
Нижче наведено результат застосування автомата до тексту Т = abababacaba. Під кожним символом Т [г] записано стан автомата після прочитання цього символу (іншими словами, значення (Т i )) (Табл. 2).
В
Знайдено одне входження зразка (починаючи з позиції 3). Знайдений зразок в тексті позначений сірим кольором. Чорним кольором позначено допускає стан автомата (стан з номером 7).
Частина 2. Експериментальний аналіз алгоритмів.
2.1. Суть експерименту.
Ми розглянули декілька алгоритмів, провели оцінку їх часової та ємнісної складності. Однак, як уже говорилося, дан...
