链接 http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11404&courseid=0
求 最长回文个数 并且输出 ； 虽然 O(n^2) 可过； 但 O(n) 是王道
看这个博客 http://www.cnblogs.com/wulangzhou/p/3449428.html
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 111000
using namespace std;
inline int min( int a,int b ){return a>b?b:a;}
inline int max( int a,int b ){return a>b?a:b;}
char cha[maxn],str[maxn*]; int pi[maxn*];
struct date{
int l,r,len;
bool operator <(const date &a)const{
if( a.len != len )return a.len < len;
else return a.r < r;
}
}node[];
void manacher( )
{
int len = strlen( str ); int mx = ; int id = ;
memset( pi,,sizeof(pi) );
for( int i = ; i < len; i++ )
{
if( mx > i )pi[i] = min( pi[id*-i],mx-i );
else pi[i] = ;
while( str[i-pi[i]] == str[i+pi[i]] )pi[i]++;
node[i].l = i-(pi[i]-); node[i].r = i+(pi[i]-); node[i].len = node[i].r - node[i].l + ;
if( i+pi[i] > mx )
{
mx = i+pi[i];
id = i;
}
}
}
int main( )
{
int T,cas = ; scanf("%d",&T);
while( T-- )
{
scanf("%s",&cha); int len = strlen( cha ); int k = ; str[k++] = '!';
for( int i = ; i < len; i++ )
str[k++] = '#',str[k++] = cha[i]; str[k++] = '#'; str[k] = '\0';
manacher( );
printf("Case #%d:\n",cas++);
sort( node,node+k ); len = node[].len;
if( len <= ){continue;}
for( int i = ; i < k; i++ )
if( node[i].len == len )
{
for( int j = node[i].l; j <= node[i].r; j++ )
if( str[j] != '#' )cout<<str[j];
cout<<endl;
}else break;
}
return ;
}
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; char str[2100],cha[2100];
int tab[2100];
void manacher( )
{
int Mx = 0; int id = 0; int len = strlen(cha);
memset(tab,0,sizeof(tab));
for( int i = 1; i < len; i++ )
{
if( i < Mx )
tab[i] = min( tab[id*2-i],Mx-i );
else tab[i] = 1;
while( cha[i+tab[i]] == cha[i-tab[i]] )tab[i]++;
tab[i]--;
if( Mx < i+tab[i] ){
Mx = i+tab[i];
id = i;
}
}
}
int main( )
{
int T,cas = 1; cin>>T;
while( T-- )
{
scanf("%s",&str); int len = strlen(str); int k = 0;
cha[k++] = '@';
for( int i = 0; i < len; i++ )
{cha[k++] = '#', cha[k++] = str[i];}
cha[k++] = '#'; cha[k] = '\0';
int Max = 0; manacher( ); printf("Case #%d:\n",cas++);
for( int i = 1; i < k; i++ )
if( cha[i] != '#' )Max = max( Max,(tab[i]/2)*2+1 );
else Max = max( Max,tab[i] );
if( Max <= 1 ){continue;}
for( int j = k-1; j >= 0; j-- )
{
if( (cha[j] == '#'&&tab[j]==Max) || (cha[j] != '#'&&(tab[j]/2)*2+1 == Max ) )
for( int i = j-tab[j]; i != j+tab[j]; i++ )
if( cha[i] != '#' )cout<<cha[i];
cout<<endl;
}
}
return 0;
}
/*
abacaba
*/