Trở về đầu
Đề bài: Cho 2 xâu X,F. Xâu nguồn có n kí tự X1X2...Xn , xâu đích có m kí tự F1F2...Fm .Có 3 phép biến đổi:
• Chèn 1 kí tự vào sau kí tự thứ i: I i C
• Thay thế kí tự ở vị trí thứ i bằng kí tự C: R i C
• Xoá kí tự ở vị trí thứ i: D i
Hãy tìm số ít nhất các phép biến đổi để biến xâu X thành xâu F.
Mời các bạn download tại: Click here
{$LONGSTRINGS ON}
const fi = 'BIENDOI.INP';
fo = 'BIENDOI.OUT';
MAXN = 1000;
MAXM = 1000;
var g: text;
X, F: string;
n, m: integer;
L: array [0..MAXN, 0..MAXM] of integer;
procedure Nhap;
begin
assign(g, fi); reset(g);
readln(g, X);
n:= length(X);
readln(g, F);
m:= length(F);
close(g);
end;
function min3(a, b, c: integer): integer;
var min: integer;
begin
min:= a;
if min > b then min:= b;
if min > c then min:= c;
exit(min);
end;
procedure QHD;
var i, j: integer;
begin
L[0, 0]:= 0;
for i:= 1 to n do L[i, 0]:= i;
for j:= 1 to m do L[0, j]:= j;
for i:= 1 to n do
for j:= 1 to m do
if X[i] = F[j] then L[i, j]:= L[i-1, j-1]
else // X[i] <> F[j]
L[i, j]:= 1 + min3(L[i-1, j], L[i-1, j-1], L[i, j-1]);
end;
procedure TruyVet(i, j: integer);
var k: integer;
begin
if i = 0 then
begin
for k:= j downto 1 do writeln(g, 'Chen ki tu ', F[k], ' tai vi tri ',
k, ' cua xau F vao sau vi tri ',
k-1, ' cua xau X');
exit;
end;
if j = 0 then
begin
for k:= i downto 1 do writeln(g, 'Xoa ki tu ', X[k], ' tai vi tri ',
k, ' cua xau X');
exit;
end;
// i > 0 va j > 0
if X[i] = F[j] then TruyVet(i-1, j-1)
else
begin
if L[i, j] = 1 + L[i-1, j] then
begin
writeln(g, 'Xoa vi tri ', i, ' cua xau X');
TruyVet(i-1, j);
end
else if L[i, j] = 1 + L[i-1, j-1] then
begin
writeln(g, 'Thay the ki tu ', X[i],
' tai vi tri ', i, ' cua xau X bang ki tu ', F[j],
' tai vi tri ', j, ' cua xau F');
TruyVet(i-1, j-1);
end
else // L[i, j] = 1 + L[i, j-1]
begin
writeln(g, 'Chen ki tu ', F[j], ' tai vi tri ', j,
' cua xau F vao sau vi tri ', i,
' cua xau X');
TruyVet(i, j-1);
end;
end;
end;
procedure InKQ;
begin
assign(g, fo); rewrite(g);
writeln(g, L[n, m]);
writeln(g, X);
writeln(g, F);
TruyVet(n, m);
close(g);
end;
BEGIN
Nhap;
QHD;
InKQ;
END.