只有小写字母 那＞＝２６００的直接找单字母串长度大于等于１００的就可以了
＜２６００ 的ｄｐ找最长回文串
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
#define N 50010
char s[N];
char pa[];
int dp[][][],g,n,o[];
void dfs(int ss,int i,int j,int k)
{
if(ss==)
return ;
if(i==j)
{
pa[g++] = s[i];
return ;
}
if(i!=n-&&j&&s[i]==s[j]&&dp[i][j][k]==dp[i+][j-][k]+)
{ pa[g++] = s[i];
dfs(dp[i+][j-][k],i+,j-,k);
return ;
}
if(i!=n-&&dp[i][j][k]==dp[i+][j][k])
{
dfs(dp[i+][j][k],i+,j,k);
return ;
}
if(j&&dp[i][j][k]==dp[i][j-][k])
{
dfs(dp[i][j-][k],i,j-,k);
return ;
}
}
int main()
{
int i,j,d;
cin>>s;
int k = strlen(s);
n = k;
if(k>=)
{
for(i = ; i < k ; i++)
o[s[i]-'a']++;
for(i = ; i < ; i++)
if(o[i]>=)
{
d = i;
break;
}
for(i = ; i <= ; i++)
printf("%c",d+'a');
puts("");
}
else
{
for(i = ; i < k ; i++)
{
dp[i][i][] = ;
}
for(i = k- ; i >= ;i--)
for(j = i+ ; j < k ; j++)
{
if(s[i]==s[j])
{
dp[i][j][] = dp[i+][j-][]+;
dp[i][j][] = dp[i+][j-][]+;
}
dp[i][j][] = max(dp[i][j][],max(dp[i+][j][],dp[i][j-][])); dp[i][j][] = max(dp[i][j][],max(dp[i+][j][],dp[i][j-][]));
}
}
if(dp[][k-][]>=)
{
dfs(dp[][k-][],,k-,);
for(i = ; i < ; i++)
printf("%c",pa[i]);
for(i = - ; i >= ; i--)
printf("%c",pa[i]);
puts("");
}
else
{
dfs(dp[][k-][],,k-,);
for(i = ; i < g ; i++)
printf("%c",pa[i]);
if(dp[][k-][]%!=)
g--;
for(i = g- ; i >= ; i--)
printf("%c",pa[i]);
puts("");
}
return ;
}