回文树/回文自动机学习笔记

我学习的博客:Palindromic Tree——回文树【处理一类回文串问题的强力工具】| poursoul 的博客

其他参考:【普及向】回文树 | VictorWonder的博客

回文树/回文自动机简介

回文树就是回文自动机,以下皆以「回文树」称呼。

假设我们有一个字符串 $S$ ,$S$ 下标从 $0$ 开始,则回文树能做到如下几点:

  • 求 $S$ 前缀 $0 \sim i$ 内本质不同的回文串的个数
  • 求 $S$ 内每一个本质不同回文串出现的次数
  • 求 $S$ 内回文串的个数
  • 求以下标 $i$ 结尾的回文串的个数

数据结构的介绍与实现

节点

回文树有两个根节点,除这两个根节点以外的节点均表示一个本质不同于其他的回文子串。

每个节点有字符集大小多的子节点,表示在当前回文子串的两端加上某一字符形成的回文子串。

两个根节点的子节点为长度分别是偶数、奇数的回文子串,为方便计算,定义偶树根节点所代表的回文串的长度为 $0$ ,奇数根节点所代表的回文串的长度为 $-1$ (这样,根节点也算是表示了回文子串了。。。)。

每个节点保存其表示的回文子串的长度 $len$ 、出现次数 $cnt$ (在调用 count() 方法之后才是,至于 count() 方法,一会儿再说)、回文后缀数 $num$ ,同时有一个 $fail$ 指针指向其最大的回文后缀。

偶数根节点的 $fail$ 指针指向奇数根节点,奇数根节点的 $fail$ 指针就是自己(或说没有,因为用不上。。。)。

1
2
3
4
5
6
7
struct Node {
Node *ch[CHAR_SET], *fail;
int len, cnt, num;
Node(int len = 0) : len(len), cnt(0), num(0) {
for (int i = 0; i < CHAR_SET; i++) ch[i] = NULL;
}
};

特殊节点

两个根节点在刚刚说了。。。

$last$ 节点:表示目前回文树已插入的所有字符组成的字符串的最大回文后缀(其实就是新插入的节点)。

插入与建树

依次插入每个字符就可完成建树。

插入时,先看当前的 $last$ 节点,若它代表的回文子串的左边的字符与插入字符相同,则插入节点为 $last$ 节点的字节点;否则一路沿 $fail$ 指针走下去,直至满足条件。记要插入节点的父节点(也就是找到的节点)为 $o$ 。

实现时,用 str[size - u->len - 1] 表示正在插入第 $size$ 个节点、节点 $u$ 所代表的回文子串的左边的字符。由于奇数根节点的长度为 $-1$ ,所以一定会走到一个节点使其满足条件。

如果发现节点 $o$ 已有该字符对应的子节点,则说明已经存在与其本质相同的回文子串,只需为其的 $cnt$ 变量加一即可。否则,建立新节点,其长度为父节点加 $2$ (再一次表明了奇数根节点的长度设为 $-1$ 的方便),同时从 $o.fail$ 开始沿 $fail$ 指针走下去,找到新节点的 $fail$ 指针指向的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Node *extend(int c) {
s[++size] = c;
for (; s[size - last->len - 1] != s[size]; last = last->fail) {}

Node *v = last;
Node *u = v->c[c];
if (!u) {
u = new (_curr++) Node(last->len + 2);
for (last = last->fail; s[size - last->len - 1] != s[size]; last = last->fail) {}
u->fail = last == odd && !odd->c[c] ? even : last->c[c];
v->c[c] = u;
}
u->cnt++;

return last = u;
}

void build(char *s) {
int n = strlen(s);
for (int i = 0; i < n; i++) insert(s[i] - BASE_CHAR);
}

count() 方法

来说说之前提过的 count() 方法,在外部使用回文树中节点的 $cnt$ 元素之前,必须先调用它。

当然,方法内容很简单,就是把所有节点的 $cnt$ 变量加给其 $fail$ 指针指向的节点。

注意要倒序,也就是从底向上进行。

1
2
3
void count() {
for (Node *p = _curr - 1; p >= _pool; p--) p->fail->cnt += p->cnt;
}

模版题

求最大的 $u.len \times u.cnt$ :BZOJ 3676题解