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.