NKPALIN - Chuỗi đối xứng
Tác giả: ladpro98
Ngôn ngữ: Pascal
program nkpalin;//qhd
uses math;
const fi='';
var s,res:ansistring;
f:array[1..2000,1..2000] of longint;
check:array[1..2000,1..2000] of boolean;
maxL,dau,cuoi,i,j,kq,len:longint;
procedure input;
var inp:text;
begin
assign(inp,fi);
reset(inp);
readln(inp,s);
close(inp);
end;
function qhd(i,j:longint):longint;
begin
if (check[i,j]) or (i>j) then exit(f[i,j]);
check[i,j]:=true;
if s[i]=s[j] then
begin
f[i,j]:=qhd(i+1,j-1)+2;
exit(f[i,j]);
end;
f[i,j]:=max(qhd(i+1,j),qhd(i,j-1));
exit(f[i,j]);
end;
procedure init;
var i:longint;
begin
for i:=1 to length(S) do
begin
check[i,i]:=true;
f[i,i]:=1;
end;
end;
begin
input;
init;
for i:=1 to length(s) do for j:=1 to length(s) do qhd(i,j);
kq:=qhd(1,length(s));
len:=high(longint);
for i:=1 to length(s) do
for j:=i to length(s) do
begin
if (f[i,j]=kq) and ((j-i+1)<len) then
begin
dau:=i;
cuoi:=j;
len:=j-i+1;
end;
end;
i:=dau;
j:=cuoi;
res:='';
while (kq>1) do
begin
if s[i]=s[j] then
begin
res:=res+s[i];
dec(kq,2);
inc(i);
dec(j);
end
else if f[i+1,j]<f[i,j-1] then
begin
dec(j);
end
else inc(i);
end;
if kq=1 then
begin
res:=res+s[i];
for i:=length(res)-1 downto 1 do
res:=res+res[i];
end
else
begin
for i:=length(res) downto 1 do
res:=res+res[i];
end;
write(res);
end.