【 HDU3294 】Girls' research (Manacher)---饶文津

题意

给定字母x，字符串变换一下: 'x'-1 -> 'z', ‘x’->‘a’, ‘x’+1->‘b’, ..., 求对应的字符串的最长的回文串。

题解

求最长回文串的O(n)的算法：Manacher算法

算法过程：用’#‘号把每个字符分隔开，且开头结尾都是’#‘。RL[i]为以i为中心的最长回文最右的字符与i的距离。已经求过的回文串中，右端点最大的回文串的中心为p。求当前的RL[i]时，若 i 在最大右端点的左边，则RL[i] 初始值为min(RL[j],最大右端点-i)，j是以p为中心，i对称的点。否则RL[i]=1。再直接扩展RL[i]，同时维护p。代码#include <cstdio> #include <algorithm> #define N 200002 using namespace std; char c,s[N<<1]; int RL[N<<1]; int Manacher(){ int i,p=0,q=0; for(i=0;s[i];i++); for(i;i>=0;i--) s[i*2+1]=s[i],s[i*2]='#'; for(i=0;s[i];i++){ if(RL[p]+p>i) RL[i]=min(RL[p*2-i],RL[p]+p-i); else RL[i]=1; while(s[i-RL[i]]&&s[i-RL[i]]==s[i+RL[i]]) RL[i]++; if(i+RL[i]>p+RL[p]) p=i; if(RL[i]>RL[q]) q=i; //q是最长的回文串的中点。 } return q; } int main() { while(~scanf(" %c%s",&c,s)){ int q=Manacher(); int i=q-RL[q]+1,j=q+RL[q]-1; if(s[i]=='#')i++,j--; if(RL[q]>2){ printf("%d %dn",i/2,j/2); for(;i<=j;i+=2) printf("%c",(s[i]-c+26)%26+'a'); }else printf("No solution!"); puts(""); } return 0; } ---来自腾讯云社区的---饶文津