题目链接：
题目描述：
给出一串字符串代表暗码，暗码字符是通过明码循环移位得到的，比如给定b，就有b == a，c == b,d == c,.......,a == z。
问最长回文串所在区间，以及最长回文串所表示的明码。
解题思路：
字符串长度[1,200000]，用manacher算法很轻松就搞定了。
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std; typedef long long LL;
const int maxn = ;
char a[maxn], b[maxn*];
int vis[maxn*]; void manacher (char s[], int len)
{
int l = ;
b[l ++] = '$';
b[l ++] = '#';
for (int i=; i<len; i++)
{
b[l ++] = s[i];
b[l ++] = '#';
}
b[l] = ; /**
vis[i],以i为中心的回文串，向两端延伸的长度
mx为向后延伸最长的回文串延伸到的位置，id为其中心 **/ int mx = , id = , ans = , index;
for (int i=; i<l; i++)
{ /**
i < mx,因为[id-vis[id],mx],所以i与id-(i-id)对称
当i+vis[2*id-i] > mx时,vis[i] = mx - i; 当i >= mx....... 两端字符匹配时增加vis[i] 更新id 和 mx
**/ vis[i] = mx > i ? min (vis[*id-i], mx-i) : ;
while (b[i+vis[i]] == b[i-vis[i]]) vis[i] ++;
if (i + vis[i] > mx)
{
mx = i + vis[i];
id = i;
}
if (ans < vis[i])
{
ans = vis[i];
index = i;
}
} /**
每一个回文串都是以'#'为边界
vis[i]是以i为第一个字母，向两边延伸的长度
每一个字母在b数组中的偶数位置
**/ int x = index - vis[index] + ;
int y = index + vis[index] - ;
x = x / - ;
y = y / - ;
if (y != x)
{
printf ("%d %d\n", x, y);
for (int i=x; i<=y; i++)
printf ("%c", a[i]);
printf ("\n");
}
else
printf ("No solution!\n");
} int main ()
{
char ch[], vis[];
while (scanf ("%s %s", ch, a) != EOF)
{
int n = strlen (a); for (int i=; a[i]; i++)
{
a[i] -= ch[] - 'a';
if (a[i] < 'a')
a[i] += ;
} manacher(a, n);
}
return ;
}