声明：这里仅仅写出了实现过程。想学习Manacher的能够看下这里给出的实现过程，算法涉及的一些原理推荐个博客。
给个链接
引子：给定一个字符串s，让你求出最长的回文子串的长度。
算法大致实现过程：
一：为了排除回文字符串长度奇或偶的影响。
先在每两个字符之间插入一个原字符串没有出现过的字符（这里就用#）构成新串str。设p[i] 为以str[i]字符为中心的回文字符串的最大半径。
则新串中以str[i]为中心的回文串长度为p[i]-1。
二：字符串从前到后求p[]数组。
（不要问为什么从前到后）
三：枚举全部p[i]值，更新最大值。
Manacher精华——求p[]数组。首先我们在求p[i]时，已经求出前面的p[j]值(0<=j<=i-1)
求p[i]的准备：
用mx记录 max{ k+p[ k ] } (0<=k<=i-1) ——前面全部回文字符串能覆盖到的最右边的位置。
用id记录mx取最大值时的k ——前面全部回文字符串中能覆盖到最右边位置 的那个以字符str[id]为中心的回文串。
（1）依据前面的p[]求p[i]
一，mx > i ——以str[id]为中心的回文字符串把字符str[i]覆盖到了。
这个情况下我们能够得到 ：p[ i ]= min( p[2*id - i ], mx - i )。（为什么？请看我推荐的博客）
二，mx <= i ——以str[id]为中心的回文字符串以字符str[i]结尾或者没有覆盖到字符str[i]。
这样的情况下p[i] = 1。由于回文串仅仅有它自己。（为什么？请看我推荐的博客）
（2）当然上面的处理还是不够的，由于处理过后得到的p[i]并不一定是我们所想要的最优的回文串半径。
（为什么？请看我推荐的博客）
兴许处理非常好理解的。
while(str[ i + p[i] ] == str[ i - p[i] ]) p[i]++;//向左右继续延伸 直到不能延伸为止
（3）每次求出p[i]后，能够先求出计算p[i+1]要用到的id。
代码实现：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 110100
using namespace std;
char s[MAXN];//原串
int str[MAXN*2];//新串 注意数组大小
int p[MAXN*2];
void Manacher(char *T)
{
int len = strlen(T);
int l = 0;
str[l++] = '@';//防止越界
str[l++] = '#';
for(int i = 0; i < len; i++)
{
str[l++] = T[i];
str[l++] = '#';
}
str[l] = 0;
int mx = 0, id = 0;
int ans = 0;
for(int i = 0; i < l; i++)
{
if(mx > i)//2*id-i 为 i关于id的对称点
p[i] = min(p[2*id - i], mx-i);
else
p[i] = 1;
//左右延伸
while(str[i+p[i]] == str[i-p[i]]) p[i]++;
if(i + p[i] > mx)//找计算p[i+1]用到的id
{
mx = i + p[i];
id = i;
}
ans = max(p[i]-1, ans);
}
printf("%d
", ans);
}
int main()
{
while(scanf("%s", s) != EOF)
{
Manacher(s);//求字符串s的 最长回文子串长度
}
return 0;
}
本人数据结构非常渣，有错误的地方欢迎指正。 (⊙o⊙)