Пошук зразка в рядку, Детальна інформація
Пошук зразка в рядку
\x00A8
\x00AA
oe
o
u
ue
X
Z
\x0161
\x0153
1/4
3/4
V) і продовжувати пошук знову-таки без повернень у рядку! Саме відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як O(m+n), що суттєво менше, ніж O(m\xF0B4 n). Ми доведемо це далі.
Функція f(j), що виражає довжину такого найдовшого початку рядка x[1]…x[j], що є водночас його кінцем, називається функцією відступів. Вона показує, до якого символу x[f(j)] треба відступити в зразку, коли x[j+1] не збігається з черговим символом рядка, щоб продовжувати пошук із порівняння чергового символу з символом x[f(j)+1]. Цей відступ рівносильний зсуву рядка на найменшу можливу кількість позицій j-f(j). Займемося тепер обчисленням цієї функції за зразком.
Очевидно, f(1)=0. Нехай всі значення f(1), … , f(j-1) уже обчислено, причому f(j-1)=k. Якщо x[j]=x[k+1], то кінець рядка x[1]…x[j-1]x[j] збігається з його ж початком довжини k+1, тому f(j)=k+1. Якщо x[j]\xF0B9 x[k+1], то "наступним кандидатом у кінці" рядка x[1]…x[j-1]x[j] є рядок x[1]…x[f(k)]x[f(k)+1], оскільки саме x[1]…x[f(k)] є найдовшим кінцем x[1]…x[k]. Якщо й він не годиться, то наступним є x[1]…x[f(f(k))+1] тощо. Отже, ми або знайдемо початок довжини p, такий, що x[1]…x[p] є кінцем x[1]…x[j], і тоді f(j)=p, або не знайдемо, і f(j)=0.
Наведені обчислення описуються таким алгоритмом (подамо функцію 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) \xF0A3 f[1]-f[2]+1+f[2]-f[3]+1+…+f[n-1]-f[n]+1 =
= f[1]-f[n]+n-1 \xF0A3 n-1.
За кожного j порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу – одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3(n-1), тобто прямо пропорційна n. Таким чином, загальну кількість порівнянь символів при побудові функції відступів можна оцінити як O(n).
Тепер, нарешті, наведемо алгоритм пошуку входжень зразка в рядок. Нехай t позначає номер поточної позиції в рядку, j – номер поточної позиції в зразку, спочатку вони рівні 1. Далі, поки t\xF0A3 m, виконуємо наступні дії. Порівнюємо символи x[j] і s[t]. Якщо вони рівні, маємо входження x[1]…x[j] в кінці рядка s[1]…s[t]. Якщо при цьому j=n, то можна повідомити про входження зразка починаючи з позиції t-j+1 і приступати до пошуків наступного входження, поклавши j=f(n). Якщо ж j1 міняємо значення j на f[j-1]+1, а при j=1 збільшуємо t на 1. Втім, зміни j не мають сенсу, коли t=m. Ось і все. Наведемо цей алгоритм також і в мові Паскаль:
\x00AA
oe
o
u
ue
X
Z
\x0161
\x0153
1/4
3/4
V) і продовжувати пошук знову-таки без повернень у рядку! Саме відсутність повернень у рядку дозволяє оцінити загальну кількість порівнянь як O(m+n), що суттєво менше, ніж O(m\xF0B4 n). Ми доведемо це далі.
Функція f(j), що виражає довжину такого найдовшого початку рядка x[1]…x[j], що є водночас його кінцем, називається функцією відступів. Вона показує, до якого символу x[f(j)] треба відступити в зразку, коли x[j+1] не збігається з черговим символом рядка, щоб продовжувати пошук із порівняння чергового символу з символом x[f(j)+1]. Цей відступ рівносильний зсуву рядка на найменшу можливу кількість позицій j-f(j). Займемося тепер обчисленням цієї функції за зразком.
Очевидно, f(1)=0. Нехай всі значення f(1), … , f(j-1) уже обчислено, причому f(j-1)=k. Якщо x[j]=x[k+1], то кінець рядка x[1]…x[j-1]x[j] збігається з його ж початком довжини k+1, тому f(j)=k+1. Якщо x[j]\xF0B9 x[k+1], то "наступним кандидатом у кінці" рядка x[1]…x[j-1]x[j] є рядок x[1]…x[f(k)]x[f(k)+1], оскільки саме x[1]…x[f(k)] є найдовшим кінцем x[1]…x[k]. Якщо й він не годиться, то наступним є x[1]…x[f(f(k))+1] тощо. Отже, ми або знайдемо початок довжини p, такий, що x[1]…x[p] є кінцем x[1]…x[j], і тоді f(j)=p, або не знайдемо, і f(j)=0.
Наведені обчислення описуються таким алгоритмом (подамо функцію 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) \xF0A3 f[1]-f[2]+1+f[2]-f[3]+1+…+f[n-1]-f[n]+1 =
= f[1]-f[n]+n-1 \xF0A3 n-1.
За кожного j порівнянь символів відбувається на 2 більше, ніж виконань тіла циклу – одне додаткове при обчисленні умови в заголовку циклу і одне в умовному операторі. Звідси загальна кількість порівнянь символів не більше 3(n-1), тобто прямо пропорційна n. Таким чином, загальну кількість порівнянь символів при побудові функції відступів можна оцінити як O(n).
Тепер, нарешті, наведемо алгоритм пошуку входжень зразка в рядок. Нехай t позначає номер поточної позиції в рядку, j – номер поточної позиції в зразку, спочатку вони рівні 1. Далі, поки t\xF0A3 m, виконуємо наступні дії. Порівнюємо символи x[j] і s[t]. Якщо вони рівні, маємо входження x[1]…x[j] в кінці рядка s[1]…s[t]. Якщо при цьому j=n, то можна повідомити про входження зразка починаючи з позиції t-j+1 і приступати до пошуків наступного входження, поклавши j=f(n). Якщо ж j
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021