算法功能

回文字符串的通俗定义是：如果一个字符串正着读或反着读都一样，那么称这个字符串为回文字符串。Manacher的作用就是在O(N)的时间复杂度下求出以每个位置为回文中心的回文半径。

算法实现

接下来我们来看看Manacher算法的原理和实现方法吧。

我们还是采用动态规划的思想，假设0~i的位置的回文半径都求出来了，那么怎么求第i+1个位置的回文半径呢？

考虑如果i+1这个位置在被之前覆盖范围最远的一个回文串包含（假设这个回文串的回文中心为j），那么i+1关于j对称的位置（不妨设为k）就可以转移到i+1这个位置，给i+1位置的回文半径一个初始的值。如果不被之前求过的任意字符串包含的话，那么显然为1（它自己）。

Example

接下来我们要考虑是否i+1位置和k位置的差别。显然，i+1个位置可能还可以继续拓展，那么直接拓展即可（想想时间复杂度为什么是对的）。

我们把每个字符作为回文中心去处理，那么很显然对于长度为偶数的回文串无法得到很好的处理，怎么办呢？

其实我们只要在每个字符中间加入一个该字符串没有的符号，并且在头尾加入没出现过的不同的符号就行了（如下面这个字符串）。

处理过后的字符串

Code

s[0] = '$'; s[++m] = '#';
for (b = 1; ss[b] != '\0'; ++b) {
    s[++m] = ss[b];
    s[++m] = '#';
}
s[++m] = '?';
for (int i = 1; i < m; ++i) {
    if (maxid > i) p[i] = min(maxid-i, p[2*id-i]);
    else p[i] = 1;
    while (s[i-p[i]] == s[i+p[i]]) p[i]++;
    if (i + p[i] > maxid) {
        maxid = i + p[i];
        id = i;
    }
}

时间复杂度证明

我们考虑产生复杂度的地方，分别是最外层对整个字符串的遍历和每次对回文串扩展的while。

显然，最外层的for循环是O(N)的，那么我们只需要证明while的总循环次数也是O(N)级别的即可。

很容易发现，每次进入while，回文串的最大覆盖范围都会加1.（为什么呢？）

1、如果以i位置的为回文中心的回文串的基础长度没有超出当前回文串的最大覆盖范围，那么显然不会进入while中（由于对称性，该回文串的长度已经最大了）。

2、如果以i位置的为回文中心的回文串的基础长度超出了当前回文串的最大覆盖范围，那么显然每进入一次while，回文串的最大覆盖范围都会加1.那么，当最大覆盖范围包含了整个字符串之后，while循环就不会在进入了。所以while循环的总次数为O(N)。综上所述，Manacher算法的时间复杂度为O(N)。