Сторінка
2

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

= 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). Якщо ж j<n, то переходимо до наступної пари символів, збільшивши t і j на 1. За нерівності s[t] і x[j] при j>1 міняємо значення 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 t<m then if j>1 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).

ДОДАТОК

Службові слова стандарту мови Паскаль

Додаткові слова в Турбо Паскаль

СПИСОК ЛІТЕРАТУРИ

[Аб] Абрамов А.С. Элементы анализа программ.- М., 1986.

[АГКС]Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию.- М., 1988.

[Ан] Андерсон Р. Доказательство правильности программ.- М.:, 1982.

[Арс] Арсак Ж. Программирование игр и головоломок.- М., 1990.

[АУ] Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1.- М., 1978.

[АХУ] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М., 1979.

[БаГо] Бауэр Ф., Гооз Г. Информатика.- М., 1990.

[Белл] Беллман Р. Динамическое программирование. М., 1960.

[БВК] Бородич Ю.С., Вальвачев А.Н., Кузьмич А.И. Паскаль для персональных компьютеров.-Минск., 1991.

[Бу] Бублик В.В. Методические указания и задания к лабораторным занятиям по курсу "Вычислительные машины и программирование".- Киев, 1986.