Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з малих літер англійського алфавіту, використовуючи прямий пошук знайти позицію першого входження даного підрядка в рядок.
Program Seach_2_1;
Uses Crt;
Const nmax=10000;
var p:string; {підрядок}
s:array[1..nmax]of char; {рядок}
d:array[char]of byte; {масив зрушень}
c:char;
m,i,j,k:integer;
begin
ClrScr;
Randomize;
for i:=1 to nmax do
begin
s[i]:=chr(97+random(26));
write(s[i]);
end;
Writeln(‘-----------------------------------’);
Writeln(‘Vvedit pidrjadok’);
Readln(p);
m:=length(p);{довжина підрядка}
for c:=chr(0) to chr(255) do d[c]:=m;
for j:=1 to m-1 do d[p[j]]:=m-j;
{масив d визначений}
i:=m+1;
repeat {вибір фрагмента в рядку}
j:=m+1; k:=i;
repeat {перевірка збігу}
k:=k-1; j:=j-1
until (j<1) or(p[j]<>s[k]);
i:=i+d[s[i-1]];{зрушення}
until (j<1) or(i>nmax+1);
Writeln;
Writeln(‘--------------------’#10#13’pozucia = ‘);
if j<1 then write(k+1) else write(0)
readln;
end.
2.2 Алгоритм Рабіна-Карпа
Ідея, яку запропонували Рабін і Карп, має на меті поставити в відповідність кожному рядку деяке унікальне число, і замість того щоб порівнювати самі рядка, порівнювати числа, що теоретично і практично є набагато швидшою дією. Проблема в тому, що шуканий рядок може бути великою, і рядків у тексті теж. А так як кожному рядку потрібно спів ставити унікальне число, то чисел повинно бути багато, а відповідно, числа будуть теж великими (порядку Dm, де D – кількість різних символів), працювати з ними буде так само незручно. Розглянемо реалізацію даного алгоритму для тексту, що складається лише із цифр, і рядка довжиною до 8 символів.
Program RabinKarpSearch;
Var T : array[1..40000] of 0..9;
S : array[1..8] of 0..9;
i,j : longint;
n,m : longint;
v,w : longint; {v - число, що характеризує шуканий рядок, w характеризує рядок довжини m в тексті}
k : longint;
const D : longint = 10; {кількість різних символів (10 цифр 0,1,2,..9)}
Begin
{Ввід тексту і зразка}
…
v:=0;
w:=0;
for i:=1 to m do
begin
v:=v*D+S[i]; {обчислення v, рядок подається як число}
w:=w*D+T[i]; {обчислення початкового значення w}
end;
k:=1;
for i:=1 to m-1 do {k потрібне для багаторазового обрахунку w і має значення Dm-1}
k:=k*D;
for i:=m+1 to n+1 do
begin
if w=v then {якщо числа рівні, то рядки співпадають, а значить, зразок знайдений в тексті}
writeln('Зразок входить в текст із ',i-m,'-ого символу');
if i<=n then
w:=d*(w-k*T[i-m])+T[i]; {обчислення нового значення w}
end;
End.
За цим алгоритмом виконується лінійний прохід по рядку (m кроків) і лінійний прохід по всьому тексту (n кроків), отже загальний час роботи рівний O(n+m).
Час роботи алгоритму лінійно залежить від розміру рядка і тексту, тобто програма працює досить швидко. Проте, виникає питання в доцільності алгоритму для роботи лише із короткими рядками і цифрами. Розробники алгоритму придумали, як покращити свій же алгоритм без особливих втрат в швидкості роботи.
Як видно, спочатку ставили в відповідність рядку його числовий еквівалент, проте виникала проблема великих чисел. Її можна оминути, якщо виконувати всі арифметичні дії по модулю якогось простого числа (постійно брати остачу від ділення на це число). Таким чином, знаходимо не саме число, що характеризує рядок, а його остачу від ділення на деяке просте число. Тепер ми ставимо число в відповідність не одному рядку, а цілому класу, так як класів буде дуже багато (стільки, скільки різних остач від ділення на це просте число), то додаткову перевірку прийдеться виконувати доволі рідко.
Var T : array[1..40000] of char;
S : array[1..10000] of char;
i,j : longint;
n,m : longint;
v,w : longint;
k : longint;
const P : longint = 7919; {1000-е простое число}
D : longint = 256; {кількість різних символів (кількість різних символів типу char)}
Begin
{Ввід тексту і зразка}
…
v:=0;
w:=0;
for i:=1 to m do {обчислення v і w}
begin
v:=(v*D+ord(S[i])) mod P; {ord повернення коду символа}
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k має значення Dm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then {якщо числа рівні, то рядки належать одному класу, і потрібно перевірити, чи вони рівні}
begin
j:=0;
while (j<m) and (S[j+1]=T[i-m+j]) do
j:=j+1;
if j=m then {кінцева перевірка}
writeln('Зразок входить в текст починаючи з ',i-m,'-ого символу ');
end;
if i<=n then
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
І так, нам все ж приходиться порівнювати рядки посимвольно використовуючи даний алгоритм, проте, оскільки "холостих" порівнювань буде небагато (в 1/Р випадках), то очікуваний час роботи буде невеликий. В загальному випадку, час роботи = O(m+n+mn/P), mn/P досить не велике, так що складність роботи практично лінійна. Зрозуміло, що просте число потрібно вибирати велике, чим більше це число, тим швидше буде працювати програма. Цей алгоритм набагато швидший за алгоритм прямого пошуку підрядка в рядку і його застосування більш доцільне при роботі із дуже довгими рядками.
Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з малих літер англійського алфавіту, використовуючи метод Рабіна-Карпа знайти позицію першого входження даного підрядка в рядок.
Program Seach_2_2;
Uses Crt;
Var T : array[1..40000] of char;
S : array[1..10000] of char;
i,j : longint;
n,m : longint;
v,w : longint;
k : longint;
c:char;
const P : longint = 7919; {1000-е простое число}
D : longint = 256; {кількість різних символів (кількість різних символів типу char)}
Begin
ClrScr;
Randomize;
Writeln(‘ Vvedit dovguny texty n’);
Readln(n);
Writeln(‘ Vvedit dovguny pidradka m, m<n’);
Readln(m);
for i:=1 to n do
begin
T[i]:=chr(97+random(26));
write(T[i]);
end;
Writeln;
Writeln(‘-----------------------------------’);
Writeln(‘Vvedit pidrjadok sumvolu a..z’);
I:=1;
While i<=m do
Begin
C:=readkey;
If (ord(c)>96)and(ord(c)<123)then begin
S[i]:=c;
Write(s[i]);
Inc(i);
End;
End;
Writeln;
v:=0;
w:=0;
for i:=1 to m do {обчислення v і w}
begin
v:=(v*D+ord(S[i])) mod P; {ord повернення коду символа}
w:=(w*D+ord(T[i])) mod P;
end;
k:=1;
for i:=1 to m-1 do
k:=k*D mod P; {k має значення Dm-1 mod P}
for i:=m+1 to n+1 do
begin
if w=v then {якщо числа рівні, то рядки належать одному класу, і потрібно перевірити, чи вони рівні}
begin
j:=0;
while (j<m) and (S[j+1]=T[i-m+j]) do
j:=j+1;
if j=m then {кінцева перевірка}
writeln('Зразок входить в текст починаючи з ',i-m,'-ого символу ');
end;
if i<=n then
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;
End.
2.3 Алгоритм Кнута-Морріса-Пратта
Ще одним важливий метод, - алгоритм Кнута-Морріса-Пратта, один із найкращих на сьогоднішній момент, працює за лінійний час для довільного тексту і довільного рядка.
Метод виконує предобробку шуканого рядка, а саме: на її основі створюється так звана префікс-функція. Суть цієї функції в знаходженні для кожного підрядка S[1..i] рядка S найбільшого підрядка S[1..j] (j<i), що присутній одночасно і в початку і в кінці підрядка (як префікс так і суфікс). Наприклад для підрядка abcHelloabc таким підрядком відповідно є abc (одночасно і префікс, і суфікс). Зміст даної префікс-функції полягає в тому, що ми можемо відкинути завідомо невірні варіанти, тобто, якщо при пошуку співпав підрядок abcHelloabc (наступний символ не співпав), то нам є смисл продовжити перевірку вже із четвертого символу (перші три і так співпадуть). Ось як можна обрахувати цю функцію для всіх значень параметра від 1 до m:
var S : array[1..10000] of char;
P : array[1..10000] of word; {масив, в якому зберігаються значення префікс-функції}
i,k : longint;
m : longint;
…
Procedure Prefix; {процедура, що знаходить префікс-функцію}
Begin
P[1]:=0; {префікс рядка із одного символу має нульову довжину}
k:=0;
for i:=2 to m do {обраховуємо для префіксів рядки довжиною від 2 до m символів}
begin
while (k>0) and (S[k+1]<>S[i]) do
k:=P[k]; {значення функції може бути отримане із обчислень, проведених раніше}
if S[k+1]=S[i] then
k:=k+1;
P[i]:=k; {присвоєння префікс-функції}
end;
End;
Давайте тепер розглянемо дану функцію, і перевіримо, чи правильно обраховується префікс-функція. Використовується наступна ідея: якщо префікс (він же суфікс) рядка довжиною і довший одного символу, то він же одночасно і префікс підрядка довжиною і-1. Таким чином, ми перевіряємо префікс попереднього підрядка, якщо ж він не підходить, то префікс її префікса і т.д. Діючи таким способом, ми знаходимо найбільший шуканий префікс. Наступне питання, на який потрібно відповісти: чому час роботи процедури ми вказали лінійний, якщо в ній присутній вкладений цикл? Ну, по-перше, присвоєння префікс-функції виконується чітко m раз, решта часу міняється змінна k. Так як в циклі while вона зменшується (P[k]<k), але не стає меншою 0, то зменшуватися вона може не частіше, чи зростати. Змінна k зростає на 1 не частіше m раз. Значить, змінна k міняється всього не більше як 2m разів. Звідки слідує, що час роботи всієї процедура рівний O(m).