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:

Страницы: 1, 2, 3, 4