MSTRING - String problem

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}

var
    pa, pb : array[0..2000] of char;
    a, b : PChar;
    i, j, na, nb : integer;
    F : array[0..1010,0..1010] of integer;
    prev : array[0..1010,'a'..'z'] of integer;
    pos : array['a'..'z'] of integer;
    c : char;

function getmin(a, b : integer) : integer;
begin
    if a=0 then getmin := b
    else if a < b then getmin := a
        else getmin := b; 
end;

begin
    readln(pa);
    readln(pb);
    a := PChar(@pa);
    Dec(a);
    b := PChar(@pb);
    Dec(b);
    na := Length(PChar(@a[1]));
    nb := Length(PChar(@b[1]));
    for i:=1 to na do
        F[i,0] := 1;
    for i:=1 to nb do
    begin
        pos[b[i]] := i;
        for c:='a' to 'z' do
            prev[i,c] := pos[c];
    end;
    for j:=1 to nb do
    begin
        for i:=1 to na do
        begin
            if F[i-1,j]<>0 then F[i,j] := F[i-1,j];
            if prev[j,a[i]]=0 then F[i,j] := 1
            else if F[i-1,prev[j,a[i]]-1]<>0 then F[i,j] := getmin( F[i,j], F[i-1,prev[j,a[i]]-1] + 1);
        end;
    end;
    writeln( F[na, nb] );
end.

Download