жна точно так само, як і для префікс - функції. Стало бути, загальний час роботи програми є O (n + m), тобто лінійне час. p> Наостанок зауважимо, що алгоритм послідовного пошуку і алгоритм КМП крім знаходження самих рядків вважають, скільки символів збіглося в процесі роботи.
1.4. Алгоритм Бойєр - Мура і деякі його модифікації.
1.4.1. Алгоритм Боейера - Мура.
Алгоритм Бойєр-Мура, розроблений двома вченими - Бойером (Robert S. Boyer) і Муром (Strother Moore), вважається найбільш швидким серед алгоритмів загального призначення, призначених для пошуку підрядка в рядку. p> Найпростіший варіант алгоритму Бойєр-Мура складається з наступних кроків. На першому кроці ми будуємо таблицю зміщень для шуканого зразка. Процес побудови таблиці буде описаний нижче. Далі ми поєднуємо початок рядка і зразка і починаємо перевірку з останнього символу зразка. Якщо останній символ зразка та відповідний йому при накладенні символ рядка не збігаються, зразок зрушується щодо рядка на величину, отриману з таблиці зміщень, і знову проводиться порівняння, починаючи з останнього символу зразка. Якщо ж символи збігаються, проводиться порівняння передостаннього символу зразка і т. д. Якщо всі символи зразка збіглися з накладеними символами рядки, значить ми знайшли підрядок і пошук закінчений. Якщо ж якийсь (не останній) символ зразка не співпадає з відповідним символом рядка, ми Зрушуємо зразок на один символ вправо і знову починаємо перевірку з останнього символу. Весь алгоритм виконується до тих пір, поки або не буде знайдено входження шуканого зразка, або не буде досягнутий кінець рядка.
Величина зрушення в випадку розбіжності останнього символу обчислюється виходячи з таких міркувань: зрушення зразка повинен бути мінімальним, таким, щоб не пропустити входження зразка в рядку. Якщо даний символ рядка зустрічається у зразку, ми зміщуємо взірець таким чином, щоб символ рядка збігся з самим правим входженням цього символу у зразку. Якщо ж зразок взагалі не містить цього символу, ми Зрушуємо зразок на величину, що дорівнює його довжині, так що перший символ зразка накладається на наступний за перевірялися символ рядка.
Величина зміщення для кожного символу зразка залежить тільки від порядку символів у зразку, тому зміщення зручно вирахувати заздалегідь і зберігати у вигляді одновимірного масиву, де кожному символу алфавіту відповідає зсув щодо останнього символу зразка. Пояснимо все вищесказане на простому прикладі. Нехай у нас є алфавіт з п'яти символів: a, b, c, d, e і ми хочемо знайти входження зразка "Abbad" у рядку "abeccacbadbabbad". Наступні схеми ілюструють всі етапи виконання алгоритму. Таблиця зсувів буде виглядати так. <В
Початок пошуку.
В
Останній символ зразка не співпадає з накладеним символом рядка. Зрушуємо зразок вправо на 5 позицій:
В
Три символу зразка збіглися, а четвертий - ні. Зрушуємо зразок вправо на одну позицію:
В
Останній символ знову не співпадає з символом рядка. Відповідно до таблиці зміщень Зрушуємо зразок на 2 позиції:
В
Ще раз зсуваємо зразок на 2 позиції:
p> Тепер, відповідно з таблицею, Зрушуємо зразок на одну позицію, і отримуємо шукане входження зразка:
В
Реалізуємо зазначений алгоритм на мові Pascal.
Насамперед варто визначити тип даних В«таблиця зсувівВ». Для кодової таблиці, складається з 256 символів, визначення цього типу буде виглядати так:
Type
TBMTable = Array [0 .. 255] of Integer;
Далі наводиться процедура, що обчислює таблицю зміщень для зразка p (Лістинг 5).
Лістинг 5
Procedure MakeMBTable (var Bmt: TBMTable; Const p: string);
Var i: Integer;
Begin
For i: = 0 to 255 do Bmt [i]: = Length (p);
For i: = Length (p) Downto 1 Do
If Bmt [Byte (p [i])] = Length (p) Then
Bmt [Byte (p [i])]: = Length (p) - i;
End;
p> Тепер напишемо функцію, здійснює пошук (Лістинг 6).
Параметр StartPos дозволяє вказати позицію в рядку s, з якою слід починати пошук. Це може бути корисно в тому випадку, якщо ви захочете знайти всі входження p в s. Для пошуку з самого початку рядка слід задати StartPos рівним 1. Якщо результат пошуку не дорівнює нулю, те для того, щоб знайти наступний збіг p в s, потрібно задати StartPos рівним значенню В«попередній результат плюс довжина зразка В».
1.4.2. Модифікації БМ.
Швидкий пошук (Класифікація Thierry Lecroq [2] ).
Зрушення поганого символу, який використовується в алгоритмі Боуер - Мура, не дуже ефективний для маленького алфавіту, але, коли розмір алфавіту великий порі...
