Trở về đầu

foto1 foto2 foto3 foto4 foto5
Nguyễn Tô Sơn - Giảng viên Đại học Sư phạm Hà Nội. SĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành tích hôm nay, Thành công ngày mai !

Tìm kiếm

Đề 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 = 0 then exit;
      if j = 0 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], ' o vi tri ', j, ' trong xau X ban dau');
                        // '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
                write(L[i,j]:3);
                writeln(f, 'Chen ki tu ', X[i], ' vao sau ki tu ', X[j], ' o vi tri ', j, ' trong xau X ban dau');
                TruyVet(i+1, j);
        end
                else if L[i, j] = L[i, j-1] + 1  then
                begin
                        write(L[i,j]);
                        writeln(f, 'Chen ki tu ', X[j], ' vao truoc ki tu ', X[i], ' o vi tri ', i, ' trong xau X ban dau');
                        TruyVet(i, j-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.

Bản quyền thuộc về Nguyễn Tô Sơn, Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869