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

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

����� - Eppstein.
������� � ����������� ������ �.

    subseq(char * P, char * T)

    {

        while (*T != '\0')

            if (*P == *T++ && *++P == '\0')

                return TRUE;

        return FALSE;

    }

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

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

    n e m a t o d e [������] k n o  w  l e d g e

      | |   |          |         |     | |

      e m p t y     [������]   b o t t l e

����������� �������:

    int lcs_length(char * A, char * B)

    {

	if (*A == '\0' || *B == '\0') return 0;

	else if (*A == *B) return 1 + lcs_length(A+1, B+1);

	else return max(lcs_length(A+1,B), lcs_length(A,B+1));

    }

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

    char * A;

    char * B;

    int lcs_length(char * AA, char * BB)

    {

	A = AA; B = BB;

	return subproblem(0, 0);

    }

    int subproblem(int i, int j)

    {

	if (A[i] == '\0' || B[j] == '\0') return 0;

	else if (A[i+1] == B[j+1]) return 1 + lcs_length(i+1, j+1);

	else return max(lcs_length(i+1, j), lcs_length(i, j+1));

    }

    char * A;

    char * B;

    array L;


    int lcs_length(char * AA, char * BB)

    {

	A = AA; B = BB;

	allocate storage for L;

	for (i = 0; i <= m; i++)

	    for (j = 0; j <= m; j++)

		L[i,j] = -1;


	return subproblem(0, 0);

    }


    int subproblem(int i, int j)

    {

	if (L[i,j] < 0) {

	    if (A[i] == '\0' || B[j] == '\0') L[i,j] = 0;

	    else if (A[i+1] == B[j+1]) L[i,j] = 1 + lcs_length(i+1, j+1);

	    else L[i,j] = max(lcs_length(i+1, j), lcs_length(i, j+1));

	}

	return L[i,j];

    }

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

������������ LCS ( Longest Common Subsequence ):

    int lcs_length(char * A, char * B)

    {

	allocate storage for array L;

	for (i = m; i >= 0; i--)

	    for (j = n; j >= 0; j--)

	    {

		if (A[i] == '\0' || B[j] == '\0') L[i,j] = 0;

		else if (A[i+1] == B[j+1]) L[i,j] = 1 + L[i+1, j+1];

		else L[i,j] = max(L[i+1, j], L[i, j+1]);

	    }

	return L[0,0];

    }

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

    sequence S = empty

    i = 0

    j = 0

    while min(i,j) > 0

    {

	if (A[i]==B[j])

	{

	    add A[i] to end of S;

	    i--; j--;

	}

	else if (L[i+1,j] >= L[i,j+1]) i++;

	else j++;

    }

        n  e  m  a  t  o  d  e  _  k  n  o  w  l  e  d  g  e



    e   7  7  6  5  5  5  5  5  4  3  3  3  2  2  2  1  1  1  0

    m   6  6  6  5  5  4  4  4  4  3  3  3  2  2  1  1  1  1  0

    p   5  5  5  5  5  4  4  4  4  3  3  3  2  2  1  1  1  1  0

    t   5  5  5  5  5  4  4  4  4  3  3  3  2  2  1  1  1  1  0

    y   4  4  4  4  4  4  4  4  4  3  3  3  2  2  1  1  1  1  0

    _   4  4  4  4  4  4  4  4  4  3  3  3  2  2  1  1  1  1  0

    b   3  3  3  3  3  3  3  3  3  3  3  3  2  2  1  1  1  1  0

    o   3  3  3  3  3  3  3  3  3  3  3  3  2  2  1  1  1  1  0

    t   3  3  3  3  3  2  2  2  2  2  2  2  2  2  1  1  1  1  0

    t   3  3  3  3  3  2  2  2  2  2  2  2  2  2  1  1  1  1  0

    l   2  2  2  2  2  2  2  2  2  2  2  2  2  2  1  1  1  1  0

    e   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0

        0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

     ����� ����� ���������� ����� ���������������������, ��������� �� ������ ������ L[0,0]. ��� 7, ������ � ������������������ 7 ��������. L[0,0] ���� ��������� ��� max( L[0,1] , L[1,0] ), ������� �������� ���������� ��� �������� 'n' �� ������ ������ ��� 'e' �� ������.
     �������� 'n' ���� ��� ��������������������� ����� L[0,1]=7, � �� ����� ��� �������� 'e' - ������ L[1,0]=6, ��� ��� �� ����� ������� ���� 'n'. ��������� �� ������ L[0,1], �c�������� ����� ����� ��������. A[0]=B[1]='e', ��� ��� �� ����� ��� ������� �������� ��� 'e' � ��������������������� � ������� � L[1,2]=6. ����������, ��� ���� 'm'... ��������� � ��� �� ���� ( � ����� �������, ��� � ��������� ����, �������� ����, � �� ��������� ) �� �������� ����� ���������������������: 'emt ole'.

     ����, �� ����� LCS �� ����� O(mn). ������, �������� �� �������, ����� ��������, ��� ��� ����� ������ �������� ���������: ������� ����� � ����������� ���������� - � ��������� ��������� '�����', ��� �������� ��������. ���� ��� ������������, �� ����� �������� ����������� O(n log s + c log log min(c,mn/c)), ��� � - ����� ����� �����, � s - ����� ��������, ������������ � ���� �������.

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

�� �������������� � ������ LCS:

    int lcs_length(char * A, char * B)

    {

	allocate storage for one-dimensional arrays X and Y

	for (i = m; i >= 0; i--)

	{

	    for (j = n; j >= 0; j--)

	    {

		if (A[i] == '\0' || B[j] == '\0') X[j] = 0;

		else if (A[i+1] == B[j+1]) X[j] = 1 + Y[j+1];

		else X[j] = max(Y[j], X[j+1]);

	    }

	    Y = X;

	}

	return X[0];

    }

����� �� ��������, � ���������� � ���������.