Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах
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(2 6 ));
write(T[i]);