Cod sursa(job #1256040)

Utilizator roberticrobert robertic Data 5 noiembrie 2014 18:50:11
Problema Cel mai lung subsir comun Scor 20
Compilator fpc Status done
Runda Arhiva educationala Marime 1.28 kb
program p3;
function max(a,b:longint):longint;
  begin
  if a>b then max:=a
            else max:=b;
  end;
  var fi,fo:text;
      a,b,d:array[1..1200] of longint;
      c:array[1..1200,1..1200] of longint;
      i,j,n,m,k:longint;
Begin
  assign(fi,'cmlsc.in');reset(fi);
  assign(fo,'cmlsc.out');rewrite(fo);
  readln(fi,n,m);
  for i:=2 to n+1 do read(fi,a[i]);
  for i:=2 to m+1 do read(fi,b[i]);
  for i:=2 to n+1 do
    for j:=2 to m+1 do
      if a[i]=b[j] then c[i,j]:=c[i-1,j-1]+1
        else c[i,j]:=max(c[i,j-1],c[i-1,j]);
  writeln(fo,c[n+1,m+1]);
  j:=m+1;i:=n+1; k:=0;
    while (j>=2)and(i>=2) do
     if a[i]=b[j] then begin
                          inc(k);
                          d[k]:=a[i];
                          dec(i);
                          dec(j);
                        end
         else if j>2 then begin
            if c[i-1,j]<c[i,j-1] then dec(j)
            else if c[i-1,j]>c[i,j-1] then dec(i)
              else if c[i-1,j]=c[i,j-1] then dec(j)
                     end
            else if (j=2)and(i>2) then begin
                                   j:=m+1;
                                   dec(i);
                                       end;
  for i:=k downto 1 do write(fo,d[i],' ');
  close(fi);
  close(fo);
end.