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

Розглянемо всю программу, що шукає рядок в тексті.

Program KnutMorrisPrattSearch;

…

{ Опис процедури Prefix і пов’язаних з нею змінних}

…

var n : longint;

T : array[1..40000] of char;

Begin

{ Ввід тексту і зразку}

…

Prefix; { Обчислення префікс-функції}

k:=0; { кількість символів, що співпадають на даний час}

for i:=1 to n do

begin

while (k>0) and (S[k+1]<>T[i]) do

k:=P[k];

if S[k+1]=T[i] then

k:=k+1;

if k=m then { якщо співпали всі символи}

begin

writeln(' Зразок входить в текст починаючи з ',i-m+1,' -ого символу');

k:=P[k];

end;

end;

End.

Довести, що ця програма працює за лінійний проміжок часу, можна аналогічно доведенню, наведеному вище для процедури Prefix . Отже, загальний час роботи програми рівний O(n+m) , тобто лінійний час.

Алгоритм Кнута-Морріса-Пратта більш громіздкий ніж наведені вище, проте час роботи із великими об’ємами даних є набагато меншим, тобто він більш швидше працює із великими об’ємами тексту ніж решта алгоритмів.

Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з літер англійського алфавіту, використовуючи метод Кнута-Морріса-Пратта знайти позицію першого входження даного підрядка в рядок.

Program Seach_2_3;