Пошук зразка в рядку, Детальна інформація
Пошук зразка в рядку
Тип документу: Реферат
Сторінок: 6
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 17
Скачувань: 937
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
СПИСОК ЛІТЕРАТУРИ
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021