HỌC TIN CÙNG THỦ KHOA

Đề 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.