ACM►字符串►回文树

回文树模板

参考资料

一篇特别棒的博客

回文树

回文树又叫回文自动机，算是和 AC 自动机、后缀自动机、KMP 相似的算法。

首先有这样一个定理，一个字符串的不同的回文子串的数量和字符串的长度是同阶的。

回文树上的每一个节点储存的是一个原字符串的回文子串，并且他像 AC 自动机一样有 fail 指针和转移边，一个节点的父亲表示的回文串是当前节点表示的回文串的子串。fail 指针指向的是当前节点表示的回文串的最长回文子串，并且这个回文子串同时是他的前缀和后缀，并且不是他本身。

BZOJ 3676

题目链接

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。

数据满足1≤字符串长度≤300000。

代码

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
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 512345;
const int ALP = 26;
 
struct Palindromic_Tree {
    int son[MAX][ALP]; //转移边
    int fail[MAX]; //fail 指针
    int cnt[MAX]; //当前节点表示的回文串在原串中出现了多少次
    int num[MAX]; //当前节点 fail 可以向前跳多少次
    int len[MAX]; //当前节点表示的回文串的长度
    int S[MAX]; //插入的字符串
    int last; //最后一次访问到的节点，类似 SAM
    int n; //插入的字符串长度
    int p; //自动机的总状态数
 
    int newnode(int l) {
        memset(son[p], 0, sizeof(son[p]));
        cnt[p] = 0;
        num[p] = 0;
        len[p] = l;
        return p++;
    }
 
    void init() {
        p = 0;
        newnode(0);
        newnode(-1);
        last = 0;
        n = 0;
        S[n] = -1;
        fail[0] = 1;
    }
 
    int get_fail(int x) {
        while (S[n - len[x] - 1] != S[n]) x = fail[x];
        return x;
    }
 
    void add(int c) {
        c -= 'a';
        S[++n] = c;
        int cur = get_fail(last); //通过上一次访问的位置去扩展
        if (!son[cur][c]) { //如果没有对应的节点添加一个新节点
            int now = newnode(len[cur] + 2);
            fail[now] = son[get_fail(fail[cur])][c]; //通过当前节点的 fail 去扩展出新的 fail
            son[cur][c] = now;
            num[now] = num[fail[now]] + 1; //记录 fail 跳多少次
        }
        last = son[cur][c];
        cnt[last]++; //表示当前节点访问了一次
    }
    void count() {
        //如果某个节点出现一次，那么他的 fail 也一定会出现一次，并且在插入的时候没有计数
        for (int i = p - 1; i >= 0; i--) cnt[fail[i]] += cnt[i];
    }
} AUT;
 
char data[MAX];
int n;
 
int main() {
    scanf("%s", data);
    n = strlen(data);
    AUT.init();
    for (int i = 0; i < n; i++) AUT.add(data[i]);
    AUT.count();
    long long ans = 0;
    for (int i = 0; i < AUT.p; i++) {
        ans = max(ans, 1ll * AUT.len[i] * AUT.cnt[i]);
    }
    printf("%lld\n", ans);
}

​