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



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

����������

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

������ ���������� � �����������. �RC

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

����� � �������, ��������,
�������������������


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


C�������� ������.
�������� ����������


AI, ��, ��������� ����

��������

����, � ��� � ���� ���������

������


����: �������� PS � PDF ������

   �������� ���-�������
   �������� ������� �����

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

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

C����� x ����� |x| = m ������������ ��� x1x2 ... xm, ��� xi ������������ i-� ������ x.

�������� xixi+1 ... xj ������ x, ��� i<=j<=m, ����� ������������ x(i,j). � ������, ����� i>j, ���������� ��������� ������������ ��� xR(i,j).

����� x ����� ���������� ������� �������, � y � ��������� ������; |x| = m, |y| = m �, �������, m<=n.

������:

x = trismegistus
|x| = 12
x(7,10) = gist
xR(7,4) = gems

������ ���������� ����� ������� ��������� (longest repeated substring), ������������ � ������ ������ ����� ������ ����, ����� �������������� ��������� �������.

��� ������ ������ y, |y| = n > 0, ����� ����� ������� ���������, ������������� � y ������ ������ ����.
C���� ������� ������������� ��������� � ��� ����� ������� �� ����� ������������ ����� x, ����� ��� y = uxvxw ��� ��������� ����� u, vw, ��� |u| > 0, |v| > 0|w| > 0.

������������ ������������� ��������� � ��� ���������, ������� � ������ ������ �� ������ ���� ��������� ���������, ������ ������������� ������ ���������� �� � ����� �����������. ����������, ��������, ������ PABCQRABCSABTU. ��������� A, B, C, AB, BCABC �����������. ������ ABABC �������� ������������� �������������� �����������, �, ����� �������, ABC �������� ����� ������� ������������� ����������.

������� ������
������ ������ � ������� ���� ������, �������� ��������� ������������ �����, ������� � ���������. �������� ������� M ����������� n * n, ����� ��� Mi,j = 1 ���� yi = yj, � Mi,j = 0 � ��������� ������. �� ����������� ������� ���������, ��� ��������� � �������, ��������� �� ������ ������ `1�, ������������ ������������ ������������� ���������, ����� ������� �� ������� ��������, ����� �������, ����� ������� ������������� ����������. �������� ��������, ��� ������� ����������� ������������ ������� ���������, ������� ���������� ��������� � ������������ ������ ����, ������, �������, �� �������� (�� ���� �������� M1...n-1,i+1...n+1).


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





����� �� ��������, � ���������� � ���������

SpyLOG