ПОШУК ЗРАЗКА В РЯДКУ

while (x[j] <> x[k+1]) and (k>0) do

k := f[k];

if (x[j] <> x[k+1] ) and (k=0) then f[j] := 0

else f[j] := k+1;

end;

Оцінимо загальну кількість порівнянь символів, виконуваних за цим алгоритмом. Позначимо через w(j) кількість виконань тіла циклу за відповідного значення j=2, … , n. Помітимо, що кожне виконання тіла циклу while зменшує значення k не менше, ніж на 1. Звідси f[j]<=f[j-1]-w(j)+1, тобто w(j)<=f[j-1]-f[j]+1. Тоді

w(2)+w(3)+…+w(n)  f[1]-f[2]+1+f[2]-f[3]+1+…+f[n-1]-f[n]+1 =

= f[1]-f[n]+n-1  n-1.За кожного j порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу – одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3(n-1), тобто прямо пропорційна n. Таким чином, загальну кількість порівнянь символів при побудові функції відступів можна оцінити як O(n).

Тепер, нарешті, наведемо алгоритм пошуку входжень зразка в рядок. Нехай t позначає номер поточної позиції в рядку, j – номер поточної позиції в зразку, спочатку вони рівні 1. Далі, поки t m, виконуємо наступні дії. Порівнюємо символи x[j] і s[t]. Якщо вони рівні, маємо входження x[1]…x[j] в кінці рядка s[1]…s[t]. Якщо при цьому j=n, то можна повідомити про входження зразка починаючи з позиції t-j+1 і приступати до пошуків наступного входження, поклавши j=f(n). Якщо ж j1 міняємо значення j на f[j-1]+1, а при j=1 збільшуємо t на 1. Втім, зміни j не мають сенсу, коли t=m. Ось і все. Наведемо цей алгоритм також і в мові Паскаль:

t:=1; j:=1;

while t<=m do

begin

if x[j]=s[t] then

if j=n then

begin writeln(t-j+1); j:=f[j] end

else

begin t:=t+1; j:=j+1 end

else { x[j]<>s[t] }

if t
if j>1 then j:=f[j-1]+1 else t:=t+1

else t:=t+1