Mine

Задача 2. Наибольшая общая подпоследовательность (НОП).
Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество ее элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCBDAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X  и Y, если Z является подпоследовательностью как X,  так и Y. Требуется для двух последовательностей X  и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.
Решение. Задача о НОП обладает свойством оптимальности для подзадач. Здесь подходящее множество подзадач — множество пар префиксов (начальных частей) двух данных последовательностей. Покажем это. Пусть Z = {z1, z2, …, zk} одна из НОП для X = {x1, x2, …, xm} и Y = {y1, y2, …, yn}. Если xm = yn, то zk = xm = yn (в противном случае мы могли бы дописать xm = yn в конец последовательности Z и получить НОП длины k+1. Кроме того Zk-1 является НОП для Xm-1 и Yn-1 (если это не так, то мы можем к НОП Xm-1 и Yn-1 дописать xm = yn и получить НОП для X и Y более длинную, чем Z. Если zk  xm, то так как Z — НОП для X и Y, она тем более является НОП для Xm-1 и Y. Аналогично, если zk  yn, то Z — НОП для X и Yn-1. Максимальное количество подзадач, которое нам может понадобиться решить, равно mn (для каждой пары префиксов X и Y). Это позволяет использовать при решении динамическое программирование. Выпишем рекуррентное соотношение между длинами НОП в подзадачах, обозначив за a[i, j] длину НОП для Xi и Yj:
Приведем программу решения этой задачи для последовательностей, состоящих из не более чем 250 символов:
var x,y,z:string;
    a:array[0..250,0..250] of byte;
    i,j:byte;
begin
  readln(x);
  readln(y);
  fillchar(a,sizeof(a),0);
  for i:=1 to length(x) do
  for j:=1 to length(y) do
    if x[i]=y[j] then a[i,j]:=a[i-1,j-1]+1 
    else if a[i-1,j]>=a[i,j-1] then a[i,j]:=a[i-1,j]
                               else a[i,j]:=a[i,j-1];
  {длина НОП найдена в a[length(x),length(y)]}
  z:='';{строим саму НОП}
  i:=length(x);
  j:=length(y);
  while (i>0) and (j>0) do
  if x[i]=y[j] then begin z:=x[i]+z; i:=i-1; j:=j-1 end
  else if a[i-1,j]>=a[i,j-1] then i:=i-1 else j:=j-1;
  writeln(z)
end.