http://acm.hdu.edu.cn/showproblem.php?pid=3068
最长回文
Problem Description
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理) 字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaa
abab
Sample Output
4 3
下面简单说下看了Manacher算法的想法，我是通过 https://www.felix021.com/blog/read.php?2040 学到的，具体的学习可以参考该博客。
当时一看这个算法觉得十分厉害啊，先把我们要求的字符串先预处理一下，把无论奇偶长度的字符串都变成奇数长度的，就是例如样例，我们把“aaaa”变成“#a#a#a#a#”，这样来处理成一个新的字符串S，然后再用一个数组P来表示当在S【i】的时候，以S【i】为中心的最长回文子串向左右扩张的最大长度，例如上面的例子，当i = 5的时候，P【5】= 5，当i = 2的时候P【i】= 2，所以明显地可以看到，我们以S【i】为中心对折对应的回文子串，对折之后的长度就是P【i】（算长度的时候在S【i】自己也是要算一位的）。那么我们可以发现，P【i】- 1表示的就是原字符串的回文子串长度。
接下来就是比较重点的地方就是算P【i】。在这里引入两个变量 id，xr，xl。id表示目前能够得到的最长的回文子串的中心，xr是该回文子串的右边界。即 xr = id + P【id】，同理xl是该回文子串的左边界，即xl = id - P【id】。
当 i < xr 的时候，我们设一个变量 j = id * 2 - i = id + （id - i），即 j 是 i 以 id 为对称点翻折过去的位置， 因为我们跑到 i 这个位置的时候，前面的 P【j】肯定被更新过了，那么可以根据P【j】和 xr - i 的关系来判断P【i】的长度。
如果P【j】 > xr - i的话，那么意味着以 j 为中心的回文子串不完全包含在以 id 为中心的回文子串里面，那么我们并不能就这样完全判断出P【i】的长度了，我们只能够了解到，因为 i < xr ，所以 j > xl，所以以 j 为中心的回文子串是有一部分包含在以 id 为中心的回文子串里边的，那么只能保证 P【i】的长度是至少有 xr - i 那么长的。至于剩下还有多长，只能用一个循环再去匹配更新P【i】了。
如果P【j】 < xr - i的话，那么相当于以 j 为中心的回文子串完全包含在了以 id 为中心的回文子串里边，又因为 i 和 j 是关于 id 对称的并且回文串的一边和另一边是相同的，所以P【i】的长度可以直接求得等于P【j】了。
所以在 i < xr 的情况下，我们可以总结得到 P【i】= min（P【j】，xr - i ）。其中 j = id * 2 - i。
上面都是 xr > i 的情况，那么 xr < i 的情况我们未知，只能设P【i】只包含自己本身即等于1，然后慢慢去匹配了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 110010
char str[N];
char s[*N];
int p[*N];
int l;
//求最长回文子串的Manacher算法
void init()
{
memset(p, , sizeof(p));
int len = strlen(str);
s[] = '%';
l = ;
for(int i = ; i < len; i++) {
s[l++] = '#';
s[l++] = str[i];
}
s[l++] = '#';
s[l] = '\0';
} int manacher()
{
init();
int xr = , id = ;
for(int i = ; s[i]; i++) {
p[i] = xr > i ? min(p[id*-i], xr - i) : ;
while(s[i+p[i]] == s[i-p[i]]) p[i]++;
if(i + p[i] > xr) {
xr = i + p[i];
id = i;
}
}
int ans = ;
for(int i = ; i < l; i++) {
if(p[i] - > ans) ans = p[i] - ;
}
return ans; } int main()
{
while(~scanf("%s", str))
printf("%d\n", manacher());
return ;
}