Manacher 算法

Manacher 推广

如果我们的 pattern 拥有如下的一些性质，那么我们就可以利用 Manacher 进行加速：

  1. 具有类似回文的对称性。如果维护的回文 Box 为 [l,r][l,r]，那么这种对称性使得 R[i]R[i] 至少 ≥R[l+r−i]\ge R[l+r-i].
  2. 外推性：如果 s[l…r]s[l\dots r] 满足性质，那么 s[l+1…r−1]s[l+1\dots r-1] 也应该满足性质

例题

P3501 [POI 2010] ANT-Antisymmetry

题目所描述的 pattern 符合外推性：一个合法的 pattern 必须有 s[0]≠s[−1]s[0]\ne s[-1], 去掉之后的子串也必然满足"反对称".

而且也具有对称性。于是可以使用 Manacher 算法，而且反对称的串长必为偶数，我们在数字中间 pad 字符，这样就可以向 Manacher 那样了。时间复杂度 O(n)O(n)

Code
 
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
#include <iostream>
#include <string>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    std::string T = ".";
    for (auto c : s) T += c, T += ".";
    int L = T.length();
    std::vector<int> R(L + 1, 0);

    auto check = [&](int p1, int p2) {
        if (T[p1] == '.' && T[p2] == '.') return true;
        else if (T[p1] == '1' && T[p2] == '0') return true;
        else if (T[p1] == '0' && T[p2] == '1') return true;
        else return false;
    };

    int C = 0, r = 0;
    long long ans = 0;
    for (int i = 0; i < L; i += 2) {
        int reflect = 2 * C - i;
        int k;

        if (i <= C + r) k = std::min(R[reflect], C + r - i);
        else k = 0;

        while (i - k >= 0 && i + k < L && check(i - k, i + k)) k++;

        R[i] = k - 1;

        if (i + R[i] > C + r) {
            C = i;
            r = R[i];
        }
        ans += R[i] / 2;
    }
    std::cout << ans << std::endl;
}