����� �� �����.


������ ���������.

����� � �������, ��������, �������������������:
�������� �����.

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. �� ����������� ���� ������� ��������� ������������ ����� ������, ��� � ������ ������� ��������� ������� � ��������� �� ���� ��������, ������������ � y4y11, � ������, ��������� triptrap.

 

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: ����� ������� x1yr+1 ���������, ������� p � ������ ������������� �������������� ����������� ������������ ����� �������� � �������, �� ���� yp =/=xp-r, � ��� ������������ ����� v, ��� q < v < k+1, �� ���� p - r = tm[r, v].

B: ��� ���� ����� �������, �� ������� ������������ ���� ����� i - r, ����������� � ������� ���, ��� �� ��������� ������� �����, ��������������, ��� yr+1yi+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-rxp-r = xp-i, ������ yp = xp-i. ��� ������������� ���������� ������ ������ � �������� �������, ��� ��� ����, ��� � ���� ������� ��� ���������.

������ 2: ����������� ������ ���� �� �������, �� ���� ���� ������� A, ���� ������� B, �� �� ��� �����. � ����� ������ yp =/=xp-i. ���� ���� ������� A �������, �� yp =/=xp-rxp-r = xp-i, ������ yp =/=xp-i. � ������ �������, ���� ��������� ������ ������� B, �� yp = xp-rxp-r =/=xp-i, � �����, yp =/=xp-i. ��� � � ���������� ������, ��� ������������� ���������� ������ ������ � �������� �������, ��� ��� ��������, ��� ��� �� ���������.

������ 3: ����������� ��� ������� � � ������� A, � ������� B. � ���� ������ �� ������ �� ����� ������� � ���, ��������� �� ������� ypxp-i, ������� �� ���� ��������.

� ������ 2, ��� ���� � ������ 3 �������� ������������ ��������, ���������� ��������� ���������� ������������ �������� b �� ������� � �������� tm[i, b] � ��������� merge.

������ ������ ��������� merge, �������������� �� ������� 27. ��� ����������� �����, ���������������� ���������� ������� ��� merge �������� tm[i-r, 1�t]tm[r, q�k+1]. ���������� uv � ������ ��������������� ������� �������� ������ ��������� ���� ���� ��������, ��������������, � ��������������� ������������� �������������� ��������� �����������.

������� ��������� ������ ��������� ���������. �� ������, ���� 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] > jtm[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 ������������ ����� ������� � ��������.

������ ��������� ������� ������� �� ������ ������. ���� ��������� ������ �������� mergeextend, ������ �� 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). ���� �� ������� ����� ������ �������� mergeextend, ������ �������� ������� �������������� �������. ��� ���� �������� �� ���� s ��������� extend ��������� ����� O(m). ����� ���� ��������, ��� ����� ������ merge ��������������� ����� ������� ������������. ����� �������, ������ ����� merge �������� ����� , ��� ����� . ����� �������, ����� ����� ��� ������ s ����� =O(km). ������� ������������ �� ���� �������, �������� ����� ����� ����� . ����� �������, ����� ������� �������, ���������� ��������������� ��������� ������� � ������ ������, ����� O(k(n + m log m)).





SpyLOG