题目大意：有多组数据，每组数据给出一个字符和一个字符串。该字符将变成’a‘，表示字符串中的所有该字符将变成’a‘,同时其他字符也将做相同的偏移。具体来说，如果该字符为’b‘,表示字符串中的’b‘都将变成a，偏移量为-1。此时字符串的其他字符都要做这个偏移，比如c将变成‘b’,‘d‘将变成‘c’……，而‘a’将变成‘z’。
现在给出许多这样的数据，要求出转换过后的最长的回文串。
分析：求回文串用manacher算法。因为manacher中会插入字符，从而改变原来的字符的位置。所以输出位置时要小心处理。一开始搞错了，位置多减了一个1，却过了样例和自己出的几个小数据。一定要多测试一些数据才行。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 400005 char s1[MAXN],s2[MAXN]; char str[3]; int p[MAXN],maxid,ans=0,pos; void manacher(char *s) { int len=strlen(s); p[0]=1,maxid=0; for(int i=1;i<len;++i) { if(maxid+p[maxid]>i) p[i]=min(p[2*maxid-i],maxid+p[maxid]-i); else p[i]=1; for(;s[i+p[i]]==s[i-p[i]];p[i]++); if(p[i]+i>p[maxid]+maxid)maxid=i; } } int main() { while(scanf("%s %s",str,s1)!=-1) { int len=strlen(s1); ans=0; pos=0; memset(s2,0,sizeof s2); s2[0]=‘*‘; s2[1]=‘#‘; for(int i=0,j=2;i<len;i++) { s2[j++]=s1[i]; s2[j++]=‘#‘; } manacher(s2); len=strlen(s2); for(int i=0;i<len;i++) { if(p[i]>ans) {ans=p[i]; pos=i; } } if(ans<=2) {printf("No solution!\n"); continue; } pos-=(ans-1); pos=(pos-1)/2; printf("%d %d\n",pos,pos+ans-2); for(int i=pos;i<pos+ans-1;i++) { s1[i]-=(str[0]-‘a‘); if(s1[i]<‘a‘) s1[i]+=26; printf("%c",s1[i]); } printf("\n"); } }
原文：http://www.cnblogs.com/hefenghhhh/p/5058854.html