|
����� � �������, ��������, �������������������:
�������� �����.
k ������������ � ������-������
� ��������� k ������������ ������-������� (1985, 1986a) ������ ������ ������������� � ������� 2-������ ������� ������������ ������� (pattern mismatch) pm[1�m-1, 1�2k+1], ������������ �� ������ ��������������� ��������� �������. ���������� ���� ������� ����� ����������� ���� ����. ������� �� ���������� ������ ������� ������.
��� ������� ������ ������������ ��������� ������ tm[0�n-m, 1�k+1], ���������� ���������� � ������������� ������ � ��������. �� ���������� ������� � ��� i-� ������ ���������� ������� � x ������ k+1 ������������ ����� �������� x(1, m) � y(i+1, i+m). ����� �������, ���� tm[i, v] = s, �� yi+s =/=xs, � ��� v-� ������������ ����� x(1, m) � y(i+1, i+m), ������ ����� �������. ���� ����� c ������������ x � ���������� y(i+1, i+m) ������ k+1, ��, ������� � c+1, �������� i-� ������ ����� �������� �� ��������� m+1, �� ����:
tm[i, c+1] = tm[i, c+2] = � = tm[i, k+1] = m+1
�������� ��������: ���� tm[i, k+1] = m+1, �� ��������� y(i+1, i+m) ���������� �� ������� x �� �����, ��� �� k ��������, �, ����� �������, �������� �������� ������. ��� �������������� ��������� ��������. ���������� ������, ����� x = tram, y = thetrippedtrap, � k = 2. �� ����������� ���� ������� ��������� ������������ ����� ������, ��� � ������ ������� ��������� ������� � ��������� �� ���� ��������, ������������ � y4 � y11, � ������, ��������� trip � trap.
|
1 |
2 |
3 |
0 |
2 |
3 |
4 |
1 |
1 |
2 |
3 |
2 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
4 |
1 |
2 |
3 |
5 |
1 |
2 |
3 |
6 |
1 |
2 |
3 |
7 |
1 |
2 |
3 |
8 |
1 |
2 |
3 |
9 |
1 |
2 |
3 |
10 |
4 |
5 |
5 |
�������� ������� ������ �������� �� ������� 25. ������� ����������� � ����� for ����������� � ������� ����� �� ����� �� ������ ������� �� ���. �� �������� i � �������� ������������ ��������� y(i+1, i+m). ����� ������ ������� � ������, ����������� �� ���������� ��������, �������� ��������� j, �� ���� j �������� ������������ �� ����� r+tm[r, k + 1], ��� 0 < r < i. ���� i < j, ���������� ��������� merge, ������� ������� ������������ ����� x(1, j - i) � y(i+1,j) � ������������� b ������ ���������� �����. ���� ��� �� ��������� k, ���������� ��������� extend. ��� ��������� ����� ������� �� y[j + 1], ���� ���� �� ����� ������� k + 1 ������������, ���� �� ����� ���������� y[i+m] � �� ������ ��� k ��������������, �� ���� ������� ��������� �������, ������������ � y[i+1].
���������� extend �������� ��������, ����� ��������� �������� �� ������� 26. ������������ ���� �������� �� �������� y(j + 1, i + m) � x(j - i + 1, m), � � ������ ������������ b ������������� � ������� ��������� ������������ �����������.
- �������������
tm[0 ... n - m, 1 ... k + 1] = m + 1
r = 0
j = 0
- ������������ ������
for i = 0 to n - m
b = 0
if i < J
merge(I, R, J, B)
IF B < K + 1
R=I
extend(I, J, B)
���. 25: ������������� ����� �� ������-�������
extend(i, j, b)
while (b < K + 1) AND (J - I < M)
J = J + 1
IF Yj =/=xj-i
b = b + 1
tm[i, b] = j - i
���. 26: ��������� extend
������ ��������� ������ ��������� merge. ��� ����������� �����, ��� ��������� ������� ������������ ����� x(1, j-1) � y(i+1, j) � ������������� b ������ ���������� �����. ����� �������, merge ��������� tm[i, 1 ... b] ��� b < k+1, � ������� ��� ���� ������������ ���������� ����� ����������. ��-������, ��������, ��� ������ r ������� ������������ ��������� � �������������, ���������� ��� ���������� ������ ������� � yr+1, � r+tm[r, k+1] �������� ������� ����� ����� ������ �� ����������� �� ��������� ������ ������� ������. ������� ������������ ������ �� yi, ���������� � ������� ���������� � r-� ������ tm, ������� ���� �� ��������� ��� ��������� ������� � �������, ������������ � yi+1. ����������� ���������� �� ������� ������������ ��������, ����� �������, tm[r, q ... k+1], ��� q � ��� ���������� �� ����� �����, ��� ������� r+tm[r, q] > i. ������, ������� ��������� ��� ����, ��� ��� ������������ ������������� ������ �������, �������������� � yr+1, � �� ����� ��� ������� ������� ������� ��������� � yi+1 � ������� � i - r ����.
������ ���������� ������������ � merge ���������� ��������, ����� �������, �������������� ����������� ������� pm ������������, ������ ������� ������������ ������� � ����� ����� ��� ��������� �������. ������ i ������� pm[1�m-1, 1 ... 2k+1] �������� ������� ������ x ������ 2k+1 ������������ ����� ����������� x(1, m-i) � x(i+1, m), �� ���� ���������������� �������� ���� ����� ������� ��� ���������������� ������ i. ����� �������, ���� pm[i, u] = s, �� xi+s =/=xs, � ��� u-� ������������ ����� x(1, m-i) � x(i+1, m) ����� �������. ���� ����� c ������������ ����� ����� �������� ������ 2k+1, ��, ������� � c+1, �������� i-� ������ ����� m+1, �������� �� ���������, �� ����:
pm[i, c+1] = pm[i, c+2] = � = pm[i, 2k+1] = m+1
����� �������, ��� merge ������� ������������ ������ i - r ������� ������������, ������ ������������ �������� pm[i-r, 1�t], ��� t � ����� ������ ������������ � pm[i-r, 1�2k+1], �����, ��� pm[i-r, t] < j-i+1, ��� ��� ��������� ������ ������������ � ��������� x(1, j-i).
����� ������, ��� ���������� ���������� ����� �������������� � ��������� merge, ���������� � ������ ������� p, ����������� � ��������������� ���������, i+1 < p < j. ������� p ����� ������������� ��� �� ������������� ������ �� ����������� ���� �������.
A: ����� ������� x1 � yr+1 ���������, ������� p � ������ ������������� �������������� ����������� ������������ ����� �������� � �������, �� ���� yp =/=xp-r, � ��� ������������ ����� v, ��� q < v < k+1, �� ���� p - r = tm[r, v].
B: ��� ���� ����� �������, �� ������� ������������ ���� ����� i - r, ����������� � ������� ���, ��� �� ��������� ������� �����, ��������������, ��� yr+1 � yi+1, ������� p ������������� ������������ ����� ����� ���������, �� ���� xp-r =/=xp-i. ��� u-� ������������ ��� ���� ������, ��� 1 < u < t, �� ���� p-i = pm[i-r, u].
��������, ��� ��� ����������, ��������� �� ������ ������ � ������� p � ���������������� �������� �������, ����� x1 �������� � yi+1, �� ���� ����� ��, ��� yp = xp-i. ���������� ���� ������ ��� ������ ����������� ��������� ���� �������.
������ 1: �� ����������� �� ������� A, �� ������� B. �� ����, yp = xp-r � xp-r = xp-i, ������ yp = xp-i. ��� ������������� ���������� ������ ������ � �������� �������, ��� ��� ����, ��� � ���� ������� ��� ���������.
������ 2: ����������� ������ ���� �� �������, �� ���� ���� ������� A, ���� ������� B, �� �� ��� �����. � ����� ������ yp =/=xp-i. ���� ���� ������� A �������, �� yp =/=xp-r � xp-r = xp-i, ������ yp =/=xp-i. � ������ �������, ���� ��������� ������ ������� B, �� yp = xp-r � xp-r =/=xp-i, � �����, yp =/=xp-i. ��� � � ���������� ������, ��� ������������� ���������� ������ ������ � �������� �������, ��� ��� ��������, ��� ��� �� ���������.
������ 3: ����������� ��� ������� � � ������� A, � ������� B. � ���� ������ �� ������ �� ����� ������� � ���, ��������� �� ������� yp � xp-i, ������� �� ���� ��������.
� ������ 2, ��� ���� � ������ 3 �������� ������������ ��������, ���������� ��������� ���������� ������������ �������� b �� ������� � �������� tm[i, b] � ��������� merge.
������ ������ ��������� merge, �������������� �� ������� 27. ��� ����������� �����, ���������������� ���������� ������� ��� merge �������� tm[i-r, 1�t] � tm[r, q�k+1]. ���������� u � v � ������ ��������������� ������� �������� ������ ��������� ���� ���� ��������, ��������������, � ��������������� ������������� �������������� ��������� �����������.
������� ��������� ������ ��������� ���������. �� ������, ���� b = k+1, �� ��� ������, ����� ������ ���������� ������������ ������ ���, ��� x1 �������� � yi+1, ���������� k+1 ������������, ������� �� ��������� ����� �����. �� ������, ��������, ��� ����� ������ �� ������������ ��� ������� � merge, � ������, j, ����� r+tm[r, k+1], ���� v = k+2, ������� tm[r, k+1] ����� ��� ������������ ��� ����������� �������� v, � ������, v = k+1, � ������� ������� j ������ ���� ���������. �������������, � ���� ������ ����� ����� ����� �� ���������. �������, ��������� ����� ��������, ���� i+pm[i-r, u] > j � tm[r, v] = m+1. ���� ����������� ������ ����� ����� �������, �� r+tm[r, v] ��������� j, � ������������� ������ ��� ����������� �������� v ������ �� k+1. � ���� ������ ��������� ����� ���� ��������, ���� ����������� ����� ������ ����� ������������ �������, ��� ��� ��� ���������, ��� ������� ������ j ���������� ���������.
�������� ��������, ��� ����� ������� ������������ � ������� ������������ ������� ���������� ��� ����, ����� merge ����� ���, ���, ���� �� ������ k+1, ������ k+1 ������������ ��� y(i+1, j). ��� ����� �������� ��������� �������. ������� A ����������� �� ������ ��� ��� k+1 ������� ������ � ��������� [i+1, j]. ������� B ����������� ��� ���������� ������������ ����� ������� � ���� �� ���������. ������ i-r � ������� ������������ �������, tm[i-r, 1 ... 2k+1], �������� �� ������ ��� 2k+1 ������� ������������ ����� ����� ������� �������, � ��������������� ������� i-r. ���� pm[i-r, 2k+1] > j - i, �� ������� �������� ��� ������� ������������ ������� ����� � �����, � ������� ������� B ����������� ��� ������� ������ � ��������� [i+1, j]. � ������ �������, ���� pm[i-r, 2k+1] < j-i, �� ������� ����� ���� 2k+1 ������� ������ � ��������� [i+1, j-1], ��� ������� ����������� ������� B. ��������� j = r+tm[r, k+1], � ��������� [i+1, j-1] ������� �� k ������� ������, ��� ������� ����������� ������� A. ����� �������, � ������ ������ ����� ���� k �������, ��� ������� ����� ����� ������ 3, � ������� ��������� �������� ��������. �������� �� ������� ���� k+1 �������, ��������������� ������� B, �� �� ������� A (������ 2), ��� �������� �����������, ����� ���������, ��� ��� ������� ��������� ������� ������������ ������ ������� �� ������ k+1 ������������ ����� ������� � ��������.
������ ��������� ������� ������� �� ������ ������. ���� ��������� ������ �������� merge � extend, ������ �� n-m+1 �������� ����� ������� ������ ����������� �� ������������� �����, ��� ���� � ����� ��������� ����� O(n). ����� ����� ��������, ����������� ���������� extend �� ����� ������� ����� O(n), ��� ��� ��� ��������� ������ ������ ������ �� ������ ������ ����. ��������� merge ��� ������ ������ ������������ ������� pm[i-r, 1 ... 2k+1] � tm[r, 1�k+1], ������� � ����� ����� 3k+2 ���������. ����� ������ merge ����� ����������, �������� �������� � ������������� �������� � ������ �� ���� ������, ��� ���� ����� ����� ��� ������� ������, ������ O(k). ����� �������, ����� ������, ��� ����� ����� ������� ������ ���������� O(nk).
merge(i, r, j, b)
u = 1
v = q
while (b < K + 1) AND (V < K + 2)
AND (I + PM[I - R, U] < j or tm[r, v] =/=m + 1)
if i + pm[i - r, u] > r + tm[r, v]
- ������ 2, ������� A
b = b + 1
tm[i, b] = tm[r, v] - (i - r)
v = v + 1
else if i + pm[i - r, u] < R + TM[R, V]
- ������ 2, ������� B
B = B + 1
TM[I, B] = PM[I - R, U]
U = U + 1
else
- I + PM[I - R, U] = R + TM[R, V]
- ������ 3
IF Xpm[i-r,u] =/=yi+pm[i-r,u]
b = b + 1
tm[i, b] = pm[i - r, u]
u = u +1
v = v + 1
������� 27: ��������� merge ������-�������
- �������������
r = 2l-1
j = 2l-1
- ���������� ����� pm � ��������� l
for i = 2l-1 to 2l - 1
b = 0
if i < J
merge(I, R, J, B)
IF
r = i
extend(i, j, b)
������� 28: ��������������� ��������� ������� ������-�������
������ �������� ������ ���������� � ���������� ������� ������������ ������� �� ������ ��������������� ����������. �� ����� ��������, ����� ������������, ��� m �������� ��������� �������� 2. � ��������� ��������������� ��������� ������������ ��������� ��������� {1, 2, ... , m-1} �� m-1 ����� pm �� ��������� log2m �����������:
{1}, {2, 3}, {4, 5, 6, 7}, ... , {m/2, ... , m-1}
�������� ������� �� log2m ������. �� ����� s, ��� 1 < s < log2m, ����������� ������ pm � ��������� s, ��� ��������� s � ��� {2s-1, ... , 2s-1}.
�����, ������������ ��� ���������� ���� �������, ������� �� ������, ������������ �� ������ ������� ������, �������� ��� ����� s �������� �� ������� 28. �� ������ s ������� ��� ��������� ������� ������� �������� ��������� ������� x(1, m-2s-1) � x(2s-1+1, m), ������� ���������� �����, ��������������, ��� ������� � �����, � ������ pm[1�2s-1-1, 1�min{2log(m)-s4k+1, m-2s-1}], ���������� ������ ���������� l - 1 ������. (����� ��������� � ������� ���������� ����� ��������� �����). ������ ������ s �������� �. �� ����������� ������ log2m, �� ������� ������� �� 2k+1 ������������, �� ������ s ��� ������ ������ pm ��������� ����� �� min{2log(m)-s2k+1, m-2s} ������������, � �� �� k+1, ��� � ��������� ������� ������.
��������� ���������, ����������� ������������� ��� �������� ������������ ��������� merge, ����� ��������, ��� ��� ���������� ���������� ���������� ������������ �� ������ s ��������� min{2log(m)-s4k+1, m-2s} �������, ��� ������� ����������� ������� B, � � ������ ������, � ������, �� ������ log2m, ��������� 4k + 1 ����� �������.
�� ������ ������ s �� log2m ������ ������� ������� ���� for ���������� 2s-1 �������� (2s-1 < i < 2s - 1). ���� �� ������� ����� ������ �������� merge � extend, ������ �������� ������� �������������� �������. ��� ���� �������� �� ���� s ��������� extend ��������� ����� O(m). ����� ���� ��������, ��� ����� ������ merge ��������������� ����� ������� ������������. ����� �������, ������ ����� merge �������� ����� , ��� ����� . ����� �������, ����� ����� ��� ������ s ����� =O(km). ������� ������������ �� ���� �������, �������� ����� ����� ����� . ����� �������, ����� ������� �������, ���������� ��������������� ��������� ������� � ������ ������, ����� O(k(n + m log m)).
| |