先预处理下：在每个字符的两边都插入一个特殊的符号，比如abba变成#a#b#b#a#，aba变成 #a#b#a#（因为Manacher算法只能处理奇数长度的字符串）。同时，为了避免数组越界，在字符串开头添加另一特殊符号，比如$#a#b#a#。
以字符串3212343219为例，处理后变成S[] = "$#3#2#1#2#3#4#3#2#1#9#"。
然后用一个数组Len[i]来记录以字符S[i]为中心的最长回文子串的半长度（包括S[i]）：
S # 3 # 2 # 1 # 2 # 3 # 4 # 3 # 2 # 1 # 9 # Len 1 2 1 2 1 6 1 2 1 2 1 8 1 2 1 2 1 2 1 2 1
（最终的回文子串的长度即为maxLen-1）
下面两幅图的红框中的字符串为当前的右边界下标最大的回文子串，mid为其中心，right为其最右端+1，i‘=2*mid-i为i关于mid的对称点。
现要计算Len[i]，若以i‘为中心的回文串（黄框）包含在最长回文子串中，则由回文串的对称性，以i为中心的回文串亦在最长回文子串中，即有Len[i]=Len[2*mid-i]
若以i‘为中心的回文串（黄框）不包含在最长回文子串中，则以i为中心的回文串的半长度Len[i]=right-i+(之后继续判断的长度)
那么，为什么复杂度是O(n)的呢？
首先，主要影响复杂度的是s[i + len[i]] == s[i - len[i]]这一判断。
由下面的代码可知，当i<right时，我们就用常数的时间计算Len[i]（此时不会执行while中的语句）；当i>=right时，我们就继续判断：while (s[i + len[i]] == s[i - len[i]]) ++len[i]; 结束后，right < i + len[i]为真，更新right值。这样，我们至多进行n次s[i + len[i]] == s[i - len[i]]判断，故复杂度为O(n)。
完整代码：
#include<bits/stdc++.h>
using namespace std;
const int mx = 10000;
char ss[mx + 5], s[2 * mx + 5];
int len[2 * mx + 5];
void debug()
{
int i;
for (i = 1; s[i]; ++i) printf("%c ", s[i]);
puts("");
for (i = 1; s[i]; ++i) printf("%d ", len[i]);
puts("");
}
int main()
{
int right, mid, i, maxlen;
while (gets(ss))
{
memset(s, 0, sizeof(s));
s[0] = ‘$‘;
for (i = 0; ss[i]; ++i) s[2 * i + 1] = ‘#‘, s[2 * i + 2] = ss[i];
s[2 * i + 1] = ‘#‘;
memset(len, 0, sizeof(len));
maxlen = right = mid = 0;
for (i = 1; s[i]; ++i)
{
len[i] = (i < right ? min(len[(mid << 1) - i], right - i) : 1);
/* 取min的原因：记点i关于mid的对称点为i‘，
若以i‘为中心的回文串范围超过了以mid为中心的回文串的范围
(此时有i + len[(mid << 1) - i] >= right，注意len是包括中心的半长度)
则len[i]应取right - i(总不能超过边界吧) */
while (s[i + len[i]] == s[i - len[i]]) ++len[i];
maxlen = max(maxlen, len[i]);
if (right < i + len[i]) mid = i, right = i + len[i];
}
printf("%d\n", maxlen - 1);
debug();
}
return 0;
}
例题：