1.3. Алгоритм Кнута - Моріса - Прата (кмп).
Спочатку розглянемо деякі допоміжні твердження. Для довільного слова X розглянемо всі його початки, одночасно що є його кінцями, і виберемо з них саме довге (не рахуючи, звичайно, самого слова X). Позначимо його n(X). Така функція носить назву префікс–функції.
Приклади.
n(aba)=a, n(n(aba))=n(a)=L;
n(abab)=ab, n(n(abab))=n(ab)=L;
n(ababa)=aba, n(n(ababa))=n(aba)=a, n(n(n(ababa)))=n(a)=L; n(abc)=L.
Доведемо кілька фактів, а саме твердження:
(1) Послідовність слів n(X),n(n(X)),n(n(n(X))),... "обривається" (на пустому слові L).
(2) Всі слова n(X),n(n(X)),n(n(n(X))),...,L є початками слова X.
(3) Будь-яке слово, одночасно є початком і кінцем слова X (крім самого X), входить в послідовність n(X),n(n(X)),....,L.
Доведення.
(1) Тривіально, так як кожне слово, коротше попереднього.
(2) Кожне з них (за визначенням) є початком попереднього. З тієї ж причини всі вони є кінцями слова X.
(3) Нехай слово Y є одночасно початком і кінцем X. Слово n(X) – саме довге з таких слів, так що Y не довше n(X). Обидва ці слова є початками X, тому більш короткий з них є початком більш довгого: Y є початок n(X). Аналогічно, Y є кінецем n(X). Розмірковуючи по індукції, можна припускати, що затвердження завдання вірно для всіх слів коротше X, зокрема, для слова n(X). Так що слово Y, є кінцем і початком n(X), або дорівнює n(X), або входить в послідовність n(n(X)),n(n(n(X))),...,,L.
Твердження доведено.
Метод КМП використовує попередню обробку шуканої стірічки, а саме: на її основі створюється префікс-функція. При цьому використовується наступна ідея: якщо префікс (він же суфікс) стрічки довжиною і довше одного символу, то він одночасно і префікс підстрічки довшої і-1.
Таким чином, ми перевіряємо префікс попередньої підстрічки, якщо ж він не підходить, то префікс її префікса, і т.д. Діючи так, знаходимо найбільший шуканий префікс. Наступне питання, на яке варто відповісти: чому час роботи процедури лінійний, адже в ній присутній вкладений цикл? Ну, по-перше, присвоєння префікс-функції відбувається чітко m раз, решту часу змінюється змінна k. Так як в циклі while вона зменшується (Т[k]<k), але не стає менше 0, то зменшуватися вона може не частіше, ніж зростати. Змінна k зростає на 1 не більш m разів. Отже, змінна k змінюється всього не більше 2m разів. Виходить, що час роботи всієї процедури є O (m).
А зараз ми переходимо до самого алгоритму, шукоючого підстрічку в стрічці (Додаток №3, функція KMPSearch).
Довести що ця програма працює лінійно, можна точно так само, як і для префікс—функції. Отже, загальний час роботи програми є O (n+m), тобто лінійний час виконання.
Назавершення зазначимо, що алгоритм послідовного пошуку та алгоритм КМП крім знаходження самих стрічок, рахують скільки символів збіглося в процесі роботи.
1.4. Алгоритм Бойера – Мура і деякі його модифікації.
1.4.1. Алгоритм Бойера – Мура.
Алгоритм Бойера-Мура, розроблений двома вченими – Бойером (Robert S. Boyer) і Муром (Strother Moore), вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підстрічки в стрічці.
Найпростіший варіант алгоритму Бойера-Мура складається з наступних кроків. На першому кроці ми будуємо таблицю зміщень для шуканого зразка. Процес побудови таблиці буде описано нижче. Далі ми сполучаєм початок стрічки і зразка і починаємо перевірку з останнього символу зразка. Якщо останній символ зразка та відповідний йому при накладенні символ стрічки не збігаються, зразок зміщується щодо стрічки на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. Якщо ж символи збігаються, проводиться порівняння передостаннього символу зразка і т. д. Якщо всі символи зразка співпали з накладенням символами стрічки, то ми знайшли підстрічку і пошук закінчено. Якщо ж будь-який (не останній) символ зразка не збігається з відповідним символом рядка, ми зсуваєм зразок на один символ вправо і знову починаємо перевірку з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнуто кінець рядка.
Величина зсуву у випадку неспівпадання останнього символу обчислюється виходячи з таких міркувань: зсув зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в стрічці. Якщо цей символ рядка зустрічається в зразку, ми зміщуєм зразок таким чином, щоб символ стрічки збігся з самим правим входженням цього символу в зразку. Якщо ж зразок взагалі не містить цього символу, ми зсуваєм зразок на величину, що дорівнює його довжині, так що перший символ зразка накладається на наступний символ стрічки, яка перевіряється.
Величина зміщення для кожного символу зразка залежить тільки від порядку символів у зразку, тому зміщення зручно вирахувати заздалегідь і зберігати у вигляді одновимірного масиву, де кожному символу алфавіту відповідає зміщення щодо останнього символу зразка. Пояснимо все вищесказане на простому прикладі. Нехай у нас є алфавіт з п'яти символів:
a, b, c, d, e і ми хочемо знайти входження зразка "abbad" в стрічці "abeccacbadbabbad". Наступні схеми ілюструють всі етапи виконання алгоритму. Таблиця зсувів буде виглядати так.
Початок пошуку.
Останній символ зразка не збігається з накладеним символом стрічки. Зсуває зразок вправо на 5 позицій:
Три символи зразка співпали, а четвертий - ні. Зсуває зразок вправо на одну позицію:
Останній символ знову не збігається із символом рядка. У відповідності з таблицею зсувів зсуває зразок на 2 позиції:
Іще раз зсуваємо зразок на 2 позиції:
Тепер, згідно з таблицею, зсуває зразок на одну позицію, і отримуємо шукане входження зразка:
