Znzryb's Blog
0%

完全理解 manacher

Posted on Edited on

manacher

马拉车算法其实和这个 kmp，z 函数还是有异曲同工之妙的。

我们维护一个最远的回文串边界，记为 r。

image

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

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s){
    int n=SZ(s);
    s='$'+s+'^';
    vector<ll> p(n+2);
    ll l=0,r=1;     // (l,r) 是开区间，其内部是这个回文子串
    for(int i=1;i<=n;++i){
        // 保底半径
        p[i]=min(r-i,p[l+r-i]);
        // 暴力外扩
        while (s[i-p[i]]==s[i+p[i]]) { // 因为有哨兵，永不越界
            p[i]++;
        }
        if(i+p[i]>r){
            l=i-p[i],r=i+p[i];
        }
    }
    return vector<ll>(p.begin()+1,p.end()-1);
}
vector<ll> manacher(const string &s){
    string t;
    for(auto c:s){
        t+='#';     // 千万不要    t+='#'+'c'
        t+=c;
    }
    t+='#';
    auto res=manacher_odd(t);
    return vector<ll>(res.begin()+1,res.end()-1);
}
// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

可以这样子使用这个差分，得到以该点起点的的这个回文串的数量。

1
2
3
4
5
6
7
8
9
10
11
12
vector<ll> ps = manacher(s);
vector<ll> cntS(szs + 3);
for (int i = 0; i < SZ(ps); ++i) {
    ll r = ps[i] / 2;
    if (r == 0) {
        continue;
    }
    ll pos = i / 2;
    cntS[pos - r + 1]++;
    cntS[pos + 1]--;
}
partial_sum(all(cntS), cntS.begin());