Câu 1. ( 3 điểm)
Cho một xâu kí tự có độ dài N không quá 5000 kí tự. Hãy tìm cách thêm vào tại vị trí bất kì của của xâu sao cho xâu mới tạo thành là một xâu đối xứng và số kí tự thêm vào là ít nhât.
Dữ liệu vào từ File văn bản BAI1.INP, dòng đầu ghi số N, dòng tiếp theo là xâu kí tự.
Kết quả ghi vào File văn bản BAI2.OUT gồm chỉ 1 giá trị duy nhất là số kí tự cần thêm vào để được xâu đối xứng.
Ví dụ:
Test 1:
|
BAI1.INP |
BAI1.OUT |
|
12 Chuoidoixung |
7 |
Test 2:
|
BAI1.INP |
BAI1.OUT |
|
5 Huynh |
2 |
uses crt;
const finp='Bai1.inp';
fout='Bai1.out';
type mangc=array[1..10000] of char;
mangl=array[1..10000] of longint;
var f:text;
ch:mangc; a:mangl;
n:longint;
procedure doc;
var i:longint;
begin
assign(f,finp);
reset(f);
readln(f,n);
for i:=1 to n do read(f,ch[i]);
close(f);
end;
procedure ghi;
begin
assign(f,fout);
rewrite(f);
end;
procedure tim;
var i,j,d,k,l:longint;
begin
for i:=n-2 downto 1 do
begin
a[i]:=1;
d:=0;
for j:=i+1 to n do
begin
l:=a[j];
if ch[i]=ch[j] then a[j]:=d+2
else if a[j-1]>a[j] then a[j]:=a[j-1];
d:=l;
end;
end;
end;
procedure xuly;
var i:longint;
begin
fillchar(a,sizeof(a),0);
if n=1 then a[n]:=1
else begin
a[n-1]:=1;
a[n]:=ord(ch[n]=ch[n-1])+1;
end;
if n>2 then tim;
write(f,n-a[n]);
end;
begin
doc;
ghi;
xuly;
close(f);
end.
ai có thể giải thích cho mình bài này đc không
nhất là cái "procedure tim" và mục đích của mảng số nguyên a
mk cảm ơn nhiều
