Cod sursa(job #601312)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 5 iulie 2011 21:40:49
Problema Cel mai lung subsir comun Scor 60
Compilator fpc Status done
Runda Arhiva educationala Marime 1.12 kb
Program arena_cmlsc;
var fi, fo : text;
    n,m,i,j : integer;
    x,y : array[0..1024] of integer;
    c : array[0..900,0..900] of integer;
    k:array[1..1024] of integer;
begin
      assign(fi,'cmlsc.in'); reset(fi); readln(fi,n,m);
      for i:=1 to n do read(fi,x[i]); for i:=1 to m do read(fi,y[i]); close(fi);
      assign(fo,'cmlsc.out'); rewrite(fo);
      for i:=0 to n do for j:=0 to m do c[i,j]:=0;
      for i:=1 to n do
         for j:=1 to m do if x[i]=y[j] then c[i,j]:=c[i-1,j-1]+1
                                       else if c[i-1,j]>c[i,j-1] then c[i,j]:=c[i-1,j]
                                                                 else c[i,j]:=c[i,j-1];
      for i:=1 to c[n,m] do k[i]:=0;
      i:=n; j:=m; writeln(fo,c[n,m]);
      while c[i,j]<>0 do begin
                         if x[i]=y[j] then begin k[c[i,j]]:=x[i]; i:=i-1; j:=j-1; end
                                      else if c[i,j-1]>c[i-1,j] then j:=j-1
                                                                else i:=i-1;
                         end;
      for i:=1 to c[n,m] do write(fo,k[i],' ');
      close(fo);
end.