Manacher算法

求解一个字符串s中的最长子串，一般的方法是，遍历s中每个字符e，以字符e为回文中心，向两边拓展，求以字符e为回文中心的最长回文串的长度，这样的方法时间复杂度为 $O(n^2)$ 。鉴于其复杂度，出现了Manacher’s Algorithm，中文名叫马拉车算法，是一位名叫Manacher的人在1975年提出的一种算法。该算法可以在 $O(n)$ 时间复杂度内求解一个字符串中的最长回文子串，也可以求解一个字符串中回文子串的总数。

方法

1. 预处理

由于回文串分为偶回文（比如 bccb）和奇回文（比如 bcacb），处理过程中需要考虑不同的情况，于是Manacher算法对字符串进行了预处理，过程如下：

在所有的相邻字符中间插入 #，例如字符串ab，添加#变为 #a#b#。
字符的首尾加入两个不同的字符，例如？和 ! , s成为 ?#a#b#!。

预处理好处是，如果从#开始拓展回文字符串，那么得到回文子串对应 s 中的偶回文。如果非#的字符开始拓展，找到的回文字符串对应 s 中的奇回文，在处理的过程中不用考虑奇回文还是偶回文的问题，以任意一个字符为回文中心，既可以包含原来的奇数长度的情况，也可以包含原来偶数长度的情况。并且这种处理方式的特点是，对处理后的字符串，以每一个字符为回文中心进行拓展，每次拓展得到的回文数的首尾一定是#，并且其长度是奇数。预处理后可以进入求解过程。

2. 求解

假设原字符串为 s，预处理后的字符串为T。

定义一个辅助数组f，f[i]表示T中以字符T[i]为回文中心的最长回文半径，例如#c#a#c#，以字符a为回文字符串的最长半径为 4。f[i] - 1是s中以T[i]为回文中心的最大回文串长度，该问题的证明见推论1及其证明。
Manacher 算法依旧需要枚举 T 的每一个字符并先假设它是回文中心，但是它会利用已经计算出来的状态来更新$ f(i) $。假设我们已经计算好了$ [1, i-1]$区间内所有点的 $f$ （即我们知道 $[1, i-1]$ 这些点作为回文中心时候的最大半径），那么我们求出 $[1, i-1]$ 范围内字符拓展出的最长回文字符串的右端点。
例如 i = 4 的时候 f(i) = 5，说明以第 4 个元素为回文中心，最大能拓展到的回文半径是 5，此时对应最长回文字符串的右端点的索引为 4 + 5 - 1 = 8。所以我们可以根据 i以及f(i)时，可以很容易得到它的右端点为$ i + f(i) - 1$。
已知 $[1, i-1]$ 范围的 f 求解f(i)时，Manacher 算法要求我们维护 $[1, i-1]$ 范围内每个字符最长回文字符串的右端点的最大值rm，以及该字符串的回文中心im。
整个过程如下：初始时令 im = 0， rm = 0，遍历T中[0, T.size()-1]范围内每个 i ：
1. 初始化f(i)
  1. 如果$ i ≤ rm $说明被包含在[0, i-1]范围内某个字符的最长回文子串中，假设 j 是 i 这个最大回文字符串回文中心 im 的对称位置, 经过Manacher算法处理的最长回文字符串始终是奇数，因此$ j + i = 2 \times im $, 于是我们令$ f(i) = min(f(j), rm-i+1)$,这一步骤为什么取最小值的原因，见推论2及其证明。
  2. 初始化 $f(i) = 1f(i)=1$ 。
2. 中心拓展
  1. 做完初始化之后，因为 $i + f(i)-1$ 是T[i]字符最长回文字符串的右端点，所以可以保证 $T[i + f(i) - 1] = T[i - f(i) + 1]$ ，要继续拓展这个区间，我们就要继续判断 $T[i + f(i)]$ 和 $T[i - f(i)]$ 是否相等，如果相等则将 $f(i)$ 自增；这样循环直到 $s[i + f(i)] \neq s[i - f(i)] $。
  2. 遍历结束后如果 $i + f(i)-1 > rm$ , 则更新 $ rm = i + f(i)-1, im = i$。
  3. 可以看出循环每次结束时都能保证 $T[i + f(i) - 1] = T[i - f(i) + 1]$ ，而循环继续（即可拓展的条件）一定是 $T[i + f(i)] = T[i - f(i)]$ 。这个时候需要注意不能让下标越界，但是Manacher方法中在字符串的开头加一个 ?，并在结尾加一个 !，这样开头和结尾的两个字符一定不相等，就可以保证每次 $f(i)$ 自增的时候不会越界。

证明

推论1

f[i]表示T中以字符T[i]为回文中心的最长回文字符串的半径， f[i] - 1是s中以T[i]为回文中心的最大回文串长度。

证明

假设原字符串中，第i个字符最大回文串长度为L，经过马拉车算法处理后的回文字符串长度增加了L+1，总长度为2L+1.已知在处理后的字符串中，第i个字符的最大回文半径为f(i), 则其回文字符串长度为2*f(i)-1 = 2L+1, 由此可知 L = f(i)-1。

推论2

$f(i) = min(f(j), rm-i+1)$

证明

                                ---X----j---------Im---------i------rm---

上图中，以im为中心的最长回文字符串的右端端点为rm, 如果i<=rm，说明 i 被包含在im为中心的最长回文字符串中，假设j是最长回文字符串中i在左侧的对称位置，再假设X是最长回文串rm对应的最左端断点，其中X<=j，已知以j为中心的回文字符串长度为f(j), f(i)的初始化分下列两种情况：

case 1：如下图所示，如果j的最长回文串的最左侧端点y不在X的左侧(在右侧或者与X重合)，说明y也包含在i的最长回文字符串中，根据i和j的对应关系可知 $f(i) >= f(j)$ ，并且 $f(j) <= rm -i+1$ , 因此把f(i)初始化为f(j)。
```
                            ---X--y--j--y------Im-------y--i--y----rm---
```
case 2：如下图所示，如果j为中心的最长回文串的最左侧端点在X左侧，说明y不在i的最长回文字符串中，此时 $rm-i+1 < f(j)$ , 根据i和j的对应关系，我们最多可知 $f(i)$ 的长度至少为 $rm -i +1$ ,因此把 $f(i)$ 初始化为 $rm-i+1$ 。
```
                               -y--X----j--------Im---------i------rm---
```

综合case1 和case2， f(i)的长度最大不应该超过rm-i+1, 因此$f(i) = min(f(j), $rm -i +1$ )$;

示例代码

下列代码求解一个给定字符串中回文字符串的总数：

int manacher(string s) {
        string mlcStr;
        mlcStr.reserve(s.size()*2+3);
        // 预处理
        mlcStr.push_back('S');
        mlcStr.push_back('#');
        for(const auto& e: s){
            mlcStr.push_back(e);
            mlcStr.push_back('#');
        }
        mlcStr.push_back('!');
		// 定义f，遍历mlcStr并求解,将遍历范围控制在[1, mlcStr.size()-1]，排除了？和！，保证数组不会越界
        vector<int> f(mlcStr.size(), 1);
        int im = 0, rm = 0, res = 0;
        for(int i = 1; i < mlcStr.size()-1; ++i){
            // 初始化f[i]
            if(i <= rm)
                f[i] = min(rm - i + 1, f[2*im - i]);
            // 中心拓展
            while(mlcStr[i+f[i]] == mlcStr[i-f[i]]) f[i]++;
            // 更新rm和im
            if( i + f[i]-1 > rm){
                rm = i+f[i]-1;
                im = i;
            }
            // 求和
            res += f[i]/2;
        }
        return res;
    }

复杂度分析

从实现代码来看，由于有两层循环，看起来貌似是 $O(n^2)$ 级别，但是实际上:

如果每次 $f(j)$ 的值不等于 $rm - i + 1$ 的时候，i的最长回文字符串都无法更新，如果可以更新，根据回文字符串可以推出矛盾，这种情况下rm和im不会更新。
如果 $f(j) == rm - i + 1$ ，此时以T[i]为回文中心的最长回文字符串有可能更新，而rm只能增大不会减小，rm最多更新T.size()次。
假设原来s长度为L，那么预处理后T变为 $2L+1$ 次(除去头尾添加的字符，因为实际遍历过程中排除了这两个字符)，rm最多更新 $2L+1$ 次，于是整个字符串的便利操作和和中心拓展最多为 $2L+1+2L+1 = 4L+2$ 次，因此其时间复杂度为 $O(n)$ ，平均访问次数为 $(4L+2)\div L = 4$ 次。
由于使用了额外的空间，其空间复杂度为 $O(n)$ 。
如果想看更加详细的证明，可以参看这里。
力扣题目链接：回文子串