|
|||||
![]() ![]() ![]() ![]() ![]() ![]() ![]() ������������������� ![]() ����������� � �������������� ![]() �������� ���������� ![]() ![]() ![]() ![]() ����: �������� 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 ������ ���������� ����� ������� ��������� (longest repeated substring), ������������ � ������ ������ ����� ������ ����, ����� �������������� ��������� �������. C���� ������� ������������� ��������� � ��� ����� ������� �� ����� ������������ ����� x, ����� ��� y = uxvxw ��� ��������� ����� u, v � w, ��� |u| > 0, |v| > 0 � |w| > 0. ������������ ������������� ��������� � ��� ���������, ������� � ������ ������ �� ������ ���� ��������� ���������, ������ ������������� ������ ���������� �� � ����� �����������. ����������, ��������, ������ PABCQRABCSABTU. ��������� A, B, C, AB, BC � ABC �����������. ������ AB � ABC �������� ������������� �������������� �����������, �, ����� �������, ABC �������� ����� ������� ������������� ����������. ![]() ������� ������ � ������� ���� ������, �������� ��������� ������������ �����, ������� � ���������. �������� ������� M ����������� n * n, ����� ��� Mi,j = 1 ���� yi = yj, � Mi,j = 0 � ��������� ������. �� ����������� ������� ���������, ��� ��������� � �������, ��������� �� ������ ������ `1�, ������������ ������������ ������������� ���������, ����� ������� �� ������� ��������, ����� �������, ����� ������� ������������� ����������. �������� ��������, ��� ������� ����������� ������������ ������� ���������, ������� ���������� ��������� � ������������ ������ ����, ������, �������, �� �������� (�� ���� �������� M1...n-1,i+1...n+1). ![]() ����� ������� ��������. |