Пошук зразка в рядку

Цей метод уперше описано Моррісом і Праттом у [MorPr]. Він наведений також у книзі [АХУ].Почнемо порівнювати символи зразка x=x[1]…x[n] із символами рядка s=s[1]…s[m] із початку. Нехай s[1]=x[1], … , s[j-1]=x[j-1], s[j] x[j], де j n. Зрозуміло, що зразок не входить у рядок із першої позиції. Можна, звичайно, спробувати почати перевірку з другої позиції, але зовсім не обов'язково. Наприклад, за зразка x='ababb' й рядка s='ababababbab' після того, як виявилося, що s[5]='a' 'b'=x[5], є сенс починати наступну перевірку лише з s[3], оскільки саме там є входження початку зразка. Символами s[3]s[4]='ab' водночас закінчується й починається частина зразка x[1]x[2]x[3]x[4], і наступне входження зразка можливе, коли x[1]x[2] займуть місце x[3]x[4], тобто зразок "зсунеться" відносно рядка одразу на дві позиції. Після цього можна продовжити перевірку від символу s[5], тобто без повернення назад у рядку s.

Далі виявляється 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)
Функція 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];