LNACS - VOI10 - Dãy con chung không liền kề dài nhất

Tác giả: ladpro98

Ngôn ngữ: Pascal

//cho 2 xau s1,s2 co length <=1000. Tim xau con chung dai nhat.
program xaucondainhat;
uses    math;
const   maxLength = 1000;

var     t1,t2:array[1..maxLength] of longint;
        len: array[-1..maxLength,-1..maxLength] of longint;
        i,j,res,m,n:longint;

procedure input;
begin
        readln(m,n);
        for i:=1 to m do readln(t1[i]);
        for j:=1 to n do readln(t2[j]);
end;

procedure process;
var     i,j:word;
begin
        for i:=1 to m do
        for j:=1 to n do
        if t1[i]=t2[j] then
             begin
                len[i,j]:=len[i-2,j-2]+1;
             end
        else len[i,j]:=max(len[i-1,j],len[i,j-1]);
end;

begin
        input;
        for i:=1 to m do begin len[i,0]:=0;len[i,-1]:=0;end;
        for j:=1 to n do begin len[0,j]:=0;len[-1,j]:=0;end;
        process;
        res:=len[m,n];
        write(res);
end.

Download