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.