довго. Замість цього фіксуємо деяку числову функцію на словах довжини n, тоді завдання зведеться до порівняння чисел, що, безсумнівно, швидше. Якщо значення цієї функції на слові в "віконечку" і на зразку різні, то збігу немає. Тільки якщо значення однакові, необхідно перевіряти послідовно збіг по буквах. В»(Лістинг 2)
Лістинг 2
Function Search (S: String; X: String; var Place: Byte): Boolean;
{Функція повертає результат пошуку в слові S}
{подслова X. Place - місце першого входження}
Var Res: Boolean; i: Byte; h, NowH, LenX: Integer; HowMany: Integer;
Begin
Res: = FALSE;
i: = 1;
h: = Hash
(x); {Обчислення хеш-функції для шуканого слова}
NowH: = Hash (Copy (S, 1, Length (x)));
HowMany: = Length (S)-Length (X) +1;
LenX: = Length (X);
While (i <= HowMany) And Not (Res) do
If (h = NowH) and (Copy (S, i, Length (X)) = X) then
Begin
Res: = TRUE;
Place: = i
End
else
Begin
i: = i +1;
NextHash (s, i , NowH, LenX); {Обчислення наступного значення хеш-функції}
End;
Search: = Res
End;
В В В В В В
Цей алгоритм виконує лінійний прохід по рядку (n кроків) і лінійний прохід по всьому тексту (M кроків), стало бути, загальний час роботи є O (n + m). При цьому ми не враховуємо тимчасову складність обчислення хеш-функції, так як, суть алгоритму в тому і полягає, щоб дана функція була настільки легко обчислюється, що її робота не впливала на загальну роботу алгоритму. Тоді, час роботи алгоритму лінійно залежить від розміру рядка і тексту, стало бути програма працює швидко. Адже замість того, щоб перевіряти кожну позицію на предмет відповідності із зразком, ми можемо перевіряти тільки ті, які В«нагадуютьВ» зразок. Отже, для того, щоб легко встановлювати явна невідповідність, будемо використовувати функцію, яка повинна: ​​
1. Легко обчислюватися.
2. Як можна краще розрізняти неспівпадаючі рядки.
3. hash (y [i +1, i + m]) повинна легко обчислюватися за hash (y [i, i + m-1].
Під час пошуку х будемо порівнювати hash (x) з hash (y [i, i + m-1]) для i від 0 до nm включно. Якщо виявляємо збіг, то перевіряємо посимвольно. p> Приклад (зручною для обчислення функції) [13, +172]. Замінимо всі букви в слові і зразку їх номерами, що представляють собою цілі числа. Тоді зручною функцією є сума цифр. (При зсуві "віконечка" потрібно додати нове число і відняти "зникле".)
Однак, проблема в тому, що шукана рядок може бути довгою, рядків в тексті теж вистачає. А так як кожному рядку потрібно зіставити унікальне число, то і чисел повинно бути багато, а стало бути, числа будуть великими (порядку D * n, де D - кількість різних символів), і працювати з ними буде так само незручно. Але який інтерес працювати тільки з короткими рядками і цифрами? Розробники алгоритму винайшли, як поліпшити цей алгоритм без особливих втрат у швидкості роботи.
Приклад (сімейства зручних функцій) [13, 172-173]. Виберемо деякий число p (бажано просте) і деякий вирахування x за модулем p. Кожне слово довжини n будемо розглядати як послідовність цілих чисел (замінивши літери їх кодами). Ці числа будемо розглядати як коефіцієнти многочлена ступеня n-1 і обчислимо значення цієї многочлена за модулем p в точці x. Це і буде одна з функцій сімейства (для кожної пари p і x виходить своя функція). Зсув "віконечка" на 1 відповідає вирахуванню старшого члена, множенню на x і додаванню вільного члена. Наступне міркування говорить на користь того, що збігу не занадто вірогідні. Нехай число p фіксоване і до того ж воно є простим, а X і Y - два різних слова довжини n. Тоді їм відповідають різні багаточлени (ми припускаємо, що коди всіх букв різні - це можливо при p, більшому числа букв алфавіту). Збіг значень функції означає, що в точці x ці два різних многочлена збігаються, тобто їх різниця звертається до 0. Різниця є багаточлен ступеня n-1 і має не більше n-1 коренів. Таким чином, якщо n багато менше p, то випадковому значенням x мало шансів потрапити в "невдалу" крапку.
Строго кажучи, час роботи всього алгоритму в цілому, є O (m + n + mn/P), mn/P досить невелика, так що складність роботи майже лінійна. Зрозуміло, що просте число слід вибирати більшим, чим більше це число, тим швидше буде працювати программа.
Алгоритм Рабіна і алгоритм послідовного пошуку є алгоритмами з найменшими трудовитратами, тому вони годяться для використання при вирішенні деякого класу завдань. Однак ці алгоритми не є ...
