回文自动机PAM

算法原理就是增量法构建 PAM，利用前面的回文后缀，fail指针配合转移边进行维护。

算法核心流程：

  • 1.加入新节点的时候找到以这个点的结尾的最长回文后缀，需要跑last,last—>fail,last—>fail->fail,直到有转移边或者有奇根。目的是找到新建节点的父亲。
  • 为新建节点找到不平凡的最长回文回文后缀(也就是不包含自身)。这一步骤爬上一步(找到的父亲)(的fail链)（不包含父亲）
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
struct PAM {
    static constexpr int asz = 28;
    struct Node {
        int len;
        int fail;
        int dep;      // 以这个节点结尾的回文子串的数量(回文fail树的深度)
        int cnt = 0;  // 同样的回文结构出现次数
        array<int, asz> next;
        // int mask = 0;用了多少种字母
        Node() : len{}, fail{}, dep{}, next{} {}
    };
    vector<Node> t;
    vector<int> idpos;  // idpos表示字符串字符位置到后缀自动机节点编号
    int last;
    string s;
    PAM() {
        init();
    }
    void init() {
        t.assign(2, Node());
        t[0].len = -1;  // 0：奇根
        last = 1;       // 1：偶根
        s.clear();
        idpos.assign(1, 0);
    }
    int newNode() {
        t.emplace_back();  // Node()
        return t.size() - 1;
    }

    bool add(char c, char offset = 'a') {
        int pos = s.size();
        s += c;
        int ch = c - offset;
        int cur = last, curlen = 0;

        while (true) {
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
                break;
            cur = t[cur].fail;
        }  // 找到在哪个节点后面建新点
        if (t[cur].next[ch]) {
            last = t[cur].next[ch];
            idpos.push_back(last);
            t[last].cnt += 1;
            return false;
        }

        int num = newNode();
        last = num;
        idpos.push_back(last);
        t[num].len = t[cur].len + 2;
        // 在这里加入题目需要维护的值
        // t[num].mask = t[cur].mask;
        // t[num].mask |= 1 << ch;
        t[cur].next[ch] = num;

        if (t[num].len == 1) {  // 如果为单字符，指向偶根
            t[num].fail = 1;
            t[num].dep = 1;
            t[num].cnt = 1;
            return true;
        }

        while (true) {  // 为新节点找fail，从父亲的fail开始找
            cur = t[cur].fail;
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                t[num].fail = t[cur].next[ch];
                break;
            }
        }
        t[num].cnt = 1;
        t[num].dep = 1 + t[t[num].fail].dep;

        return true;
    }
    int tot = 0;
    void work(string tt) {
        for (auto x : tt) add(x);
        tot = t.size() - 1;
        for (int i = tot; i >= 2; i--) {
            int fa = t[i].fail;
            t[fa].cnt += t[i].cnt;
        }
    }
    int fail(int p) {
        return t[p].fail;
    }
    int len(int p) {
        return t[p].len;
    }
    int size() {
        return t.size();
    }
    int cnt(int p) {
        return t[p].cnt;
    }
};

【模板】回文自动机（PAM）https://www.luogu.com.cn/problem/P5496P5496 输出以第 i 个字符结尾的回文子串个数,强制在线

Sol:建出回文自动机，考虑维护深度就是以当前节点结尾的回文后缀个数，只在新节点的时候需要维护。dp考虑即可dp[u]=dp[fail[u]]+1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PAM pam;
void solve() {
    string s;
    cin >> s;
    int last = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (i == 0)
            pam.add(s[i]);
        else {
            char c = (s[i] - 97 + last) % 26 + 97;
            pam.add(c);
        }
        last = pam.t[pam.idpos[i + 1]].dep;
        cout << last <<" ";
    }
}

[APIO2014] 回文串https://www.luogu.com.cn/problem/P3649

我们定义 ss 的一个子串的价值为这个子串在 ss 中出现的次数乘以这个子串的长度。求所有回文子串中的最大价值。

Sol：维护cnt表示出现次数，每次作为结尾节点的时候+1.最后出现次数就是fail树内的tot全加起来，为了减少常数不去建fail树然后dfs。考虑直接按编号逆序拓扑更新求和。

1
2
3
4
5
6
7
8
9
10
PAM pam;
void solve() {
    string s;
    cin >> s;
    pam.work(s);
    ll ans = 0;
    int tot = pam.size() - 1;
    for (int i = 2; i <= tot; i++) ans = max(ans, (ll)pam.len(i) * pam.t[i].cnt);
    cout << ans << endl;
}

P4287 [SHOI2011] 双倍回文

记字符串 ww 的倒置为 wRw^{\mathsf R}。例如(abcd)R=dcba\tt (abcd)^{\mathsf R}=dcba，(abba)R=abba\tt (abba)^{\mathsf R}=abba。

如果 xx 能够写成 wwRwwRww^{\mathsf R} ww^{\mathsf R} 形式，则称它是一个“双倍回文”。换句话说，若要 xx 是双倍回文，它的长度必须是 44 的倍数，而且 xx，xx 的前半部分，xx 的后半部分都要是回文。例如 abbaabba\tt abbaabba 是一个双倍回文，而 abaaba\tt abaaba 不是，因为它的长度不是 44 的倍数。

对于给定的字符串，计算它的最长双倍回文子串的长度。

Sol:所有解法都基于一个事实就是：双倍回文存在一个长度为len/2的回文后缀。-

  • 或者说显然的观察是len/2是双倍回文的border，又由于回文串的border一定是回文后缀，所以结论正确。

  • 解法1：从border角度考虑：我们记录每次传进来的字符的位置，然后选判长度整除4，再用提前处理好的字符串哈希判前一半=后一半前一半=后一半

    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
    int ans = 0;
    Hash hs;
    int res = 0;
    struct PAM {
        static constexpr int asz = 28;
        struct Node {
            int len;
            int fail;
            int cnt;      // 以这个节点结尾的回文子串的数量
            int tot = 0;  // 同样的回文结构出现次数
            array<int, asz> next;
            Node() : len{}, fail{}, cnt{}, next{} {}
        };
        vector<Node> t;
        int last;

        string s;
        PAM() {
            init();
        }
        void init() {
            t.assign(2, Node());
            t[0].len = -1;  // 0：奇根
            last = 1;       // 1：偶根
            s.clear();
        }
        int newNode() {
            t.emplace_back();  // Node()
            return t.size() - 1;
        }

        bool add(int tmppos, char c, char offset = 'a') {
            int pos = s.size();
            s += c;
            int ch = c - offset;
            int cur = last, curlen = 0;

            while (true) {
                curlen = t[cur].len;
                if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
                    break;
                cur = t[cur].fail;
            }  // 找到在哪个节点后面建新点
            if (t[cur].next[ch]) {
                last = t[cur].next[ch];
                t[last].tot += 1;
                return false;
            }

            int num = newNode();
            last = num;
            t[num].len = t[cur].len + 2;
            t[cur].next[ch] = num;

            if (t[num].len == 1) {  // 如果为单字符，指向偶根
                t[num].fail = 1;
                t[num].cnt = 1;
                t[num].tot = 1;
                return true;
            }

            while (true) {  // 为新节点找fail，从父亲的fail开始找
                cur = t[cur].fail;
                curlen = t[cur].len;
                if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                    t[num].fail = t[cur].next[ch];
                    break;
                }
            }
            t[num].tot = 1;
            t[num].cnt = 1 + t[t[num].fail].cnt;
            if (t[num].len % 4 == 0) {
                int tmplen = t[num].len / 2;
                int l1 = tmppos - t[num].len + 1;
                int l2 = l1 + tmplen;
                if (hs.getpre(l1, l1 + tmplen - 1) == hs.getpre(l2, l2 + tmplen - 1)) {
                    res = max(res, t[num].len);
                }
            }
            return true;
        }
    };

    PAM pam;

    void solve() {
        cin >> n;
        string s;
        cin >> s;
        hs.init(s);
        for (int i = 0; i < n; i++) pam.add(i + 1, s[i]);
        cout << res << endl;
    }

  • 解法2：从PAM树角度考虑：我们需要爬fail链去查询是否存在一个祖先节点的长度是当前节点的一半。我们建出fail树，dfs一遍同时维护当前哪些节点是祖先，存的是他们的长度。

    细节：从偶根（1）开始dfs。

    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
    PAM pam;
    void solve() {
        cin >> n;
        string s;
        cin >> s;
        for (auto x : s) pam.add(x);
        auto t = pam.t;
        int tot = t.size() - 1;

        vector<vector<int>> e(tot + 3);
        for (int i = 2; i <= tot; i++) e[t[i].fail].push_back(i);
        vector<bool> st(n + 1);
        int ans = 0;
        auto dfs = [&](auto self, int u) -> void {
            int lenu = t[u].len;
            if (lenu % 4 == 0 && st[lenu / 2]) {
                ans = max(ans, lenu);
            }
            st[lenu] = 1;
            for (auto v : e[u]) {
                self(self, v);
            }
            st[lenu] = 0;
        };
        dfs(dfs, 1);
        cout << ans << endl;
    }

  • 提供一种接近本质的做法：直接增加一个trans指针，维护fail的时候也维护它。trans 指针的含义是小于等于当前节点长度一半的最长回文后缀，求法和 fail指针的求法类似。来源：https://www.luogu.com.cn/article/gx0icv96

由于回文自动机可能会被卡空间，开成全局变量了

https://qoj.ac/contest/1440/problem/7876给出字符串，定义价值为$出现次数\times 出现次数\times长度$，求所有回文区间串的价值总和。区间串的定义如下：

  • i≤js[i..j]i\le j \quad s[i..j]
  • i>js[i..n]+s[1..j]i>j \quad s[i..n] + s[1..j]

Sol:首先考虑只有len≤nlen \le n的回文子串才能贡献。再考虑我们需要处理循环位移，不难想到倍长原串，所以会出现重复计算次数的情况，怎么处理？考虑重复的情况一定会在结尾0-n的时候遇到，所以我们对于0−n0-n的时候对原串和倍长串都统计次数，两者之差就减去了单独这个串的影响。n−2n−1n-2n-1这段不会出现重复，但需要注意控制长度在1−n1-n内就可以了。

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
PAM pam1;
PAM pam2;
void solve() {
    ll ans = 0;
    string s;
    cin >> n >> s;
    pam1.work(s);
    pam2.work(s + s);
    auto &t1 = pam1.t, t2 = pam2.t;
    vector<bool> mp(pam2.tot + 5, 0);
    for (int i = 0; i < n; i++) {
        int u1 = pam1.idpos[i], u2 = pam2.idpos[i];
        if (mp[u2])
            continue;
        mp[u2] = true;
        int cnt = t2[u2].cnt - t1[u1].cnt;
        ans += (((ll)cnt * cnt % mod) * (ll)t2[u2].len) ;
        ans %= mod;
    }
    for (int i = n; i < 2 * n; i++) {
        int u = pam2.idpos[i];
        if (mp[u])
            continue;
        mp[u] = true;
        if (t2[u].len > n)
            continue;
        int cnt = t2[u].cnt;
        ans += (((ll)cnt * cnt % mod) * (ll)t2[u].len);
        ans %= mod;
    }
    cout << ans << endl;
}

给出一个字符串S，定义一个字符串的价值为：出现字母的种类数。
求S 所有回文子串的价值之和。

Sol：本题除了求每个本质不同子串的出现次数外，还需要求每个本质不同子
串出现的字母种类数。
可以在PAM 的每个节点额外维护一个mask，表示这个点代表的回文串
用到了哪些字母，在新建节点的时候顺便维护即可

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
 struct Node {
        int len;
        int fail;
        int dep;      // 以这个节点结尾的回文子串的数量(回文fail树的深度)
        int cnt = 0;  // 同样的回文结构出现次数
        array<int, asz> next;
        int mask = 0;
        Node() : len{}, fail{}, dep{}, next{} {}
    };
     bool add(char c, char offset = 'a') {
        int pos = s.size();
        s += c;
        int ch = c - offset;
        int cur = last, curlen = 0;

        while (true) {
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
                break;
            cur = t[cur].fail;
        }  // 找到在哪个节点后面建新点
        if (t[cur].next[ch]) {
            last = t[cur].next[ch];
            idpos.push_back(last);
            t[last].cnt += 1;
            return false;
        }

        int num = newNode();
        last = num;
        idpos.push_back(last);
        t[num].len = t[cur].len + 2;
        // 在这里加入题目需要维护的值
        t[num].mask = t[cur].mask;
        t[num].mask |= 1 << ch;
        t[cur].next[ch] = num;

        if (t[num].len == 1) {  // 如果为单字符，指向偶根
            t[num].fail = 1;
            t[num].dep = 1;
            t[num].cnt = 1;
            return true;
        }

        while (true) {  // 为新节点找fail，从父亲的fail开始找
            cur = t[cur].fail;
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                t[num].fail = t[cur].next[ch];
                break;
            }
        }
        t[num].cnt = 1;
        t[num].dep = 1 + t[t[num].fail].dep;

        return true;
    }
    void solve() {
    ll ans = 0;
    string s;
    cin >> s;
    PAM pam;
    pam.work(s);
    int tot = pam.size() - 1;
    for (int i = 2; i <= tot; i++) ans += pam.cnt(i) * __builtin_popcount(pam.t[i].mask);
    cout << ans << endl;
}

给出一个字符串S，|S| ≤ 1000, 000。求前K 大的奇回文子串奇数长度乘积。
K ≤ 1000, 000, 000

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
void solve() {
    ll n, k;cin >> n >> k;
    string s;cin >> s;
    PAM pam;pam.work(s);
    vector<int> a(n + 1);
    int tot = pam.size() - 1;
    ll ans = 1;
    for (int i = 2; i <= tot; i++) {
        a[pam.len(i)] += pam.cnt(i);
    }
    // 注意读题:不要偶数回文
    for (int i = n; i >= 1; i--) {
        if (i % 2 == 0)continue;
        if (k - a[i] >= 0) {
            ans = (ans * qmi(i, a[i])) % mod;
            k -= a[i];
        } else {
            ans = (ans * qmi(i, k)) % mod;
            k = 0;
            break;
        }
    }
    if (k)
        cout << -1;
    else
        cout << ans << endl;
}

给出一个字符串S，求最长的双回文子串。
回文双子串T 定义为：可以从一个位置切开，使得前缀和后缀都是回文
串。
|S| ≤ 100, 000.

Sol:可以枚举拼接点pos，然后分别最大化以pos为左端点pos+1为右端点的回文串长度。问题转化为求某个点最长回文前缀后缀，开两个回文自动机，对正串反串跑一遍即可。枚举拼接点，更新答案pam1.len(idpos(i))+pam2.len(idpos(n+1−i))pam1.len(idpos(i))+pam2.len(idpos(n+1-i)).注意反串的坐标映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    PAM pam;
    string s;
    cin >> s;
    string rs = s;
    reverse(alls(rs));
    PAM par;
    pam.work(s);
    par.work(rs);
    int n = s.size();
    int ans = 0;
    for (int i = 1; i <= n - 1; i++) {
        int pre = par.idpos[n + 1 - (i + 1)], suf = pam.idpos[i];
        ans = max(ans, pam.len(suf) + par.len(pre));
    }
    cout << ans << endl;
}

给出一个01 串S，求最长的反对称子串。
反对称串T 定义为：将R(T) 逐位取反之后等于原串T，则T 是一个反
对称串，例如010101。
|S| ≤ 500, 000

Sol:考虑在新的相等运算意义下进行Manacher 即可。注意到奇数长度一定非法，因为中间字符没办法相等。统计答案的时候只统计偶数长度的，再考虑初始化的时候，单个字符构成的半径显然是0，因为它本身不能构成反对称串。

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
bool defeq(char c, char d) {
    if (c == '#' && d == '#')
        return true;
    int cc = c - '0', dd = d - '0';
    if (cc == 0 && dd == 1)
        return true;
    if (cc == 1 && dd == 0)
        return true;
    return false;
}
struct PAS {
    string s = "#";
    int len = 1;
    vector<int> p;
    // vector<pair<int, int>> all;
    PAS(string t) {
        for (auto c : t) {
            s += c;
            s += '#';
            len += 2;
        }
        s = " " + s;
        p.resize(len + 1);
        deb(s);
        getp(s);
    }
    vector<int> getp(string t) {
        int mid = 0, r = 0;
        for (int i = 1; i <= len; i++) {
            if (i > r) {
                p[i] = 0;
            } else
                p[i] = min(p[2 * mid - i], r - i + 1);
            while (i - p[i] > 0 && i + p[i] <= len && defeq(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);
            }
            // deb(i,s[i],p[i]);
            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);
    }
};
void solve() {
    ll ans = 0;
    int n;
    string s;
    cin >> n >> s;
    PAS pas(s);
    deb(pas.p);
    for (int i = 1; i <= pas.len; i++) {
        if (i % 2)
            ans += pas.p[i] / 2;
    }
    cout << ans << endl;
}

https://www.luogu.com.cn/problem/P4656

[CEOI2017] Palindromic Partitions

题目描述

给出一个只包含小写字母字符串，要求你将它划分成尽可能多的小块，使得这些小块构成回文串。

例如：对于字符串 abcab，将他分成 ab c ab 或者 abcab 就是构成回文串的划分方法，abc ab 则不是。abcab把ab看做一个整体元素，ab=x.则xcx是回文串。考虑最坏情况整个串看作一个整体，再贪心考虑每次从当前指针指向前后缀找最短非零的border，可以用字符串哈希实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
    string s;
    cin >> s;
    Hash hs1(s);
    int n = s.size();
    int ql = 1, qr = n;
    int len = 0, cnt = 0;
    deb(s);

    deb(hs1.getpre(1, 2));
    while (ql + len < qr - len) {
        deb(ql, qr, len);
        if (hs1.getpre(ql, ql + len) == hs1.getpre(qr - len, qr)) {
            ql += len + 1;
            qr -= len + 1;
            len = 0;
            cnt += 2;
        } else {
            len++;
        }
    }
    if(len||ql==qr)cnt+=1;
    cout << cnt << endl;
}

https://ac.nowcoder.com/acm/problem/13230

【每日一题】3月26日题目精讲 区间dp、最长回文子序列_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder.com)