Наведені обчислення описуються таким алгоритмом (подамо функцію 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). Якщо ж 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).
ДОДАТОК
Службові слова стандарту мови Паскаль
| 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