WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Пошук зразка в рядку - Реферат

Пошук зразка в рядку - Реферат

збігається з його ж початком довжини k+1, тому f(j)=k+1. Якщо x[j] x[k+1], то "наступним кандидатом у кінці" рядка x[1]…x[j-1]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[j-1];
while (x[j] x[k+1]) and (k>0) 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[j-1]-w(j)+1, тобто w(j)<=f[j-1]-f[j]+1. Тоді
w(2)+w(3)+…+w(n) f[1]-f[2]+1+f[2]-f[3]+1+…+f[n-1]-f[n]+1 =
= f[1]-f[n]+n-1 n-1.
За кожного j порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу - одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3(n-1), тобто прямо пропорційна 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). Якщо ж j1 міняємо значення j на f[j-1]+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 writeln(t-j+1); j:=f[j] end
else
begin t:=t+1; j:=j+1 end
else { x[j]s[t] }
if t1 then j:=f[j-1]+1 else t:=t+1
else t:=t+1
end.
Оцінимо тепер кількість порівнянь символів при виконанні цього алгоритму. Помітимо, що при кожному виконанні тіла циклу збільшується t на 1 або зменшується j принаймні на 1 присвоюванням f[j] чи f[j-1]+1. Позначимо через b(t) початкове значення j при черговому значенні t=1, 2, …, m, а через w(t) - кількість зменшень j при відповідному значенні t. Оскільки при збільшенні t значення j або не міняється, або збільшується на 1, то маємо, що b(t) b(t-1)-w(t)+1 за t>1, звідки w(t) b(t-1)-b(t)+1. Тоді
w(1)+w(2)+…+w(m) 1+b[1]-b[2]+1+b[2]-b[3]+1+…+b[m-1]-b[m]+1 =
= m+b[1]-b[m] m+1.
З алгоритму очевидно, що порівнянь символів відбувається рівно стільки, скільки збільшень t та зменшень j разом. Оскільки t збільшується m-1 разів, загальна кількість порівнянь символів не більше 2m, тобто пропорційна 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
СПИСОК ЛІТЕРАТУРИ
[Аб] Абрамов А.С. Элементы анализа программ.- М., 1986.
[АГКС]Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию.- М., 1988.
[Ан] Андерсон Р. Доказательство правильности программ.- М.:, 1982.
[Арс] Арсак Ж. Программирование игр и головоломок.- М., 1990.
[АУ] Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1.- М., 1978.
[АХУ] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М., 1979.
[БаГо] Бауэр Ф., Гооз Г. Информатика.- М., 1990.
[Белл] Беллман Р. Динамическое программирование. М., 1960.
[БВК] Бородич Ю.С., Вальвачев А.Н., Кузьмич А.И. Паскаль для персональных компьютеров.-Минск., 1991.
[Бу] Бублик В.В. Методические указания и задания к лабораторным занятиям по курсу "Вычислительные машины и программирование".- Киев, 1986.
[Ви77] Вирт Н. Систематическое программирование. Введение.- М., 1977.
[Ви85] Вирт Н. Алгоритмы + Структуры данных = Программы.- М., 1985.
[Григ] Григорьев В.Л. Микропроцессор i486.- М., 1993.
[Грис] Грис Д. Наука программирования.- М., 1984.
[Гро] Грогоно П. Программирование на языке Паскаль.- М., 1982.
[ГД] Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи. - М., 1982.
[ЙеВи]Йенсен К., Вирт Н. Паскаль. Руководство для пользования.- М., 1993.
[КаСа] Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ.- М., 1986.
[Кнут] Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы.- М., 1976. Т. 1. Получисленные алгоритмы.- М., 1977. Т. 2. Сортировка и поиск.- М., 1978. Т. 3.
[М80] Майерс Г. Надежность программного обеспечения.- М., 1980.
[М82] Майерс Г. Искусство тестирования программ.-М., 1982.
[ПоКр]Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль. Версия 5.5. М., 1992.
[Пи] Пильщиков В.Н. Сборник упражнений по языку Паскаль.-М., 1989.
[ПрЧС]Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі.- К., 1993.
[РНД] Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М., 1980
[Сл] Слэйгл Дж. Искусственный интеллект. М.: Мир, 1973.
[СтКо] Ставровський А.Б., Коваль Ю.В. Вступний курс програмування.- К., 1998.
[Фар] Фаронов В.В. Турбо Паскаль 7.0. Начальный курс.- М., 1997.
[Фор] Форсайт Р. Паскаль для всех.- М., 1987.
[BoMo]Boyer R.S., Moore J.S. A fast string searching algorithm.- Comm.ACM, 1977.- № 10
[MorPr]Morris J.H. Jr, Pratt V.R. A linear pattern matching algorithm.- Tech.Rept. 40, Comput. Centre, University of California, Berkeley.- 1970
Loading...

 
 

Цікаве