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