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

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).

ДОДАТОК

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

andfalsemodset

arrayfilenilthen

beginfornotto

caseforwardoftrue

constfunctionortype

divgotopackeduntil

doifprocedurevar

downtoinprogramwhile

elselabelrecordwith

endmaxintrepeat

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

absoluteimplementationobjectunit

constructorinlineshluses

destructorinterfaceshrvirtual

externalinterruptstringxor