Manacher 算法学习笔记

十一月 01, 2018 4149

O(n) 回文串

Manacher 是什么

Manacher 是一种可以在 O(n) 的时间复杂度内求出一个字符串的最长回文子串的算法。

Manacher，中文一般念做「马拉车」。

Manacher Algorithm 的思想

首先我们来看一道题洛谷P3805【模板】manacher算法。

考虑一下暴力做法，就是枚举字串的边界并进行验证，时间复杂度 O(n^3)

考虑一下优化，我们可以枚举所有“回文子串”的对称轴（尽管它现在不一定是回文子串）并向两边进行扩展，用一个数组external[i]记录第i个字符可向外扩展的数量，显然数组中最大值的二倍就是答案，时间复杂度均摊 O(n^2) 。

但这还不够快……毕竟 \text{|s|} \leq 11000000

于是我们考虑在优化的思想基础上进行再次优化。

在此之前，我们首先要解决一个棘手的问题——字符串的长度。
一个字符串子串的对称轴是在字母中间还是在字母上，是由子串长度为偶数还是奇数决定的。于是，为了统一对于奇数长度字符串和偶数长度字符串的做法，我们需要对字符串进行修改。（代码见「代码实现」Pre()部分）

1
2
3
4
5
6
7
就比如说
 - - - - - -
|%|%|%|w|y|h|
我们要用一些无关紧要的字符填一下
 - - - - - - - - - - -
|%|!|%|!|%|!|w|!|y|!|h|
这样更好处理

修改完了之后，就是真正的Manacher()过程了
首先，我们要用一个变量maxRight记录「当前的 最靠右的 回文子串的 右端点」，和一个变量mid记录「当前的 最靠右的 回文子串的 对称轴所在的 字符的 下标」，注意这里的mid是可以不赋初值的

我们循环枚举经过处理的字符串的每一个字符。对于每一个字符的下标i，如果i < maxRight，那么我们就可以获取external[i]的部分信息（external[i]的意义和上文相同），否则就只能将external[i]设为1

接着就是和暴力一样的扩展了，我这里选择用for语句实现（

最后更新一下maxRight和mid即可

最终答案就是external[]的最大值——而不是2倍，因为这是我们扩展过的字符串，最终答案还要 \times \frac{1}{2} 。

Manacher Algorithm 的代码实现

同样也是「manacher模版」的代码实现。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 31000000 + 10;
    // 没错，就是要开这么大
    
    int n, external[MAXN];
    char s[MAXN], str[MAXN << 1];
    
    void Pre() {
        str[0] = str[1] = '~';
        for (int i = 0; i < n; ++i) {
            str[i * 2 + 2] = s[i];
            str[i * 2 + 3] = '~';
        }
        n = n * 2 + 2;
        str[n] = 0;
    }
    
    void Manacher() {
        int maxRight = 0, mid = 0; // mid 初值无所谓
        for (int i = 1; i < n; ++i) {
            if (i < maxRight) {
                external[i] = std::min(external[(mid << 1) - i], external[mid] + mid - i);
            } else {
                external[i] = 1;
            }
            for (; str[i + external[i]] == str[i - external[i]]; ++external[i]);
            if (external[i] + i > maxRight) {
                maxRight = external[i] + i;
                mid = i;
            }
        }
    }
    
    void Work() {
        cin >> s;
        n = (int) strlen(s);
        Pre();
        Manacher();
        int ans = 1;
        for (int i = 0; i < n; ++i) ans = std::max(ans, external[i]);
        cout << ans - 1 << endl;
    }
}

int main(int argc, char *const argv[]) {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using namespace FastIO;
    Work();
    return 0;
}