або
(число ітерацій на i-му кроці) <= l [i]-l [i +1] 1
Залишається скласти ці нерівності по всіх i і отримати оцінку
зверху для загального числа ітерацій.
Будемо використовувати цей алгоритм, щоб з'ясувати, чи є
слово X довжини n подсловом слова Y довжини m. (Як це робити за допомогою
спеціального роздільник #, описано вище.) При цьому число дій буде не
більш C (n + m), і використовувана пам'ять теж. Придумати, як обійтися пам'яттю не
більше Cn (що може бути істотно менше, якщо шуканий зразок короткий, а
слово, в якому його шукають - довге).
Рішення. Застосовуємо алгоритм КМП до слова А # В. При цьому: обчислення
значень l [1 ],..., l [n] проводимо для слова X довжини n і запам'ятовуємо ці значення.
Далі ми пам'ятаємо тільки значення l [i] для поточного i - окрім нього і крім
таблиці
l [1] ... l [n], нам для обчислень нічого не потрібно.
На практиці слова X та Y можуть не перебувати поспіль, тому
перегляд слова X і потім слова Y зручно оформити у вигляді різних циклів. Це
рятує також від клопоту з роздільником.
Написати відповідний алгоритм (перевіряє, чи є слово
X = x [1] ... x [n] подсловом слова Y = y [1] ... y [m]
Рішення. Спочатку обчислюємо таблицю l [1] ... l [n] як раніше. Потім
пишемо таку програму:
j: = 0; len: = 0;
(len - довжина максимального хитала слова X, одночасно
що є кінцем слова y [1] .. j [j])
while (len <> n) and (j <> m) do
begin
while (x [len +1] <> у [j +1]) and (len> 0) do begin
(початок не підходить, застосовуємо до нього функцію l)
len: = l [len];
end;
(знайшли підходяще або переконалися у відсутності)
if x [len +1] = y [j +1] do begin
(x [1] .. x [len] - найдовше підходяще початок)
len: len = 1;
end else begin
(відповідних немає)
len: = 0;
end;
j: = j +1;
end;
(якщо len = n, слово X зустрілося; інакше ми дійшли до кінця
слова Y, так і не зустрівши X)
Алгоритм Бойєр - Мура
Цей алгоритм робить те, що на перший погляд здається неможливим:
в типовій ситуації він читає лише невелику частину всіх літер слова, в якому
шукається заданий зразок. Як так може бути? Ідея проста. Нехай, наприклад, ми
шукаємо зразок abcd. Подивимося на четверту букву слова: якщо, приміром, це
буква e, то немає ніякої необхідності читати перші три букви. (Насправді, в
зразку букви e немає, тому він може початися не раніше п'ятого літери.)
Ми наведемо найпростіший варіант цього алгоритму, який не
гарантує швидкої роботи у всіх випадках. Нехай x [1] ... х [n] - зразок,
який треба шукати. Для кожного символу s знайдемо саме праве його входження в
слово X, тобто найбільшу k, при якому х [k] = s. Ці відомості будемо зберігати в
масиві pos [s]; якщо символ s зовсім не зустрічається, то нам буде зручно
покласти pos [s] = 0 (ми побачимо далі, чому).
Як заповнити масив pos?
Рішення.
покласти всі pos [s] рівними 0
for i: = 1 to n do begin
pos [x [i]]: = i;
end;
У процесі пошуку ми будемо зберігати в змінної last номер букви в
слові, проти якої стоїть остання буква зразка. Спочатку last = n (довжина
зразка), потім last поступово збільшується.
last: = n;
(всі попередні положення зразка вже перевірені)
while last <= m do begin (слово не скінчилося)
if
x [m] <> y [last] then begin (останні букви різні)
last: = last + (n-pos [y [last ]]);
(n - pos [y [last]] - це мінімальний зсув зразка,
при якому навпроти y [last] постане така ж
буква в зразку. Якщо такої літери немає взагалі,
то зсувається на всю довжину зразка)
end else begin
якщо нинішній стан підходить, тобто якщо
x [i] .. х [n] = y [last-n +1] .. y [last],
то повідомити про збіг;
last: = last 1;
end;
end;
Знавці рекомендують перевірку збігу проводити справа наліво,
тобто починаючи з останньої букви зразка (у якій збіг завідомо є).
Можна також трохи заощадити, зробивши віднімання заздалегідь і зберігають не pos [s],
а n-pos [s],
тобто кількість літер у зразку праворуч від останнього входження букви
Можливі різні модифікації цього алгоритму. Наприклад, можна рядок
last: = last + i
замінити на
last: = last + (n-u),
де u - координата другий праворуч входження букви x [n] в зразок.
Як простіше за все врахувати це у програмі
Рішення. При побудові таблиці pos написати
for i: = 1 to n-1 do ...
(далі як раніше), а в основній програмі замість
last: = last 1
написати
last: = last + n-pos [y [last ]];
Наведений спрощений варіант алгоритму Бойєр-Мура в деяких
випадках вимагає істотно більше n дій (число дій порядку mn),
програючи алгоритму Кнута-Моріса-Пратта.
Приклад ситуації, в якій зразок не входить в слово, але алгоритму
потрібно близько mn дій, щоб це встановити.
Рішення. Нехай зразок має вигляд baaa ... aa, а саме слово складається
тільки з літер а. Тоді на кожному кроці невідповідність з'ясовується лише в
останній момент.
Справжній (не спрощений) алгоритм Бойєр-Мура гарантує, що
число дій не перевершує C (m + n) в гіршому випадку. Він використовує ідеї,
близькі до ідей алгоритму Кнута-Моріса-Пратта. Уявімо собі, що ми
порівнювали зразок з вхідним словом, йдучи справа наліво. При цьому деякий
шматок Z (який є кінцем зразка) збігся, а потім виявилося відмінність:
перед Z у зразку варто не те, що у вхідному слові. Що можна сказати на цей
момент про вхідному слові? У ньому виявлений фрагмент, рівний Z, а перед ним стоїть
не та буква, що у зразку. Ця інформація може дозволити зрушити зразок на
декілька позицій праворуч без ризику пропустити його входження. Ці зрушення слід
вирахувати заздалегідь для кожного кінця Z нашого зразка. Як кажуть знавці, все
це (обчислення таблиці зрушень та її використання) можна укласти в C (m + n)
дій.
Алгоритм Рабіна
Цей алгоритм заснований на простій ідеї. Уявімо собі, що в
слові довжини m ми шукаємо зразок довжини n. Виріж віконечко розміру n і будемо
рухати його з вхідного слова. Нас цікавить, чи не збігається слово у віконечку
із заданим зразком. Порівнювати з
буквах довго. Натомість фіксуємо деяку функцію, визначену на словах
довжини n. Якщо значення цієї функції на слові на віконечку і на зразку різні,
то збігу немає. Тільки якщо значення однакові, потрібно перевіряти збіг
по буквах.
У чому виграш при такому підході. Здавалося б, нічого - адже щоб
обчислити значення функції на слові на віконечку, все одно треба прочитати все
літери цього слова. Так вже краще їх відразу порівняти зі зразком. Тим не менше
виграш можливий, і ось за рахунок чого. При зсуві віконечка слово не змінюється
повністю, а лише додається літера в кінці і забирається на початку. Добре б,
щоб за цими даними можна було розрахувати, як змінюється функція.
Привести приклад зручною для обчислення функції.
Рішення. Замінимо всі букви в слові і зразку їх номерами,
що представляють собою цілі числа. Тоді зручною функцією є сума цифр.
(При зсуві віконечка потрібно додати нове число і відняти зникле.)
Для кожної функції існують слова, до яких вона застосовується
погано. Зате інша функція в цьому випадку може працювати добре. Виникає ідея:
треба запастися багато функцій і на початку роботи алгоритму вибирати з них
випадкову. (Тоді ворог, який хоче напаскудити нашому алгоритмом, не буде знати, з
який саме функцією йому боротися.)
Привести приклад сімейства зручних функцій.
Рішення. Виберемо деякий число p (бажано просте, дивись
далі) і деякий вирахування x за модулем p. Кожне слово довжини n будемо
розглядати як послідовність цілих чисел (замінивши літери кодами). Ці
числа будемо розглядати як коефіцієнти многочлена мірою n-1 і обчислимо
значення цього многочлена за модулем p в точці x. Це і буде одна з функцій
сімейства (для кожної пари p і x виходить, таким чином, своя функція).
Зрушення віконця на 1 відповідає вирахуванню старшого члена (хn-1
слід вирахувати заздалегідь), множення на x і додаванню вільного члена.
Наступне міркування на користь того, що збігу не
дуже вірогідні. Нехай число p фіксоване і до того ж просте, а X і Y - два
різних слова довжини n. Тоді їм відповідають різні багаточлени (ми
припускаємо, що коди всіх букв різні - це можливо, якщо p більше числа
букв алфавіту). Збіг значень функції означає, що в точці x ці два
різних многочлена збігаються, тобто їх різниця звертається до 0. Різниця
є многочлен мірою n-1 і має не більше n-1 коренів. Таким чином, якщо і
багато менше p, то випадковому x мало шансів потрапити в невдалу крапку.
Список літератури
Для підготовки даної роботи були використані матеріали з сайту http://www.monax.ru/
