Manacher 笔记

tuxiaolai · 2026-07-15 21:30:50 · 算法·理论

刚刚学完 Manacher 并做一些笔记

蒟蒻曾今在 NOIP 的前一天晚上开倍速看 Manacher 视频并得到了 0 收获。

1. 目标 & 定义

luogu P3805 【模板】Manacher

我们的目的是找出一个字符串中回文串的数量或最大长度等。

当字符串 t = t_{rev} 时，t 是一个回文串。（t_{rev} 是 t 的反转字符串）

敢来学 Manacher 的人真的有不知道回文串是什么的吗？

首先，我们知道回文串的长度有奇数和偶数两种，我们先只考虑奇数长度的回文串。
过程部分的“回文串”均指奇数长度的回文串。

我们定义回文串最中间的字符到最右边字符之间的字符数（包括两端）为回文串的半径 d。
那么回文串的长度就是 d \times 2 - 1。
例如回文串 abcba 的 d 就是 3。

定义以字符串 s 的第 i 个字符为中心的回文串的最大半径为 d_i。
显然，以第 i 个字符为中心，半径 \le d_i 的子串都是回文串。

接下来，我们的目标就是找到这个 d_i 数组。

2. 过程

首先，最简单的思路就是从 i 开始不断判断两侧的字符是否一样，不一样则结束。
代码如下：

d[i] = 1;  
while (0 <= i - d[i] && i + d[i] < s.size() && s[i - d[i]] == s[i + d[i]]) {  
    d[i]++;  
}

我们将这个过程称为暴力寻找。

接下来我们来看 Manacher 算法的过程：

依次遍历每个下标，遍历过程中我们记录前面找到的回文串（即以前面某个字符为中心的回文串）中右端点最大的回文串的两个端点 l 和 r。

当遍历到 i 时，若 r < i，我们无法从前面的 d 中获取经验，那就只能暴力寻找。

若 i \le r ，由于 l \sim r 这个回文串的左右两侧是相同的，所以我们显然可以从 i 在回文串中的对应点找到经验，这个对应点应当是 l + r - i。

我们令 j = l + r - i
情况应当是这样：

s: ----------------------
l~r:  ------*------
       -j-      i

或者是这样：

s: ----------------------
l~r:  ------*------
     ---j---    i

也就是说以 j 为中心的最大回文串可能在 l \sim r 的范围内，也可能超出了该范围。
注意：即使 j 的最大回文串左端恰好是 l 也算作超出范围。

• 如果没有超出范围，那么 d_i = d_j 是显然的，因为 j 的最大回文串以外两端字符不同，i 的最大回文串以外两端也是不相同的，d_j 自然就是最大的了。
• 如果超出了范围，由于 j 的最大回文串以外两端与 i 的不同，我们最多只能将在 l \sim r 范围内的部分使用，而其余部分只能暴力寻找。上文“注意”中提到的情况正是因为此时最大回文串外两端已经超出了 l \sim r 的范围，i 和 j 的情况不能类比。

当然过程中应当更新 l 和 r。

事实上，Manacher 算法的本身并不复杂，一般人其实也未必想不到。

string s;  

int d[N];  

void Manacher() {  
    int l = 0, r = -1;  
    for (int i = 0; i < s.size(); i++) {  
        d[i] = (i > r) ? 1 : min(r - i + 1, d[l + r - i]);  
        while (0 <= i - d[i] && i + d[i] < s.size() && s[i - d[i]] == s[i + d[i]]) {  
            d[i]++;  
        }  
        if (i + d[i] - 1 > r) {  
            r = i + d[i] - 1;  
            l = i - d[i] + 1;  
        }  
    }  
}

3. 复杂度

Manacher 最令人困惑的一点就是它的时间复杂度，很难想象这种动不动就暴力的算法竟然是 O(n) 的。

我们发现算法的过程主要有 3 种。

• 直接暴力寻找
• 直接从对应点获取
• 从对应点获取部分结果后暴力寻找 显然第二种操作的复杂度是 O(1) 的

对于另外两种操作，我们聚焦最大回文串右边界 r 的变化。
对于第一种操作，本身 r < i，暴力寻找时这个 r 就会不断增加。
对于第三种，我们从 r 处开始暴力寻找，r 也会不断增加。

也就是说没暴力一次，r 都会增加，而 r 的范围是 0 \sim n，那么复杂度自然也是 O(n) 的了。

4. 其他

对于偶数的情况：

for (int i = 0, l = 0, r = -1; i < n; i++) {
  d[i] = (i > r) ? 0 : min(d[l + r - i + 1], r - i + 1);
  while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
    d[i]++;
  }
  if (i + k > r) {
    l = i - k;
    r = i + k + 1;
  }
}

这里我们定义的中心是中间两个字符中靠右的那个。

还有一种奇妙的技巧，我们在每个字符以及收尾都插入一个不在原字符串中的字符，如 #。例如将 abba 改为 #a#b#b#a#，那么不难发现所有的回文串都变成了奇数长度，而 d_i 则变成了回文串长度 +1，这样我们就可以将两种情况统一了。

5. 一道奇妙的例题

luogu P4555 [国家集训队] 最长双回文串

题目大意就是说要找出字符串中长度最大的子串，满足可以将这个子串分割成非空的两段，且这两段都是回文串。

题解中有一种简单的 O(n) 做法，但是我这里提供一种奇妙的 O(n \log n) 做法。

首先：如果我们已经确定了左右两个回文串的中心，且他们的最长回文串中间没有空隙，那么无论两端回文串的长度取多少，总长度应当是固定的。因为两个中心中间的的字符数量与两端的字符数量是相等的。

那么对于一个右边中心 i，我们要找的是满足 j < i 且 r_j \le l_i 的最小 j。（其中 l_i 和 r_i 分别是最大回文串的左右端点）

不难想到我们可以用线段树，以 r_j 的值作为下标，维护区间最小 j 值。

但是由于我懒得写线段树，于是想到了一种类似单调栈的做法。

在不考虑 j 的大小的情况下，r_j 自然是越大越好的。那么如果说 j < i 且 r_i \le r_j，那么 i 在选取上是没有任何贡献的，因为选择 j 一定比选择 i 更优。沿用单调栈的思路，我们从左往右遍历时，如果说 r_i 比栈顶的 r 值更小或相等，我们就不必将 i 加入栈中。此时就可以保证栈中的 r_j 值时单调递增的，而 j 也是单调递增的。那我们只要用二分，找到栈中第一个 l_i \le r_j 的值即可。

// ^_~ Accepted  
// All-Kill Automaton   RP++  
// [AC] WA CE RE TLE MLE...  

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  

const int N = 1e6 + 10;  

int d[N];  

int l = 0, r = -1;  

int n;  
string s, y;  

void Manacher() {  
    for (int i = 0; i < n; i++) {  
        d[i] = (i > r) ? 1 : min(r - i + 1, d[l + r - i]);  
        while (0 <= i - d[i] && i + d[i] < n && y[i - d[i]] == y[i + d[i]]) {  
            d[i]++;  
        }  
        if (i + d[i] - 1 > r) {  
            r = i + d[i] - 1;  
            l = i - d[i] + 1;  
        }  
    }  
}  

struct Node {  
    int i, r;  

    bool operator<(const Node &rhs) const {  
        return r == rhs.r ? i < rhs.i : r < rhs.r;  
    }  
};  

Node stk[N];  
int top = 0;  

int main() {  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  

    cin >> s;  

    y = "#";  
    for (char ch: s) {  
        y += ch;  
        y += '#';  
    }  

    n = y.size();  

    Manacher();  

    int yyy = 0;  

    for (int i = 0; i < n; i++) {  
        if (top) {  
            int it = lower_bound(stk + 1, stk + 1 + top, (Node){0, i - d[i]}) - stk;  
            if (it <= top && d[i] - 1) {  
                yyy = max(yyy, i - stk[it].i);  
            }  
        }  
        if (stk[top].r < i + d[i] - 1) {  
            stk[++top] = {i, i + d[i] - 1};  
        }  
    }  

    cout << yyy << endl;  

    return 0;  
}

6. 结语

你不会以为我真的编得出结语吧……