hdu3294:http://acm.hdu.edu.cn/showproblem.php?pid=3294
题意：就是给你一个串，然后求一个最长的回文串，输出起点及串，但是这里在之前要转化一下。
题解：转化一下，就是简单的Manacher算法。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=2e6+440; 7 char str1[N],str[N<<1]; 8 int rad[N]; 9 char temp; 10 void Manacher(int *rad,char *str,int n){ 11 int i,mx=0,id; 12 for(int i=1;i<n;i++){ 13 if(mx>i){ 14 rad[i]=min(rad[2*id-i],mx-i); 15 } 16 else 17 rad[i]=1; 18 for(;str[i-rad[i]]==str[i+rad[i]];rad[i]++){ 19 if(rad[i]+i>mx){ 20 mx=rad[i]+i; 21 id=i; 22 } 23 } 24 } 25 } 26 27 int main(){ 28 while(~scanf("%c %s",&temp,str1)){ 29 getchar(); 30 int nn=strlen(str1); 31 int n=2*nn+2; 32 str[0]='$'; 33 for(int i=0;i<=nn;i++){ 34 str[2*i+1]='#'; 35 str[2*i+2]=(str1[i]-temp+26)%26+'a'; 36 } 37 memset(rad,0,sizeof(rad)); 38 Manacher(rad,str,n); 39 int ans=0,pos=0; 40 for(int i=0;i<=n;i++){ 41 if(rad[i]>=3&&rad[i]>ans){ 42 ans=rad[i]; 43 pos=i; 44 } 45 } 46 ans--; 47 if(ans==-1)printf("No solution "); 48 else{ 49 int s=pos-ans+1,e=pos+ans-1; 50 printf("%d %d ",s/2-1,e/2-1); 51 for(int i=pos-ans+1;i<=pos+ans-1;i++){ 52 if(str[i]=='#')continue; 53 printf("%c",str[i]); 54 } 55 puts(""); 56 } 57 } 58 }