Пошук зразка в рядку
Пошук зразка в рядку
Тип документу: Реферат
Сторінок: 6
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 17
Скачувань: 1162
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
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)\xF0A3 b(t-1)-w(t)+1 за t>1, звідки w(t)\xF0A3 b(t-1)-b(t)+1. Тоді
w(1)+w(2)+…+w(m) \xF0A3 1+b[1]-b[2]+1+b[2]-b[3]+1+…+b[m-1]-b[m]+1 =
= m+b[1]-b[m] \xF0A3 m+1.
З алгоритму очевидно, що порівнянь символів відбувається рівно стільки, скільки збільшень t та зменшень j разом. Оскільки t збільшується m-1 разів, загальна кількість порівнянь символів не більше 2m, тобто пропорційна m, і оцінюється як O(m).
З урахуванням побудови функції відступів загальна кількість порівнянь символів за будь-яких рядків довжини m і n оцінюється як O(n)+O(m), або O(m+n).
ДОДАТОК
Службові слова стандарту мови Паскаль
e
else label record with
end maxint repeat
Додаткові слова в Турбо Паскаль
absolute implementation object unit
constructor inline shl uses
destructor interface shr virtual
external interrupt string xor
СПИСОК ЛІТЕРАТУРИ
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
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)\xF0A3 b(t-1)-w(t)+1 за t>1, звідки w(t)\xF0A3 b(t-1)-b(t)+1. Тоді
w(1)+w(2)+…+w(m) \xF0A3 1+b[1]-b[2]+1+b[2]-b[3]+1+…+b[m-1]-b[m]+1 =
= m+b[1]-b[m] \xF0A3 m+1.
З алгоритму очевидно, що порівнянь символів відбувається рівно стільки, скільки збільшень t та зменшень j разом. Оскільки t збільшується m-1 разів, загальна кількість порівнянь символів не більше 2m, тобто пропорційна m, і оцінюється як O(m).
З урахуванням побудови функції відступів загальна кількість порівнянь символів за будь-яких рядків довжини m і n оцінюється як O(n)+O(m), або O(m+n).
ДОДАТОК
Службові слова стандарту мови Паскаль
e
else label record with
end maxint repeat
Додаткові слова в Турбо Паскаль
absolute implementation object unit
constructor inline shl uses
destructor interface shr virtual
external interrupt string xor
СПИСОК ЛІТЕРАТУРИ