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

1. Оцінка кількості порівнянь

Задача. У рядку відшукати всі позиції, починаючи з яких інший рядок Зразок Входить в рядок, тобто є його підрядком. Наприклад, у рядку

ABRACADABRA

Зразок ABR входить як підрядок з позицій 1 і 8, зразок A – з позицій 1, 4, 6, 8 і 11, а зразок ARA не входить.

Позначимо через S рядок, у якому шукається зразок X. Нехай M і N – довжини рядків S і X. Можна порівняти з X усі підрядки S довжини N, які починаються з позицій 1, 2, , M N+1. У разі рівності друкується відповідна позиція:

For k:=1 To mn+1 Do

If copys, k, n=x Then writelnk.

Нагадаємо, що з виклику copys, k, n повертається підрядок рядка S, що починається в його позиції K та має довжину N. Дуже просто, але дуже нерозумно! Адже загальна кількість порівнянь символів є M N+1 N. Наприклад, за M=255, N=128 порівнянь символів буде 1282=16384, хоча Більшість їх насправді зайва. Ми переконаємося в цьому, розглянувши далі зовсім інші способи пошуку зразка.

Але спочатку оцінимо зверху кількість порівнянь символів. Зафіксуємо довжину рядка M. Нехай довжина зразка N довільна в межах між 1 та M. Тоді M N+1 N M n. Як бачимо, різниця N2 N між M n та M N+1 N мала за значень N, близьких до 1, і велика за N, близьких до M. За малих значень N величиною N2 N можна нехтувати. Таким чином, наша оцінка

M N+1 N = O M n

Є досить точною за малих значень N і грубою – за великих. Припустивши, що зразки з великою довжиною – явище дуже рідкісне, можна вважати цю оцінку цілком прийнятною.

2. Метод БойєраМура спрощений варіант

Один із способів суттєво зменшити кількість порівнянь належить Бойєру та Муру [BoMo]. Розглянемо спрощений варіант їх алгоритму. Нехай символи рядка й зразка належать деякому алфавіту. Нехай зразок X= X[1] X[2] X[ N]. Спочатку для кожного символу Z алфавіту визначається номер позиції P[ Z] його Останньої появи в рядку X. Якщо символ Z відсутній в X, то P[ Z]=0. Наприклад, у зразку 'ababc' P['a']=3, P['b']=4, P['c']=5, а для решти символів Z алфавіту P[ Z]=0.

Обчислення масиву P очевидне:

Для всіх символів Z алфавіту p[ Z]:=0;

For k:=1 To n Do p[ X[k]]:=k.

Інформація про останню появу символів у зразку використовується так. Порівняємо одразу S[ N] та X[ N]. Якщо S[ N] X[ N], то найближчим до кінця зразка символом, якому рівний S[ N], є символ X[ P[ S[ N]]]. Таким чином, можна не порівнювати S[ N] із жодним із символів зразка між X[ P[ S[ N]]] та X[ N]. А це означає, що можна не перевіряти рівність зразка з підрядками, що починаються з позицій 2, 3, , N P[ S[ N]]. Наприклад, якщо X='ababc', а рядок S починається символами aaaba, то P[ S[5]]=3 підказує, що зразок не може починатися в рядку з позиції 53=2. Отже, за S[ N] X[ N] можна перейти одразу до порівняння X[ N] із S[ N+ N P[ S[ N]]].

Якщо S[ N]= X[ N], то можна порівняти попередні символи рядка з відповідними символами зразка, рухаючися від його кінця до початку. Якщо всі відповідні символи рівні, то зразок є підрядком, що починається з першої позиції рядка. Після цього можна переходити до аналізу другої позиції S, порівнюючи X[ N] із S[ N+1].

Якщо за деякого K0 S[ K] X[ K], то серед X[ K1], , X[1] треба відшукати найближчий до X[ K] символ X[ J]= S[ K]. Ця рівність означає, що зразок, можливо, має кінець у рядку в позиції K+ N J, тобто N+ K J. Тоді можна знову починати все з кінця зразка, порівнюючи X[ N] із S[ N+ K J].

Нехай змінна last позначає позицію кінця зразка в рядку S. Спочатку last= N, а його наступним значенням може бути лише, як показує попередній аналіз, або N+1, або N+ N P[ S[ N]], або N+ K J. За будьякого з цих значень змінної last наступним її значенням буде так само або last+1, або last+last P[ S[ N]], або last+ K J. На основі цих міркувань записується такий спрощений варіант алгоритму БойєраМура:

Last:=n;

While last=m Do

If x[n]s[last] Then last:=last+np[s[n]]

Else

Begin

K:=n1; ok:= True;

While k0 And ok Do

If x[k]=s[lastn+k] Then k:=k1 Else ok:= False;

If k=0 Then {s[lastn+1]s[last]= X}

Begin

Повідомити про те, що з lastn+1 починається зразок;

Last:=last+1

End else

Begin

Відшукати серед x[1]x[k1] найближчий до x[k]

Символ x[j], рівний s[lastn+k]; якщо такого немає, то j:=0

Last:=last+kj

End

End.

Зауважимо, що цей спрощений варіант в деяких випадках не рятує від необхідності здійснювати O M n порівнянь символів. Справжній алгоритм БойєраМура забезпечує, що кількість порівнянь символів за будьяких рядків довжини M і N оцінюється як O M+ N, тобто її можна вважати пропорційною сумі довжин рядка й зразка. Ідея цього методу приблизно така сама, як і методу з наступного підрозділу.

3. Метод КнутаМоррісаПратта

Цей метод уперше описано Моррісом і Праттом у [MorPr]. Він наведений також у книзі [АХУ].

Почнемо порівнювати символи зразка X= X[1] X[ N] із символами рядка S= S[1] S[ M] із початку. Нехай S[1]= X[1], , S[ J1]= X[ J1], 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[ I1], а X[ J+1] не збігається з черговим символом рядка S[ I]. У такому разі треба відшукати такий Найдовший початок x[1]x[k] зразка, що водночас є кінцем підрядка x[1]x[j]. Він є також і кінцем підрядка S[1] S[ I1]!

Перехід від перевіреного початку зразка довжини J до перевіреного початку довжини K означає зсув зразка відносно рядка S одразу на J K позицій. Але на меншу кількість позицій зсувати зразок немає сенсу, оскільки X[1] X[ K] – це Найдовший початок зразка, що збігається з кінцем підрядка s[1] S[ I1].

Якщо X[ K+1]= S[ I], то можна продовжувати порівняння від символу S[ I+1]. Якщо X[ K+1] S[ I], то треба відшукати найдовший початок X[1] X[ K1] зразка, що збігається з кінцем X[1] X[ K] і з кінцем S[1] S[ I1], і порівняти 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[ I1], тобто назад від позиції S[ I] в рядку можна не повертатися.

Отже, Якщо для кожної позиції j зразка відома найбільша довжина fjj такого початку зразка x[1]x[fj], що збігається з кінцем x[1]x[j], то перше входження зразка знаходиться без повернень у рядку s. Для визначення можливого початку наступного входження треба знати лише F N і продовжувати пошук зновутаки без повернень у рядку! Саме Відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як Om+n, що суттєво менше, ніж Om n. Ми доведемо це далі.

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

Очевидно, F1=0. Нехай всі значення F1, , F J1 уже обчислено, причому F J1= K. Якщо X[ J]= X[ K+1], то кінець рядка X[1] X[ J1] X[ J] збігається з його ж початком довжини K+1, тому F J= K+1. Якщо X[ J] X[ K+1], то наступним кандидатом у кінці рядка X[1] X[ J1] 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[j1];

While x[j] x[k+1] And k0 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[ J1] W J+1, тобто W J= F[ J1] F[ J]+1. Тоді

W2+ W3++ W N F[1] F[2]+1+ F[2] F[3]+1++ F[ N1] F[ N]+1 =

= F[1] F[ N]+ N1 N1.

За кожного J порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу – одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3 N1, тобто прямо пропорційна 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] при J1 міняємо значення J на F[ J1]+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 writelntj+1; j:=f[j] End

Else

Begin t:=t+1; j:=j+1 End

Else { x[j]s[t] }

If tm Then

If j1 Then j:=f[j1]+1 Else t:=t+1

Else t:=t+1

End.

Оцінимо тепер кількість порівнянь символів при виконанні цього алгоритму. Помітимо, що при кожному виконанні тіла циклу збільшується T на 1 або зменшується J принаймні на 1 присвоюванням F[ J] чи F[ J1]+1. Позначимо через B T початкове значення J при черговому значенні T=1, 2, , M, а через W T – кількість зменшень J при відповідному значенні T. Оскільки при збільшенні T значення J або не міняється, або збільшується на 1, то маємо, що B T B T1 W T+1 за T1, звідки W T B T1 B T+1. Тоді

W1+ W2++ W M 1+ B[1] B[2]+1+ B[2] B[3]+1++ B[ M1] B[ M]+1 =

= M+ B[1] B[ M] M+1.

З алгоритму очевидно, що порівнянь символів відбувається рівно стільки, скільки збільшень t та зменшень J разом. Оскільки T збільшується M1 разів, загальна кількість порівнянь символів не більше 2 M, тобто пропорційна M, і оцінюється як O M.

З урахуванням побудови функції відступів загальна кількість порівнянь символів за будьяких рядків довжини M і N оцінюється як O N+ O M, або O M+ N.

ДОДАТОК

Службові слова стандарту мови Паскаль

And	False	Mod	Set
Array	File	Nil	Then
Begin	For	Not	To
Case	Forward	Of	True
Const	Function	Or	Type
Div	Goto	Packed	Until
Do	If	Procedure	Var
Downto	In	Program	While
Else	Label	Record	With
End	Maxint	Repeat

Додаткові слова в Турбо Паскаль

Absolute	Implementation	Object	Unit
Constructor	Inline	Shl	Uses
Destructor	Interface	Shr	Virtual
External	Interrupt	String	Xor