Далі виявляється s[7]? x[5], і зразок можна зсунути одразу на дві позиції, щоб x[1]x[2] знову зайняли місце x[3]x[4], збігаючися при цьому з s[5]s[6]. Тепер s[7]=x[3], s[8]=x[4], s[9]=x[5], і входження починаючи з позиції 5 знайдено.

Отже, нехай перевіряється входження зразка від позиції i-j, x[1]…x[j]=s[i-j]…s[i-1], а x[j+1] не збігається з черговим символом рядка s[i]. У такому разі треба відшукати такий найдовший початок x[1]…x[k] зразка, що водночас є кінцем підрядка x[1]…x[j]. Він є також і кінцем підрядка s[1]…s[i-1]!

Перехід від перевіреного початку зразка довжини j до перевіреного початку довжини k означає зсув зразка відносно рядка s одразу на j-k позицій. Але на меншу кількість позицій зсувати зразок немає сенсу, оскільки x[1]…x[k] – це найдовший початок зразка, що збігається з кінцем підрядка s[1]…s[i-1].

Якщо x[k+1]=s[i], то можна продовжувати порівняння від символу s[i+1]. Якщо x[k+1]? s[i], то треба відшукати найдовший початок x[1]…x[k1] зразка, що збігається з кінцем x[1]…x[k] (і з кінцем s[1]…s[i-1]), і порівняти x[k1+1] із s[i] тощо.

Наприклад, якщо s='abababc', а x='ababc', то при спробі "прикласти" зразок починаючи з першого символу рядка маємо x[1]=s[1], x[2]=s[2], x[3]=s[3], x[4]=s[4], x[5]? s[5], тобто j=4. Відповідним значенням k буде 2, оскільки 'ab' є найдовшим початком рядка 'abab', що є водночас його кінцем. Звідси випливає, що немає сенсу пробувати "прикласти" зразок до рядка, починаючи з його другої позиції, а слід "пересунути" його одразу на j-k=2 позиції. При цьому гарантується рівність x[1]…x[k] і s[i-k]…s[i-1], тобто назад від позиції s[i] в рядку можна не повертатися.

Отже, якщо для кожної позиції j зразка відома найбільша довжина f(j)<j такого початку зразка x[1]…x[f(j)], що збігається з кінцем x[1]…x[j], то перше входження зразка знаходиться без повернень у рядку s. Для визначення можливого початку наступного входження треба знати лише f(n) і продовжувати пошук знову-таки без повернень у рядку! Саме відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як O(m+n), що суттєво менше, ніж O(m? n). Ми доведемо це далі.

Функція f(j), що виражає довжину такого найдовшого початку рядка x[1]…x[j], що є водночас його кінцем, називається функцією відступів. Вона показує, до якого символу x[f(j)] треба відступити в зразку, коли x[j+1] не збігається з черговим символом рядка, щоб продовжувати пошук із порівняння чергового символу з символом x[f(j)+1]. Цей відступ рівносильний зсуву рядка на найменшу можливу кількість позицій j-f(j). Займемося тепер обчисленням цієї функції за зразком.

Очевидно, f(1)=0. Нехай всі значення f(1), … , f(j-1) уже обчислено, причому f(j-1)=k. Якщо x[j]=x[k+1], то кінець рядка x[1]…x[j-1]x[j] збігається з його ж початком довжини k+1, тому f(j)=k+1. Якщо x[j]? x[k+1], то "наступним кандидатом у кінці" рядка x[1]…x[j-1]x[j] є рядок x[1]…x[f(k)]x[f(k)+1], оскільки саме x[1]…x[f(k)] є найдовшим кінцем x[1]…x[k]. Якщо й він не годиться, то наступним є x[1]…x[f(f(k))+1] тощо. Отже, ми або знайдемо початок довжини p, такий, що x[1]…x[p] є кінцем x[1]…x[j], і тоді f(j)=p, або не знайдемо, і f(j)=0.

Наведені обчислення описуються таким алгоритмом (подамо функцію f масивом):

f[1] := 0;

for j := 2 to n do

begin

k := f[j-1];

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). Якщо ж j<n, то переходимо до наступної пари символів, збільшивши t і j на 1. За нерівності s[t] і x[j] при j>1 міняємо значення 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<m then

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

else t:=t+1

end.

Оцінимо тепер кількість порівнянь символів при виконанні цього алгоритму. Помітимо, що при кожному виконанні тіла циклу збільшується t на 1 або зменшується j принаймні на 1 присвоюванням f[j] чи f[j-1]+1. Позначимо через b(t) початкове значення j при черговому значенні t=1, 2, …, m, а через w(t) – кількість зменшень j при відповідному значенні t. Оскільки при збільшенні t значення j або не міняється, або збільшується на 1, то маємо, що b(t)? b(t-1)-w(t)+1 за t>1, звідки w(t)? b(t-1)-b(t)+1. Тоді

w(1)+w(2)+…+w(m) ?