回文就是正反读都是一样的字符串,如aba, abba等
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
题意：模板题，求最长回文子串的长度，字符串长度有11W,可以用manacher算法，注意输入的时候如果写成while(scanf("%s", a))会tle，应该写成while(scanf("%s", a) == 1)
manacher(马拉车)算法：复杂度O(n)
作用：给出一个字符串，求它的最长回文子串（的长度），求具体的串可以在模板上改一改
1.将字符串之间插入串中不可能有的字符，如将a a b a b a a b处理成 $ # a # a # b # a # b # a # a # b #,
一个回文串是对称的，既然对称，就一定有那个“对称轴”，对于长度为奇数的回文，它的对称轴是一个字符，对于长度为偶数的回文串，它的对称轴是两个字符。为了方便处理，将所有回文串的对称轴变为一个字符，可以如上插入不相关字符，这样连上刚插入的字符，原串就变成了奇数长度。 最前面的 '$' 是为了防止溢出（我也不太懂）
2.设数组Mp[i]为以i为中心的回文串的半径长度，
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
ma[i] $ # a # a # b # a # b # a # a # b #
mp[i] 0 0 1 2 1 0 3 1 7 ...
如此可以观察到mp[i]也代表 原串中 以i为中心的回文串的长度 ！ 所以最长回文串的长度就是mp数组中的最大值了
3.求mp数组
用i将整个ma数组遍历一遍，在遍历的过程中维护一个已知的最长回文串，这个回文串要求它的右边界最靠右、右边界相同的话中心最靠左，
以下转载于https://www.felix021.com/blog/read.php?2040
该算法增加两个辅助变量（其实一个就够了，两个更清晰）id和mx，其中 id 为已知的 {右边界最大} 的回文子串的中心，mx则为id+mp[id]，也就是这个子串的右边界。
然后可以得到一个非常神奇的结论，这个算法的关键点就在这里了：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。就是这个串卡了我非常久。实际上如果把它写得复杂一点，理解起来会简单很多：
if (mx - i > mp[j])
mp[i] = mp[j];
else /* mp[j] >= mx - i */
mp[i] = mx - i; // mp[i] >= mx - i，取最小值，之后再匹配更新。
当然光看代码还是不够清晰，还是借助图来理解比较容易。
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。
于是代码如下：
int mp[1000], mx = 0, id = 0;
memset(mp, 0, sizeof(mp));
for (i = 1; s[i] != '\0'; i++) {
p[i] = mx > i ? min(mp[2*id-i], mx-i) : 1;
while (s[i + mp[i]] == s[i - mp[i]]) mp[i]++;
if (i + mp[i] > mx) {
mx = i + mp[i];
id = i;
}
}
//找出mp[i]中最大的
整个manacher算法就是这些，另外贴一下该题目的代码，也是manacher的模板，模板取自上海大学kuangbin
#include<cstdio>
#include<cstring>
#include<algorithm>#define clr(a, x) memset(a, x, sizeof(a))
typedef long long ll;
typedef long double ld;using namespace std;const int maxn = 110011;
char ma[maxn * 2];
int mp[maxn * 2];void manacher(char s[], int len){int l = 0;ma[l++] = '$';ma[l++] = '#';for(int i = 0 ; i < len; i++){ma[l++] = s[i];ma[l++] = '#';}ma[l] = 0;int mx = 0, id = 0;for(int i = 0; i < l; i++){mp[i] = mx > i ? min(mp[2*id - i],mx - i): 1;while(ma[i + mp[i]] == ma[i - mp[i]])mp[i]++;if(i + mp[i] > mx){mx = i + mp[i];id = i;}}
}int main(){char s[maxn];while(scanf("%s", s) == 1){int len = strlen(s);manacher(s, len);int ans = 0;for(int i = 0; i < 2 * len + 2; i++)ans = max(ans, mp[i] -1);printf("%d\n", ans);}return 0;
}