## Editorial for Chuỗi đối xứng

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxn=2000;
var a,b,kq:array[0..maxn] of char;
f:array[0..maxn,0..maxn] of integer;
num:integer;

procedure rf;
begin
num:=0;
while not eoln do
begin
inc(num);
end;
end;
{---------------}
procedure pr;
var i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to num do
b[i]:=a[num-i+1];
for i:=1 to num do
for j:=1 to num do
begin
if f[i-1,j]>=f[i,j-1] then f[i,j]:=f[i-1,j]
else f[i,j]:=f[i,j-1];
if (a[i]=b[j]) and (f[i,j]<=f[i-1,j-1]) then
f[i,j]:=f[i-1,j-1]+1;
end;
end;
{---------------}
procedure wf;
var i,j,c,pre:integer;
begin
repeat
if a[i]=b[j] then
begin
write(a[i]);
dec(i);
dec(j);
end
else
begin
if f[i,j]=f[i-1,j] then dec(i)
else dec(j);
end;
until (f[i,j]=0);
end;
{---------------}
begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define SZ 2005
#define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i )
#define max(a, b) ((a) > (b) ? (a) : (b))
char s[SZ];
int f[SZ][SZ], n;

void solve() {
FOR( len, 1, n ) FOR( i, 0, n-len ) {
int j = i + len - 1;
if ( len == 1 ) f[i][j] = 1;
//else if ( len == 2 ) f[i][j] = s[i] == s[j] ? 2 : max(f[i][j], f[j][j]);
else f[i][j] = s[i] == s[j] ? f[i+1][j-1] + 2 : max(f[i][j-1], f[i+1][j]);
/*printf( "%d %d %d\n", len, i, j);
FOR(i, 0, n-1) {
FOR(j, 0, n-1) printf( "%3d", f[i][j] );
putchar('\n');
}*/
}
}

void print() {
char res[SZ]; memset(res, '\0', sizeof res);
int i = 0, j = n-1, l = 0;
while( i <= j ) {
if ( f[i][j] == f[i+1][j] ) ++i;
else if ( f[i][j] == f[i][j-1] ) --j;
else {
res[l++] = s[i];
++i; --j;
}
}
printf( "%s", res );
if( f[0][n-1] % 2 ) res[--l] = 0;
reverse(res, res+l);
puts(res);
}

int main() {
scanf( "%s", s ); n = strlen(s);
solve();
print();
return 0;
}


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);
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.


#### Code mẫu của RR

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
init;
solve(1,n);
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <string.h>

main()
{
char s[2000],B[2000]; int f[2000][2000],max[2000][2000],min[2000][2000];
gets(s);
int n=strlen(s)-1;
f[0][0]=1;
min[0][0]=0;
max[0][0]=0;
for(int i=1;i<=n;i++)
{
f[i][i]=1;
f[i][i-1]=0;
max[i][i]=i;
min[i][i]=i;
}
for(int i=1;i<=n;i++)
for(int j=0;j<=n-i;j++)
{
if(s[j]==s[j+i])
{
f[j][j+i]=f[j+1][j+i-1]+2;
max[j][j+i]=j+i;
min[j][j+i]=j;
}

else
{
if(f[j+1][j+i]>f[j][j+i-1])
{
f[j][j+i]=f[j+1][j+i];
max[j][j+i]=max[j+1][j+i];
min[j][j+i]=min[j+1][j+i];
}
else
{
f[j][j+i]=f[j][j+i-1];
max[j][j+i]=max[j][j+i-1];
min[j][j+i]=min[j][j+i-1];
}
}

}
int x=0,y=n,z=f[0][n],t=f[0][n];
// printf("%d %d %d\n",min[0][n],max[0][n],t);
while(z!=0 && z!=1)
{
B[(t-z)/2+1]=s[min[x][y]];
B[(t+z)/2]=s[max[x][y]];
int xx=x;
x=min[x][y]+1;
y=max[xx][y]-1;
z=z-2;
// printf("%d %d\n",x,y);
}
if(z==1)
B[(t+1)/2]=s[min[x][y]];
for(int i=1;i<=t;i++)
printf("%c",B[i]);
// getch();
}


#### Code mẫu của ll931110

Program NKPALIN;
Const
input  = '';
output = '';
Var
s: array[1..2000] of char;
F: array[0..2000,0..2000] of integer;
fo: text;
n: integer;
Procedure init;
Var
fi: text;
Begin
Assign(fi, input);
Reset(fi);
n:= 0;
While not eoln(fi) do
Begin
inc(n);
End;
End;

Function max(p,q: integer): integer;
Begin
If p < q then max:= q else max:= p;
End;

Procedure optimize;
Var
i,j: integer;
Begin
Fillchar(F, sizeof(F), 0);
For i:= 1 to n do F[i,i]:= 1;

For i:= n downto 1 do
For j:= i + 1 to n do
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;

Procedure trace(x,y: integer);
Begin
If x = y then write(fo, s[x])
else if x < y then
Begin
If s[x] = s[y] then
Begin
write(fo, s[x]);
trace(x + 1,y - 1);
write(fo, s[x]);
End
else
if F[x + 1,y] > F[x,y - 1] then trace(x + 1,y)
else trace(x,y - 1);
End;
End;

Begin
init;
optimize;
Assign(fo, output);
Rewrite(fo);
trace(1,n);
Close(fo);
End.


#### Code mẫu của skyvn97

#include<stdio.h>
#include<string.h>
#define MAX 2222
char s[MAX];
bool t[MAX];
int o[MAX][MAX];
int l;
int max(int x,int y)
{
if (x>y) return (x);else return (y);
}
void count(int i,int j)
{
if (i>j) return;
if (o[i][j]!=0) return;
if (i==j)
{
o[i][j]=1;
return;
}
if (s[i-1]==s[j-1])
{
if (j-i==1)
{
o[i][j]=2;
return;
}
if (o[i+1][j-1]==0) count(i+1,j-1);
o[i][j]=o[i+1][j-1]+2;
}
else
{
if (o[i+1][j]==0) count(i+1,j);
if (o[i][j-1]==0) count(i,j-1);
o[i][j]=max(o[i+1][j],o[i][j-1]);
}
return;
}
void init(void)
{
int i;
gets(s);
l=strlen(s);
for (i=1;i<=l;i=i+1) t[i]=false;
}
void optimize(void)
{
int i,j;
for (i=1;i<l;i=i+1)
for (j=i+1;j<=l;j=j+1) count(i,j);
}
void trace(void)
{
int i,j;
i=1;j=l;
while (i<=j)
{
if (s[i-1]==s[j-1])
{
t[i]=true;
t[j]=true;
i=i+1;
j=j-1;
}
else
{
if (o[i][j]==o[i+1][j]) i=i+1;
else j=j-1;
}
}
for (i=1;i<=l;i=i+1)
if (t[i]) printf("%c",s[i-1]);
}
int main(void)
{
init();
optimize();
trace();
}


#### Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

char a[2020];
int f[2020][2020];
int n;

int calc(int i,int j) {
if(i>j) return 0;
if(i==j) return 1;
int &ret = f[i][j];
if(ret!=-1) return ret;
ret = 0;
ret >?= calc(i+1,j);
ret >?= calc(i,j-1);
if(a[i]==a[j]) ret >?= calc(i+1,j-1) + 2;
return ret;
}

void truy(int i,int j) {
if(i>j) return;
if(i==j) {
cout << a[i];
return;
}
int r = f[i][j];
if(r==calc(i+1,j)) { truy(i+1,j); return; }
if(r==calc(i,j-1)) { truy(i,j-1); return; }
if(a[i]==a[j] && r==calc(i+1,j-1)+2) {
cout << a[i];
truy(i+1,j-1);
cout << a[j];
return;
}
}

int main() {
gets(a);
n = strlen(a);
memset( f, -1, sizeof(f));
calc(0,n-1);
truy(0,n-1);
cout << endl;
return 0;
}