Trở về đầu
Đề 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.