- 基础方法：枚举子串，判断是否为回文串。
- 改进：枚举中间位置，向两侧拓展。
- 再改进：利用以前的信息，使得不用每个新位置都从长度1开始拓展。
- 优化：将字符串预处理为奇数长度以避免考虑条件分支。
- 再优化：开头加入特殊字符避免考虑边界。
Manacher 算法：
id 是中心点，mx 是其边界。P[i] 表示以 i 为中心的最长回文子串的折半长度。
只要 i < mx， 以 i 为中心的回文子串就可以不必从长度1开始找，而从min{P[j], mx - i}开始（其中j为i关于id的对称点）。
当mx可以向右前进时（i + P[i] > mx），改变id和mx的值。
具体实现的代码如下：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_SIZE 1000000
char str[2 * MAX_SIZE + 10];
int p[2 * MAX_SIZE + 10];
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", str);
int n = strlen(str);
for (int i = n - 1; i >= 0; i--) {
str[2*i+2] = str[i];
str[2*i+3] = ‘#‘;
}
str[0] = ‘$‘;
str[1] = ‘#‘;
memset(p, 0, sizeof(p));
int id = 0, mx = 0;
int res = 0;
for (int i = 1; i < 2*n+4; i++) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (str[i + p[i]] == str[i - p[i]]) {
p[i]++;
}
res = max(res, p[i]);
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
printf("%d\n", res - 1);
}
return 0;
}
吐槽：p数组大小没乘2，但是hiho居然报wa。白找了半天错。
Ref：http://taop.marchtea.com/01.05.html
原文：http://www.cnblogs.com/xblade/p/4439264.html