马拉车学习笔记

概念与定义：

回文串：S=R(S)

回文中心：

  • 奇长度：回文中心为S[n+12]S[\frac{n+1}{2}],如abcbaabcba
  • 偶长度：回文中心在S[n2]与S[n2+1]S[\frac{n}{2}]与S[\frac{n}{2}+1]之间,如$ abc|cba$。

回文半径L：回文中心到回文串左右端点的距离，常用二元组<回文中心，回文半径>< 回文中心，回文半径>来表示一个回文子串.

回文长度和回文半径的关系：

  • 奇长度回文串：∣S∣=2L−1|S|=2L-1
  • 偶长度回文串：∣S∣=2L|S|=2L

回文半径的二分性：回文半径-1 等价于同时删掉回文串的首尾字母，依然是回文串。

回文串和 Border：对于回文串 S，回文前（后）缀等价于Border。因此得到结论：回文串的回文前后缀都是border（!!!)

算法预处理：为了将偶回文串的处理方式与奇回文串统一起来，将 S 的每两个字母中间，以及开头结尾插入 。

  • 因此所有回文串都变成奇数长度，且首尾一定是 #。
  • 所有极长回文子串长度一定为奇数：因为极长回文子串一定以 #开头结尾。

P[i] 表示以 i 为回文中心的最大回文半径。

板子：传入0base0base即可

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
struct PAS {
    string s = "#";
    int len = 1;
    vector<int> p;
   // vector<pair<int, int>> all;
    PAS() {}
    PAS(string t) {
        for (auto c : t) {
            s += c;
            s += '#';
            len += 2;
        }
        s = " " + s;
        p.resize(len + 1);
        getp(s);
    }
    vector<int> getp(string t) {
        int mid = 0, r = 0;
        for (int i = 1; i <= len; i++) {
            if (i > r)
                p[i] = 1;
            else
                p[i] = min(p[2 * mid - i], r - i + 1);
            while (i - p[i] > 0 && i + p[i] <= len && t[i - p[i]] == t[i + p[i]]) {
                p[i] += 1;
                // int ql, qr;
                // if ((i - p[i] + 1) % 2 == 0)
                //     ql = (i - p[i] + 1) / 2;
                // else
                //     ql = (i - p[i] + 2) / 2;
                // if ((i + p[i] - 1) % 2 == 0)
                //     qr = (i + p[i] - 1) / 2;
                // else
                //     qr = (i + p[i] - 2) / 2;
                // all.emplace_back(ql, qr);
            }
            if (i + p[i] - 1 > r)
                mid = i, r = i + p[i] - 1;
        }
        return p;
    }
    int getmax() {
        int ans = 0;
        for (int i = 1; i <= len; i++) {
            ans = max(ans, p[i]);
        }
        return (ans - 1);
    }
};

复杂度分析:每次暴力匹配一定伴随着最右回文串右端点 R 的右移。因此复杂度为线性。

用法:

  1. 求每个回文中心的回文半径

  2. 求本质不同回文串：在 ManacherManacher 中，新的回文串一定出现在使得最右串右移的时候。因此本质不同回文串至多 $n $个，把所有更新最右回文串去重即得到本质不同回文串

下标映射关系：首先我们预处理过的字符串是1base的，所有有效字符都是偶数，那么对应原字符串下标就是$\left \lfloor \frac{i}{2} \right \rfloor $.

  • 对于无效字符串我们需要知道他右区间的第一个有效字符下标是$\left \lfloor \frac{i+1}{2} \right \rfloor ，左区间的第一个有效字符下标是，左区间的第一个有效字符下标是\left \lfloor \frac{i-1}{2} \right \rfloor $，这在前缀和差分统计回文串某些数量信息时有用

P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
void solve()
{
    string s;
    cin >> s;
    PAS pas(s);
    cout << pas.getmax() << endl;
}

Gym10198-Mediocre String Problem-2018南京ICPC现场赛 - Cwolf9 - 博客园 (cnblogs.com)

https://acm.hdu.edu.cn/showproblem.php?pid=6599

例题：

1.https://codeforces.com/problemset/problem/17/E题意：找出所有位置相交的回文串的对数。

Sol：考虑容斥，所有回文串的对数减去不相交的回文串对数。

  • 回文串的对数容易统计，我们只需要映射回原字符串下标后，每次计算长度就可以。
  • 对于不相交的字符串，我们考虑枚举分割点，也就是第一个回文串的结束的位置。
    • 我们想知道有多少回文串以这个位置作为右端点：我们差分维护，最后求一遍前缀和
    • 有多少个回文串的起左端点严格大于当前位置：同样也是差分维护，前缀和统计，严格大于的贡献用后缀和即可
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
void solve(){
        cin>>n;;
        string s;
        cin>>s;
        PAS pas(s);
        int len=pas.len;
        int res=0;
        vector<int>pre(n+2),suf(n+3);
        for(int i=1;i<=len;i++){
        	int rad=pas.p[i];
        	//右端点结束
        	int l=(i+1)/2,r=(i+rad-2)/2;
        	pre[l]++;pre[r+1]--;
        	//左端点开头
        	l=(i-rad+2)/2,r=i/2;
        	suf[l]++;suf[r+1]--;
        	res+=r-l+1;
        	res%=mod; //不能提前取模算贡献
        }
        
        for(int i=1;i<=n;i++){
        	pre[i]+=pre[i-1];pre[i]%=mod;
        	suf[i]+=suf[i-1];suf[i]%=mod;
        }
        suf[n+1]=0;
        for(int i=n;i>=1;i--){
        	suf[i]+=suf[i+1];
        	suf[i]%=mod;
        }
       // cerr<<res<<endl;
       //mod的不是质数，不能直接快速幂求逆元
  if(res&1){
  res=(res-1)/2%mod*(res%mod)%mod;
  }
  else {
  	res=res/2%mod*((res-1)%mod)%mod;
  }
      // res=res*(res-1)/2;
       int tmp=0;
        for(int i=1;i<=n-1;i++){
        	tmp+=pre[i]*suf[i+1]%mod;
        	tmp%=mod;
        }
        res=(res-tmp+mod)%mod;
        cout<<res<<endl;
}

很多细节：1.这里取mod是51123987，不是质数，不能简单的快速幂得到逆元。但是大数乘法要取模又必须处理，考虑x(x−1)/2x(x-1)/2的时候奇偶性分讨一下。

2.这里取模必须手动取三次，不然会爆longlong

1
res=(res-1)/2%mod*(res%mod)%mod;

3.后缀和要多开一个空间，但差分的时候修改了那个无效空间，所以要清0.

2.https://www.luogu.com.cn/problem/UVA11475题意：给定一个字符串，问至少在结尾添加几个字符后字符串变成回文串？

Sol：考虑最差情况原串反转拼接，所以在马拉车处理的串中，这个题目答案串的中心点也是在范围内的。我们枚举答案的中心点，显然如果不是回文后缀无法作为备选答案，在备选答案中找到前缀最短的即可，找到后反转输出

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
string s;
void solve()
{

    PAS pas(s);
    int ans = inf;
    n = pas.len;
    for (int i = 1; i <= n; i++)
    {
        if (i + pas.p[i] - 1 == n)
            ans = min(ans, (i - pas.p[i]) / 2);
    }
    string res = s;
    for (int i = ans; i >= 1; i--)
        res += s[i - 1];
    cout << res << endl;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // freopen("debug.txt", "w", stderr);
    //  int t=1;
    // cin>>t;
    while (cin >> s)
        solve();
    return 0;
}

3.https://acm.hdu.edu.cn/showproblem.php?pid=3948题意：给定字符串，求本质不同回文子串个数.

Sol：这是回文自动机的基本应用，这里用马拉车+字符串哈希求出。在马拉车右边界拓展的过程中，我们考虑记录左右端点，这是答案备选集，哈希提前预处理，每次存到set里即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    string s;
    cin >> s;
    PAS pas(s);
    Hash hs(s);
    s = " " + s;
    auto &v = pas.all;
    set<pii> st;
    for (auto [x, y] : v) {
        // cerr<<x<<" "<<y<<endl;
        st.insert(hs.getpre(x, y));
    }
    cnt++;
    cout << "Case #" << cnt << ": ";
    cout << st.size() << endl;
}