= 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