NKPALIN - Chuỗi đối xứng
Tác giả: hieult
Ngôn ngữ: C++
#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();
}