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

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;