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

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

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

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 порівнянь символів буде 128² =16384, хоча більшість їх насправді зайва . Ми переконаємося в цьому, розглянувши далі зовсім інші способи пошуку зразка.

Але спочатку оцінимо зверху кількість порівнянь символів. Зафіксуємо довжину рядка m . Нехай довжина зразка n довільна в межах між 1 та m . Тоді (m -n +1)´ n <m ´ n . Як бачимо, різниця n ² -n між m ´ n та (m -n +1)´ n мала за значень n , близьких до 1, і велика за n , близьких до m . За малих значень n величиною n ² -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 наступним її значен

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать