给定字母x,字符串变换一下: 'x'-1 -> 'z', ‘x’->‘a’, ‘x’+1->‘b’, ..., 求对应的字符串的最长的回文串。
求最长回文串的O(n)的算法:Manacher算法
#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 %d\n",i/2,j/2);
for(;i<=j;i+=2) printf("%c",(s[i]-c+26)%26+'a');
}else printf("No solution!");
puts("");
}
return 0;
}