Program Problem6_3; 
Uses crt;
Type
   matrix = array [0..20,0..20] of byte;
   str1 = string[20];
Var
    X,Y,L:str1;
    b,c:matrix;
    i,j:byte;
{-- Процедура вычисления длины НОП и "координат" ее получения --}
Procedure LCS_LENGTH(X,Y:str1; var b,c:matrix);
Var i, j: byte;
Begin
  {Обнуление нулевого столбца}
  For i:=1 To length(X) do c[i, 0]:=0;
  {Обнуление нулевой строки}
  For i:=1 To length(Y) do c[0, i]:=0;
  {Заполнение матриц C и B}
  For i:=1 To length(X) do
    For j:=1 To length(Y) do
       If X[i]=Y[j] Then{Если символы совпадают}
                        Begin
                            c[i,j]:= c[i - 1, j - 1] + 1;
                            b[i,j]:= 3;
                        end
                    else
                     If c[i-1, j] >= c[i, j-1] Then
                        Begin{Если элемент сверху больше элемента слева}
                            c[i,j]:= c[i - 1, j];
                            b[i,j]:= 1;
                        end
                    else
                        Begin
                            c[i,j]:= c[i, j - 1];
                            b[i,j]:= 2;
                        end;
end;
{----------- Функция нахождения НОП ---------}
Function PRINT_LGS1(i, j: integer; X: str1; b: matrix):str1;
Var L: str1;
Begin
    L:='';
    While (i<>0) And (j<>0) Do {Пока не элемент (0,0)}
      If b[i, j] = 3 Then {Если попали в эту ячейку по диагонали}
         Begin
           L:= x[i] + L; {Получение последовательности}
           i:= i - 1;
           j:= j - 1;
         end
      else
         {Элементы не входят в обе последовательности}
         If b[i, j] = 1 Then i:= i-1
                        else j:= j-1;
    PRINT_LGS1:= L;
end;
{--------- Код основной программы ---------}
Begin
  clrscr;
  writeln(' Введите первую последовательность 
           (максимальная длина 20 символов):');
  readln(x);{Ввод последовательности}
  writeln(' Введите вторую последовательность 
           (максимальная длина 20 символов):');
  readln(y);{Ввод последовательности}
  clrscr;
  Writeln(' Ваши последовательности:');
  writeln(x);{Вывод последовательностей}
  writeln(y);
  LCS_LENGTH(X, Y, b, c); {Обращение к процедуре}
  writeln;
  L:= PRINT_LGS1(length(x), length(y), X, b); {Вызов функции}
  {Вывод НОП или осообщения о том, что НОП не существует}
  If L = '' Then Writeln('Нет такой последовательности!!!')
            else Writeln('Наибольшая общая последовательность:  ',L);
  ReadKey;
End.