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

Реферат з програмування:

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

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
m-n+1 do

if
copy(s, k, n)=x then
writeln(k).

Нагадаємо, що з виклику copy(s, 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
. Як бачимо, різниця n
2
-n
між m
´
n
та (m
-n
+1)´ n
мала за значень n
, близьких до 1, і велика за n
, близьких до m
. За малих значень n
величиною n
2
-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 підказує, що зразок не може починатися в рядку з позиції 5-3=2. Отже, за s
[n
]¹ x
[n
] можна перейти одразу до порівняння x
[n
] із s
[n
+(n
-p
[s
[n
]])].

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

Якщо за деякого k
>0 s
[k
]¹ x
[k
], то серед x
[k
-1], … , 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+(n-p[s[n]])

else

begin

k:=n-1; ok:=true
;

while
(k>0) and
ok do

if
x[k]=s[last-n+k] then
k:=k-1 else
ok:=false
;

if
k=0 then
{s[last-n+1]…s[last]=x
}

begin

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

last:=last+1

end else

begin

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

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

last:=last+(k-j)

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
[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
[k
1
] зразка, що збігається з кінцем x
[1]…x
[k
] (і з кінцем s
[1]…s
[i
-1]), і порівняти x
[k
1
+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