NKPALIN - Chuỗi đối xứng
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
const
MAXN = 2011;
var
s : ansistring;
n : longint;
f : array[1..MAXN,1..MAXN] of longint;
procedure init;
var
k,i,j:longint;
begin
for i:=1 to n do f[i,i]:=1;
for k:=1 to n-1 do
for i:=1 to n-k do
begin
j:=i+k;
if s[i]=s[j] then f[i,j]:=f[i+1,j-1]+2
else f[i,j]:=max(f[i+1,j],f[i,j-1]);
end;
end;
procedure solve(l,r:longint);
begin
if l>r then exit;
if s[l]=s[r] then
begin
write(s[l]);
solve(l+1,r-1);
if l<>r then write(s[r]);
end
else
if f[l+1,r]>f[l,r-1] then solve(l+1,r)
else solve(l,r-1);
end;
begin
readln(s); n:=length(s);
init;
solve(1,n);
end.