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

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) .

Час роботи алгоритму лінійно залежить від розміру рядка і тексту, тобто програма працює досить швидко. Проте, виникає питання в доцільності алгоритму для роботи лише із короткими рядками і цифрами. Розробники алгоритму придумали, як покращити свій же алгоритм без особливих втрат в швидкості роботи.