Manacher 学习笔记

AutumnKite

笔记

发布于：2019年1月11日

次浏览

问题形式

给定一个字符串，求该字符串的最长回文子串。

洛谷传送门

一个简单的暴力实现

由于回文串是对称的，我们枚举对称轴（注意奇偶分类讨论）。然后从该对称轴向左向右扩展，直到两字母不相等。此时的字符串长度一定是以当前对称轴作为中心的最长回文子串。

时间复杂度\(\mathcal O(n^2)\)。

Manacher - 暴力的优化

为了避免奇偶分类讨论，我们现在字符之间以及字符串两端插入一个特殊字符（与字符串中所有字符都不相等）。

例如：ababaab -> #a#b#a#b#a#a#b#，显然，原来是回文串的还是回文串，原来不是回文串的仍然不是回文串，长度稍做处理即可。

通过观察发现，暴力主要慢在相同的状态被重复枚举，没有利用回文串的性质。

记\(hw_i\)表示以\(i\)为对称轴时，最长的回文串的右端距离\(i\)（包括最右端的字符和\(i\)）的长度为\(hw_i\)。栗子：

char:    # a # b # a #
 hw :    1 2 1 4 1 2 1

char:    # a # b # b # a #
 hw :    1 2 1 2 5 2 1 2 1

如何快速求出\(hw_i\)？

考虑根据回文串的性质，利用已经求出的\(hw\)值来求出当前的\(hw_i\)。

引入两个辅助变量\(MaxRight,Mid\)。\(MaxRight\)表示当前访问到的所有回文子串，所能触及的最右一个字符的位置，\(Mid\)表示对应的对称轴。

为方便观察，下面的图示中记\(x\)为\(MaxRight\)关于\(Mid\)对称的位置，\(r\)表示\(MaxRight\)，\(m\)表示\(Mid\)，\(*\)表示未触及的位置。

1	\| \| \| \| \|x\| \| \| \| \| \|m\| \| \| \| \| \|r\|\|\|*\|

当前要求\(hw_i\)的位置\(i\)一定在\(Mid\)右边。那么我们根据\(i\le MaxRight\)和\(i>MaxRight\)讨论：

当\(i\le MaxRight\)时

1	\| \| \| \| \|x\| \| \|j\| \| \|m\| \| \|i\| \| \|r\|\|\|*\|

记\(j\)为\(i\)关于\(m\)的对称点。由于\(hw_j\)已知，我们尝试利用\(hw_j\)得出\(hw_i\)的下界。

又分成两种小情况：

\(hw_j\)比较小，向左没有超过\(x\)

大概情况如图所示：

1	\| \| \| \| \|x\| \|-\|j\|-\| \|m\| \|-\|i\|-\| \|r\|\|\|*\|

此时显然\(hw_i\)的下界为\(hw_j\)。如图所示的情况一定也是上界，但如果\(i+hw_i-1\)刚好等于\(MaxRight\)，那么有可能可以继续扩展。由于不影响复杂度，为方便起见，无论哪一种情况都尝试扩展。

\(hw_j\)比较大，向左超过\(x\)

大概情况如图所示：

                    |             |
       /-------j----|--\          |
| | | | |x| | |j| | |m| | |i| | |r|*|*|*|
                   \|------i------|/
                    |             |

此时暂时只能确定两根较长的线之间的部分时回文的，所以\(hw_i\)的下界是\(MaxRight-i+1\)。然后同样地直接继续扩展即可。

实际实现中，这两种情况不需要特殊判断，只要在\(hw_j\)和\(MaxRight-i+1\)中取\(min\)即可。

当\(i>MaxRight\)时

此时显然\(hw_i\)的求值不能利用之前的任意值，所以定下界为\(1\)，也直接扩展即可。

总结

步骤

综上所述，从左到右枚举\(i\)的过程中，对于每个\(i\)，算法步骤如下：

若\(i\le MaxRight\)，则令\(hw_i=min(hw_{2*Mid-i}, MaxRight-i+1)\)，否则令\(hw_i=1\)（显然，\(i\)关于\(Mid\)的对称点\(j\)为\(2*Mid-i\)）。
以\(i\)为中心扩展回文串，直到左右两边字符不同，或者到达边界。
更新\(MaxRight\)和\(Mid\)。
更新答案。扩展出来的子串在原串中的长度一定为\(hw_i-1\)。因为在添加字符后的串中该子串长度为\(2hw_i-1\)，由于首尾一定是特殊字符，所以特殊字符数量比其他字符多\(1\)，所以特殊字符数量为\(hw_i\)，其他字符为\(hw_i-1\)。

一个小技巧

如果你的字符串下标从\(1\)开始，你可以令\(s_0\)为那个特殊字符，这样就省去了判断边界的问题。

复杂度分析

根据上面三种情况的分析，在继续扩展\(hw_i\)时，每一次的扩展都可以更新\(MaxRight\)，而\(MaxRight\)最多变化\(n\)次，所以总的时间复杂度为\(\mathcal O(n)\)的。

代码实现

#include <cstdio>
#include <algorithm>
char buf[11000005], *ps = buf;
int n, hw[22000005], mr = 0, mid = 0, ans = 0;
char s[22000005];
int main(){
    buf[fread(buf, 1, 11000005, stdin)] = '\0', s[0] = '#'; // 小技巧
    while (*ps >= 'a' && *ps <= 'z') s[++n] = '#', s[++n] = *ps, ++ps;
    s[++n] = '#'; // 插入特殊字符
    for (register int i = 1; i <= n; ++i){
        hw[i] = i <= mr ? std :: min(hw[(mid << 1) - i], mr - i + 1) : 1;  // 得出下界
        while (s[i - hw[i]] == s[i + hw[i]]) ++hw[i]; // 继续扩展
        if (i + hw[i] - 1 > mr) mid = i, mr = i + hw[i] - 1; // 更新mr,mid
        ans = std :: max(ans, hw[i] - 1); // 更新答案
    }
    printf("%d\n", ans);
}