题意：求最长回文串
用Manacher 可以在O（n)时间内解决
#include<iostream>
#include<algorithm>
#include<string.h>
#define MAXN 200010
using namespace std;
char str1[MAXN],str[MAXN*2];
int rad[MAXN*2],nn,n;
void Manacher(int *rad,char *str,int n)
{
int i;
int mx = 0;
int id;
for(i=1; i<n; i++)
{
if( mx > i )
rad[i] = rad[2*id-i]<mx-i?rad[2*id-i]:mx-i;
else
rad[i] = 1;
for(; str[i+rad[i]] == str[i-rad[i]]; rad[i]++)
;
if( rad[i] + i > mx )
{
mx = rad[i] + i;
id = i;
}
}
}
int main()
{
char c;
while(scanf("%c %s",&c,str1)==2)
{
getchar();
int t=c-'a';
nn=strlen(str1);
for(int i=0;i<nn;i++)
{
int tt=str1[i]-'a';
str1[i]=(tt-t+26)%26 + 'a';
}
n=2*nn+2;
str[0]='$';
for(int i=0;i<=nn;i++)
{
str[2*i+1]='#';
str[2*i+2]=str1[i];
}
Manacher(rad,str,n);
int ans=1,st;
for(int i=0;i<n;i++)
{
if(rad[i]>ans)
{
ans=rad[i];
st=i;
}
}
ans--;
st=st/2 + ans/2-1;
if(ans==1)
puts("No solution!");
else
{
printf("%d %d\n",st+1-ans,st);
for(int i=st+1-ans;i<=st;i++)
printf("%c",str1[i]);
puts("");
}
}
return 0;
}