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

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+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].