Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах

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;