HỌC TIN CÙNG THỦ KHOA

Đề bài: Cho xâu X. Hãy thêm một số ít nhất các ký tự để xâu thu được là xâu đối xứng

Mời các bạn download tại: Click here

const fi = 'DOIXUNG.INP';
      fo = 'DOIXUNG.OUT';
      MAXN = 1000;
var X: string;
    L: array [1..MAXN, 1..MAXN] of integer;
    n: integer;
    f: text;

procedure Nhap;
begin
        assign(f, fi); reset(f);
        readln(f, X);

        n:= length(X);

        close(f);
end;

function Min(a, b: integer): integer;
begin
        Min:= a;
        if Min>b then Min:= b;

end;

procedure QHD;
var i, j, k: integer;
begin
               fillchar(L,sizeof(L),0);


                for i:= 1 to n-1 do
                        if X[i] =  X[i+1] then L[i, i+1]:= 0
                                else L[i, i+1]:= 1;


                // k = j - i:
                // 0 <= k <= n - 1

                for k:= 2 to n-1 do
                     for i:= 1 to n-k do
                       begin
                        j:= i + k;
                        if X[i] = X[j] then
                                L[i, j]:= L[i+1, j-1]
                                else
                                    L[i, j]:= Min(L[i+1, j]+1, L[i, j-1]+1);
                       end;
end;

procedure TruyVet(i, j: integer);
begin
      if i = j then exit;

      if i = j-1 then
      begin
        if X[i] = X[j] then exit
                else
                begin
                        writeln(f, 'Chen ki tu ', X[i], ' vao sau ki tu ', X[j], ' tai vi tri ', j);
                        // 'ab'
                        exit;
                end;
      end;

      //i < j-1

      if X[i] = X[j] then TruyVet(i+1, j-1)
        else if L[i, j] = L[i+1, j] + 1  then
        begin
                writeln(f, 'Chen ki tu ', X[i], ' vao sau ki tu ', X[j], ' tai vi tri ', j); // in truoc TruyVet
                TruyVet(i+1, j);
        end
                else if L[i, j] = L[i, j-1] + 1  then
                begin
                        TruyVet(i, j-1);
                        // in sau TruyVet. Doi cach ghi: truoc ki tu X[i] => sau ki tu X[i-1] vi day la ki tu tam thoi chua thay doi
                        if i > 1 then
                           writeln(f, 'Chen ki tu ', X[j], ' vao sau ki tu ', X[i-1], ' tai vi tri ', i-1)
                           else writeln(f, 'Chen ki tu ', X[j], ' vao sau ki tu tai vi tri ', i-1);
                end

end;

procedure InKQ;
var i: integer;
begin
        assign(f, fo); rewrite(f);
        writeln(f, L[1, n]);
        TruyVet(1, n);
        close(f);
end;

BEGIN
        Nhap;
        QHD;
        InKQ;
END.