UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПошук зразка в рядку (реферат)
Автор
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1480
Скачало205
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

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

 

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

мала за значень 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 підказує, що зразок

не може починатися в рядку з позиції 5-3=2. Отже, за s[n]? x[n] можна

перейти одразу до порівняння x[n] із s[n+(n-p[s[n]])].

 

Якщо s[n]=x[n], то можна порівняти попередні символи рядка з

відповідними символами зразка, рухаючися від його кінця до початку. Якщо

всі відповідні символи рівні, то зразок є підрядком, що починається з

першої позиції рядка. Після цього можна переходити до аналізу другої

-----> Page:

0 [1] [2] [3] [4]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ