QBSTR - Xâu con chung dài nhất

Tác giả: flashmt

Ngôn ngữ: Pascal

const max=1000000;
var n,m,i,j,re,t:longint;
    a,b:array[1..max] of char;
    c:array[0..1,0..max] of longint;
begin
     {---------Read---------}
     n:=0;
     while not eoln do
     begin
          inc(n);
          read(a[n]);
     end;
     readln;
     m:=0;
     while not eoln do
     begin
          inc(m);
          read(b[m]);
     end;
     {---------Process---------}
     re:=0;
     fillchar(c,sizeof(c),0);
     for i:=1 to n do
         for j:=1 to m do
         begin
              t:=i mod 2;
              if c[1-t,j]>=c[t,j-1] then c[t,j]:=c[1-t,j]
              else c[t,j]:=c[t,j-1];
              if (a[i]=b[j]) and (c[t,j]<=c[1-t,j-1]) then
              begin
                   c[t,j]:=c[1-t,j-1]+1;
                   if c[t,j]>re then re:=c[t,j];
              end;
         end;
     {---------Write---------}
     write(re);
end.

Download