Manacher 学习笔记

发表于 分类于

简介

$ Manacher $ ，俗称马拉车，是一种可以在 $ O(n) $ 的时间复杂度下，求出一个字符串的所有回文子串的神奇算法。

思想

暴力拆出主串的子串，时间复杂度 $O(n^3)$。

对于每一位向外延伸，时间复杂度 $O(n^2)$。

如何优化？

奇数长度回文

记 $d_i$ 表示以 $i$ 为对称中心的奇数长度回文子串，右端点为 $i+d_i$。

发现在第 $i$ 位向外延伸时，若 $i$ 在一个确定的回文区间 $[l,r]$ 内，将 $i$ 对称得到 $j(j<i)$ 后，$d_i\ge d_j$。

用符号表示则是对 $\forall k\in [1,d_j]$，$s_{d_i+k}=s_{d_j-k}=s_{d_j+k}=s_{d_i-k}$。

但是如果 $i+d_i>r(j-d_j<l)$，就无法保证 $s_{d_i+k}=s_{d_j-k}$ 和 $s_{d_j+k}=s_{d_i-k}$。

所以 $d_i=\min (d_j,r-i)$。

之后再暴力向外拓展，尽可能增大答案。

显然区间 $[l,r]$ 的右端点越大越好，记得每一位操作后都要更新。

偶数长度回文

最讨厌分类讨论了 $qwq$。

这里有个很作弊的处理方法。

预处理时，往两每个字符中间和字符串头尾塞一个不在字符集中的字符。

比如 $abcde\to a$#$b$#$c$#$d$#$e$#。

这样当处理到 # 字符的时候，奇数长度的回文就是原字符串的偶数长度回文辣！

此时 $d_i$ 就直接代表了原串回文的长度。

实现

再往原串最前面丢个 $($ 之类的，由于 $(\not=$ #，一旦遍历到就会停止。

连判断越界都免了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 2.2e7;

string a;
char s[N + 2];
int n;
int d[N + 2];
int ans;

inline void init()
{
    s[0] = '(';
    s[1] = '#';
    for (int i = 0; i < n; i++) {
        s[(i + 1) << 1] = a[i];
        s[((i + 1) << 1) + 1] = '#';
    }
    n = (n + 1) << 1;
    return;
}
inline void manacher()
{
    int l = 0, r = -1;

    for (int i = 1; i < n; i++) {
        if (i < r)
            d[i] = min(d[l + r - i], r - i);
        while (s[i - d[i] - 1] == s[i + d[i] + 1])
            d[i]++;
        if (i + d[i] > r) {
            r = i + d[i];
            l = i - d[i];
        }
        ans = max(ans, d[i]);
    }
    return;
}
int main()
{
    cin >> a;
    n = a.size();

    init();
    manacher();

    printf("%d\n", ans);
    return 0;
}