可持久化 Trie

trie

  • root[]\text{root}[\cdots] 数组来定位每个根节点,不妨设trie\text{trie} 中字符集合为CC,全体字符集为AA
    当前插入第ii 个字符串,即执行第ii 个版本,proot(i1)p \leftarrow \text{root}(i-1)
  • 新建一个节点qq,即q=root(i)=++totq = root(i) = ++tot,假设当前插入字符SjS_j
  • 如果p0p \neq 0,对于c{C}, cSj\forall c \in \{C\}, \ c \neq S_j,令t(q,c)t(p,c)t(q, c) \leftarrow t(p, c)
    (这一步可以检查c{A}\forall c \in \{A\} 全体字符集,令t(q,c)t(p,c)t(q, c) \leftarrow t(p, c),因为下一步t(q,Sj)t(q, S_j) 会重新定位到新开的节点上)
  • 新建一个节点,令t(q,Sj)=++tott(q, S_j) = ++tot,即除了SjS_j 指针不同外,p,qp, q 的其余信息完全相同
  • pt(p,Sj),qt(q,Sj),jj+1p \leftarrow t(p, S_j), q \leftarrow t(q, S_j), j \leftarrow j+1 直到字符串结尾

最大异或和
可以类似引入一个异或前缀和的概念

i=pnap=SnSp1\bigoplus_{i = p}^{n} a_p = S_n \oplus S_{p-1}

  • 对于添加操作,很简单Sn+1=Snx, n=n+1S_{n+1} = S_n \oplus x, \ n = n+1
  • 如果令p=p1, l1pr1p' = p-1, \ l-1 \leqslant p' \leqslant r-1,询问操作实际上就是令val=xSnval = x \oplus S_n
    求一个位置pp,满足l1pr1l-1 \leqslant p \leqslant r-1,使得SpvalS_p \oplus val 最大
    这个问题如果没有p[l1,r1]p \in [l-1, r-1] 的限制,就是最大异或和问题
  • 对于pr1p \leqslant r-1,可以借鉴主席树思想,对trie\text{trie} 进行可持久化,在第r1r-1 个版本
    root(r1)\text{root}(r-1)查询最大异或和路径
    p=root(r1)p = \text{root}(r-1),从高位到低位尽可能沿着和valval 相反的位走)
  • 对于pl1p \geqslant l-1,只要保证异或和路径上所经过点的时间戳l1\geqslant l-1 即可
    对于插入操作insert(pre,p,i)\text{insert}(pre, p, i) 表示插入第ii 个字符串
    kk 从高位到低位遍历,此时第kk 位的字符为c=Sik & 1c = S_i \gg k \ \& \ 1
    • 如果pre0pre \neq 0,令t(p,c1)t(pre,c1)t(p, c\oplus 1) \leftarrow t(pre, c\oplus 1)
    • t(p,c)=++tott(p, c) = ++tot于此同时标记节点时间戳dfn(p)=idfn(p) = i,然后和主席树一样同步往下走
      pt(p,c), pret(pre,c),then dfn(p)=ip \leftarrow t(p, c), \ pre \leftarrow t(pre, c), \textbf{then} \ dfn(p) = i
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
const int N = 600000 + 5;
const int maxn = N * 25;
int n, m, s[N], root[N];

class Trie {
public:
int t[maxn][2], dfn[maxn];
int tot;

Trie() {
tot = 0;
memset(t, 0, sizeof 0);
memset(dfn, 0, sizeof 0);
dfn[0] = -1;
}

void insert(int pre, int p, int ver) {
dfn[p] = ver;
for (int k = 25; k >= 0; k--) {
int c = s[ver] >> k & 1;
t[p][c^1] = t[pre][c^1];
t[p][c] = ++tot;
p = t[p][c], pre = t[pre][c];
dfn[p] = ver;
}
}

int ask(int p, int val, int lim) {
for (int k = 25; k >= 0; k--) {
int c = val >> k & 1;
if (dfn[ t[p][c^1] ] >= lim) p = t[p][c^1];
else p = t[p][c];
}
return s[dfn[p]] ^ val;
}
} trie;

int main() {
freopen("input.txt", "r", stdin);
cin >> n >> m;

// init
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
s[i] = s[i-1] ^ x;
root[i] = ++trie.tot;
trie.insert(root[i-1], root[i], i);
}
while (m--) {
char cmd[2];
scanf("%s", cmd);
if (cmd[0] == 'A') {
int x;
scanf("%d", &x);
root[++n] = ++trie.tot;
s[n] = s[n-1] ^ x;
trie.insert(root[n-1], root[n], n);
}
else {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
int res = trie.ask(root[r-1], s[n]^x, l-1);
printf("%d\n", res);
}
}
}

树上可持久化 Trie

树上异或

利用可持久化线段树的思路,可以设计出如下算法

  • dfs(u)\textbf{dfs}(u) 对于(u,v)(u, v),将vv 看作一个基于uu 的新的版本,建立可持久化trie\text{trie}
    root(v)=++tot,insert(root(u),root(v))\text{root}(v) = ++tot, \quad \text{insert}(root(u), root(v))
    注意保存版本信息,ver(v)=ver(u)+1\text{ver}(v) = \text{ver}(u) + 1
  • 查询操作呢?对于ask(x,y,val)\text{ask}(x, y, val)
    不妨令d=LCA(x,y), fafa(lca(x,y))d = \text{LCA}(x, y), \ fa \leftarrow fa(\text{lca}(x, y))
    此时分别查询root(x)\text{root}(x)root(y)\text{root}(y),然后取一个max\max 即可
    但是这里是有限制的,在对可持久化trie\text{trie} 查询的时候,必须保证x,yx, y fafa 的子节点
    这不难,只要让p=root(fa),q=root(x)p = root(fa), q = root(x) 同步往下走,保证qq 经过的点的版本号ver(q)>ver(p)\text{ver}(q) > \text{ver}(p)
  • 具体来说,以root(x)root(x) 为例,调用ask(p,q,val)=ask(root(fa),root(x),val)\text{ask}(p, q, val) = \text{ask}(root(fa), root(x), val)
    从高位到低位检查valval 的位,假设此时第kk 位是ccp,qp, q 尽可能沿着c1c \oplus 1 的指针往下走
    pt(p,c1),qt(q,c1),res=res+(1k)p \leftarrow t(p, c \oplus 1), q \leftarrow t(q, c \oplus 1), res = res + (1 \ll k)
    如果没有c1c \oplus 1 的指针,那么只好沿着cc 指针走,这和最大异或和解决方法大同小异
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
const int N = 1e5 + 5;
const int maxn = N * 32, H = 17;
int a[N], root[N], n, m;

class Graph {
public:
int n;
int tot;
vector<int> head, ver, ne;

Graph(int _n) : n(_n) {
tot = 1;
head.resize(n), ver.resize(n<<1), ne.resize(n<<1);
}
void clear() {
tot = 1;
fill(head.begin(), head.end(), 0);
}

void add(int a, int b) {
ver[++tot] = b; ne[tot] = head[a]; head[a] = tot;
}
} G(N);

class Trie {
public:
int tot;
int t[maxn][2], ver[maxn];

Trie() {
tot = 0;
memset(t, 0, sizeof t);
memset(ver, 0, sizeof ver);
}
void clear() {
tot = 0;
memset(t, 0, sizeof t);
memset(ver, 0, sizeof ver);
}

void insert(int p, int q, int val) {
ver[q] = ver[p] + 1;
for (int k = 16; k >= 0; k--) {
int c = val >> k & 1;
t[q][c^1] = t[p][c^1];
t[q][c] = ++tot;

p = t[p][c], q = t[q][c];
ver[q] = ver[p] + 1;
}
}

int query(int fa, int p, int val) {
int res = 0;
for (int k = 16; k >= 0; k--) {
int c = val >> k & 1;
if (ver[ t[fa][c^1] ] < ver[ t[p][c^1] ]) {
res += (1<<k); fa = t[fa][c^1], p = t[p][c^1];
}
else fa = t[fa][c], p = t[p][c];
}
return res;
}

} trie;

int fa[N][H], dep[N];

void dfs(int u, int pa) {
fa[u][0] = pa, dep[u] = dep[pa] + 1;
for (int i = 1; i < H; i++) fa[u][i] = fa[fa[u][i-1]][i-1];
root[u] = ++trie.tot, trie.insert(root[pa], root[u], a[u]);

for (int i = G.head[u]; i; i = G.ne[i]) {
int v = G.ver[i];
if (v == pa) continue;
dfs(v, u);
}
}

int lca(int x, int y) {
if (dep[y] < dep[x]) swap(x, y);
for (int i = H-1; i >= 0; i--) {
if (dep[ fa[y][i] ] >= dep[x]) y = fa[y][i];
}
if (y == x) return y;
for (int i = H-1; i >= 0; i--) {
if (fa[y][i] != fa[x][i]) y = fa[y][i], x = fa[x][i];
}
return fa[x][0];
}

int main() {
freopen("input.txt", "r", stdin);
while (~scanf("%d%d", &n, &m)) {
// init
trie.clear(), G.clear();
memset(root, 0, sizeof root);
memset(fa, 0, sizeof fa);
memset(dep, 0, sizeof dep);

for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n-1; i++) {
int u, v;
scanf("%d%d", &u, &v);
G.add(u, v), G.add(v, u);
}

// dfs
dfs(1, 0);

// query
while (m--) {
int x, y, val;
scanf("%d%d%d", &x, &y, &val);
int f = fa[lca(x, y)][0];
int res = max(trie.query(root[f], root[x], val), trie.query(root[f], root[y], val));
printf("%d\n", res);
}
}
}

树上可持久化 Trie 综合

异或粽子

考虑前缀和s[i]s[i],原问题等价于对于一个点pp,找到s[1p1]s[1\cdots p-1] 的一个点pp'
使得s[p]s[p]s[p'] \oplus s[p] 最大,可以考虑使用可持久化trie\text{trie}

对于可持久化trie\text{trie}root(p1)\text{root}(p-1) 这个版本中只有区间[1p1][1\cdots p-1] 的信息
利用主席树的思想,可以解决可持久化trie\text{trie}k-query\text{k-query} 问题

对于区间[1r][1\cdots r],要找到一个l[1r1]l \in [1\cdots r-1],使得slsrs_l \oplus s_r 为第kk
proot(r1), vals[r]p \leftarrow \text{root}(r-1), \ val \leftarrow s[r]从高位到低位检查valval 的第bbcc
如果size(t(p,c1))k\textbf{size}(t(p, c \oplus 1)) \geqslant k,那么res+=(1b), pt(p,c1)res += (1 \ll b), \ p \leftarrow t(p, c\oplus 1)
否则的话,kksize(t(p,c1))k' \leftarrow k - \textbf{size}(t(p, c\oplus 1))pt(p,c)p \leftarrow t(p, c),递归在t(p,c)t(p, c) 子树查找第kk'

需要注意的是边界,想要让r=1r = 1 时有意义,必须提前在trie\text{trie} 树中插入insert(root(0),0)\text{insert}(\text{root}(0), 0)
表示在root(0)\text{root}(0) 初始化插入一个每个位都是00 的数

具体来说

  • 对于HH 位的数valval,由于要统计size\text{size} 信息,所以递归地插入
    insert(pre,p,H,val)\textbf{insert}(pre, p, H, val),递归的边界是H<0,size(p)=size(pre)+1H < 0, \text{size}(p) = \text{size}(pre) + 1
    H=0H = 0 时插入最后一个字符cc,递归执行t(p,c)t(p, c) 之后,边界H=1H = -1
  • res(i,rk(i))res \leftarrow (i, rk(i)),表示在区间[1i1][1\cdots i-1] 中找到一个jj
    使得res=sjxires = s_j \oplus x_i 为第rk(i)rk(i) 大,很显然一开始rk(i)=1rk(i) = 1
  • 建立一个优先队列que\text{que},对于 r[1,n]\forall \ r \in [1, n]
    ask(root(r1),rk(r),s[r])\textbf{ask}(\text{root}(r-1), rk(r), s[r]) 的结果放入que\text{que}
  • 取出堆顶元素,此时堆中最大元素假设为(res,p)(res, p)
    表示此时l[1,p)\exist l \in [1, p),使得slsps_l \oplus s_p 为第11 大,其值为resres
    将其累加到答案中,删掉sls_l注意要接着找到[1,l1][l+1,p)[1, l-1] \cup [l+1, p) 中第11 大,将其放入堆中
    注意到[1,l1][l+1,p)[1, l-1] \cup [l+1, p) 中的第11 大,等价于[1,p)[1, p) 中的第22
    由此在编程实现上可以更简单一些,一开始令rk(i)=1rk(i) = 1,取出堆顶元素(res,p)(res, p) 之后
    执行查询resask(root(p),++rk(p),s[p])res' \leftarrow \textbf{ask}(\text{root}(p), ++rk(p), s[p]),再继续将resres' 放入堆中
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
typedef pair<ll, int> PII;
const int maxn = 500000 + 10, N = maxn * 35;
const int H = 33;
int n, k, rk[maxn], root[maxn];
ll s[maxn];
priority_queue<PII> heap;

// insert(pre, p, H, val)
// ask(root(p), rk, &ans)

class Trie {
public:
int tot;
int t[N][2], sz[N];

Trie() {
tot = 0;
memset(t, 0, sizeof t);
memset(sz, 0, sizeof sz);
}

void insert(int pre, int p, int H, ll val) {
if (H < 0) {
sz[p] = sz[pre] + 1;
return;
}
int c = val >> H & 1;
if (pre) t[p][c^1] = t[pre][c^1];
t[p][c] = ++tot;
insert(t[pre][c], t[p][c], H-1, val);
sz[p] = sz[t[p][c]] + sz[t[p][c^1]];
}

void ask(int p, int rk, int H, ll val, ll &res) {
if (H < 0) return;
int c = val >> H & 1;
if (sz[ t[p][c^1] ] >= rk) {
res = (res << 1 | 1);
ask(t[p][c^1], rk, H-1, val, res);
}
else {
res <<= 1;
ask(t[p][c], rk - sz[t[p][c^1]], H-1, val, res);
}
}
} trie;

void solve() {
for (int i = 1; i <= n; i++) {
ll res = 0;
trie.ask(root[i-1], rk[i], H, s[i], res);
heap.push({res, i});
}
ll ans = 0;
while (k--) {
auto x = heap.top(); heap.pop();
ans += x.first;
int r = x.second;
ll res = 0;
trie.ask(root[r-1], ++rk[r], H, s[r], res);
heap.push({res, r});
}
printf("%lld\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
// init
memset(root, 0, sizeof root);

scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
ll x;
scanf("%lld", &x);
s[i] = s[i-1] ^ x;
rk[i] = 1;
}

// per trie
root[0] = ++trie.tot;
trie.insert(0, root[0], H, 0);
for (int i = 1; i <= n; i++) {
root[i] = ++trie.tot;
trie.insert(root[i-1], root[i], H, s[i]);
}

// solve
solve();
}

AC 自动机

AC 自动机实际上是trie\text{trie} 树上的自动机,是基于kmp\text{kmp} 思想的
假设在kmp\text{kmp} 模式匹配中,模板有很多个,这个时候怎么办呢?
一个很直观的想法是把所有模式串插入trie\text{trie} 树中,再在trie\text{trie} 树中加上失配边
AC-01

AC 自动机字典树的构建

  1. 对于模式串s1,s2,sns_1, s_2, \cdots s_n,将它们全部插入trie\text{trie} 树中,此时构成的所有状态集合称为QQ
    实际上,QQ每个状态节点对应一个模式串的一个前缀
  2. 假设当前的状态节点为uufail(u)=v\textbf{fail}(u) = v,其中vQv \in Q,并且vvuu最长后缀
    换句话说,fail\textbf{fail} 指针检查所有模式串的任意前缀,找到能和当前串后缀匹配上
    并且要使得匹配上的部分最长

AC 自动机的 fail 指针
AC-02

fail 指针的构建
构建过程类似kmp\text{kmp} 算法,不过这里是用bfs\text{bfs} 来递推
不妨设上一个阶段的最后节点为pp(即bfs\text{bfs} 的队头节点), 当前正在添加字符cc,即t(p,c)=ut(p, c) = u
假设深度小于uu 的所有指针已经求出来了,那么fail(u)\textbf{fail}(u) 应该指向谁?
这里要关注q=fail(p)q = \textbf{fail}(p)

  • 如果t(fail(p),c)=t(q,c)nullt(\text{fail}(p), c) = t(q, c) \neq \textbf{null},那么加入字符cc
    相当于在ppfail(p)\textbf{fail}(p) 后面同时接上cc,只要令fail(u)=t(fail(p),c)\textbf{fail}(u) = t(\text{fail}(p), c) 即可
  • 如果t(fail(p),c)=t(q,c)=nullt(\text{fail}(p), c) = t(q, c) = \textbf{null},类似kmp\text{kmp} 算法,不断沿着失配边走
    直到走到一个存在t(q,c)nullt(q, c) \neq \text{null} 的转移
    qfail(p)q \leftarrow \text{fail}(p)while qnull and t(q,c)=null: q=fail(q)\quad \textbf{while} \ q \neq \text{null} \ \textbf{and} \ t(q, c) = \textbf{null}: \ q = \textbf{fail}(q)
    此时令fail(u)=t(q,c)\textbf{fail}(u) = t(q, c)
    (如果一直找不到,那么qq 最后就会走到根节点)
    (如果还是不存在t(0,c)t(0, c),那么t(0,c)=0t(0, c) = 0,还是指向根节点,并不影响答案)

失配优化
容易证明上述算法的正确性,对于t(S,c)t(S, c) 相当于在SS 后面添加一个字符cc 变成另一个状态SS'
注意到fail(S)\textbf{fail}(S) 恰好是SS 的一个后缀,所以上述过程相当于
同步在{S,fail(S)}\{S, \textbf{fail}(S)\} 后面添加字符cc,由此t(fail(S),c)t(\textbf{fail}(S), c) 仍然是SS' 的后缀

那如果t(fail(S),c)t(\textbf{fail}(S), c) 不存在呢?我们要反复沿着失配边走,直到t(fail(S),c)nullt(\textbf{fail}(S), c) \neq \textbf{null}
这就造成了额外时间开销,能不能一步到位呢?
AC-03

实际上

1
2
3
4
5
6
7
while (q.size()) {
auto u = q.front(), q.pop();
for (int i = 0; i < 26; i++) {
if (t[u][i]) { ... }
else t[u][i] = t[ fail[u] ][i];
}
}

last 优化
由于fail\textbf{fail} 指针不一定都指向表示单词的节点,举个例子
对于模式串{sher, his, hep}\{\text{sher, his, hep}\},那么很显然节点99 与节点22 都不是单词节点
那么输出具体方案的时候,我们就可以跳过这些节点

trie\text{trie} 树中,val(j)>0\textbf{val}(j) > 0 的节点我们认为是单词节点
这样就可以考虑增加一个指针last(i)\textbf{last}(i),表示从节点ii 处沿着失配指针往回走,
遇到的下一个单词节点的编号,也叫后缀链接

1
2
3
4
5
6
7
8
9
10
while (q.size()) {
auto u = q.front(), q.pop();
for (int i = 0; i < 26; i++) {
if (t[u][i]) { ... }
else t[u][i] = t[ fail[u] ][i];
}

// 增加 last 指针
last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
}

AC 自动机的实现

AC 自动机模版

模版串多但是短,文本串很长,正好适合用 AC 自动机,由于要统计模版串出现的次数,也就是模版串能够匹配上的次数
可以这样设计算法

  • M(Si)=idx\text{M}(S_i) = idx,将模版串SiS_i 映射为相应的字符串的编号idxidx,执行插入insert(Si,idx)\textbf{insert}(S_i, idx)
    这样就可以先在 AC 自动机中执行统计,如果pp单词节点,在trie\text{trie} 中令val(p)=idx\text{val}(p) = idx
    对于trie\text{trie} 中的节点pp如果是单词节点,其匹配上的次数记为cnt(val(p))\textbf{cnt}(\text{val}(p))
    然后离线处理所有模版串,i[1,n], resmax(res,cnt(i))\forall i \in [1, n], \ res \leftarrow \max (res, \textbf{cnt}(i))
    如果要输出具体的方案,同样可以离线处理,对所有的模版串i[1,n]\forall i \in [1, n]
    如果cnt(M[Si])=res\textbf{cnt}(M[S_i]) = res,那么就将SiS_i 输出

  • 值得注意的是,如果模版串有重复,插入trie\text{trie} 树时,后面的串会覆盖前一个
    解决方法很简单,以后出现的为准,只要每次插入到达单词结尾时,更新M(Si)=idxM(S_i) = idx 即可
    那么问题就只剩下如何统计cnt(val(p))\textbf{cnt}(\text{val}(p))

  • find(T)\textbf{find}(T) 在文本串TT 中寻找能够匹配的所有模版串
    i[1,len(T)]\forall i \in [1, \text{len}(T)]与此同时p=0p = 0 从根节点开始遍历 AC 自动机的trie\text{trie}
    cT[i], pt(p,c)c \leftarrow T[i], \ p \leftarrow t(p, c)
    如果trie\text{trie} 树中的节点pp 为单词节点,那么它表示的单词编号为val(p)\text{val}(p)

    • 如果val(p)0val(p) \neq 0pp 为单词节点,也就是说pp 表示的单词能匹配上文本串TT 的一个位置,cnt(val(p))++\textbf{cnt}(\text{val}(p))++
      另外,pp 的所有后缀链接也一定能匹配上TT,相应节点对应单词cnt\textbf{cnt} 也应该++++
      这里就需要用到之前的last\text{last} 数组,dfs(last(p))\textbf{dfs}(\text{last}(p)) 递归统计所有后缀链接
    • 如果val(p)=0val(p) = 0,但是last(p)0\text{last}(p) \neq 0,就说明存在一个后缀单词能够匹配上
      需要dfs(last(p))\textbf{dfs}(\text{last}(p)) 进行递归统计
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
101
102
103
104
105
const int maxn = 1e6 + 5;
const int N = (150 + 5) * 80;
map<string, int> M;
int n, cnt[N];
string text, P[N];

class AC {
public:
int t[N][27], fail[N], val[N], last[N];
int tot;
AC() {
memset(t, 0, sizeof t);
memset(fail, 0, sizeof fail);
memset(val, 0, sizeof val);
memset(last, 0, sizeof last);
tot = 0;
}
void clear() {
tot = 0;
memset(t, 0, sizeof t);
memset(fail, 0, sizeof fail);
memset(val, 0, sizeof val);
memset(last, 0, sizeof last);
}

void insert(const string &str, int idx) {
int p = 0;
for (auto x : str) {
int c = x-'a';
if (!t[p][c]) t[p][c] = ++tot;
p = t[p][c];
}
val[p] = idx;
}

void build() {
queue<int> que;
for (int i = 0; i < 26; i++) if (t[0][i]) {
que.push(t[0][i]);
}

while (que.size()) {
auto u = que.front(); que.pop();
for (int i = 0; i < 26; i++) {
if (t[u][i]) {
fail[ t[u][i] ] = t[ fail[u] ][i];
que.push(t[u][i]);
}
else t[u][i] = t[ fail[u] ][i];
}
last[u] = val[fail[u]] ? fail[u] : last[ fail[u] ];
}
}

void dfs(int p) {
if (p) {
cnt[val[p]]++;
dfs(last[p]);
}
}

void find(const string &str) {
int p = 0;
for (auto x : str) {
int c = x-'a';
p = t[p][c];
if (val[p]) dfs(p);
else if (last[p]) dfs(last[p]);
}
}
} ac;

void solve() {
int res = -1;
for (int i = 1; i <= n; i++) res = max(res, cnt[i]);
printf("%d\n", res);
for (int i = 1; i <= n; i++) if (cnt[M[P[i]]] == res) {
printf("%s\n", P[i].c_str());
}
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
// init
ac.clear();
M.clear();
memset(cnt, 0, sizeof cnt);

// get data
for (int i = 1; i <= n; i++) {
cin >> P[i];
M[P[i]] = i;
ac.insert(P[i], i);
}

// ac automata
cin >> text;
ac.build();
ac.find(text);

// solve
solve();
}
}

AC 自动机和全概率

substring

其实就是从 AC 自动机根节点p=0p = 0 处遍历,求全概率
AC 自动机节点uu 若为单词节点,则word(u)=1\text{word}(u) = 1
那么可以根据全概率公式设计出如下算法

f(u,L)f(u, L) 表示当前在 AC 自动机的uu 节点,还要走LL 步,此时满足条件的概率,可以用记忆化搜索
ans &f(u,L)ans \ \& \leftarrow f(u, L), for c\forall \ \textbf{for} \ c
if word(t(u,c))=0:ans+=prob(c)f(t(u,c),L1)\quad \text{if} \ \text{word}(t(u, c)) = 0: \quad ans += \text{prob}(c) \cdot f(t(u, c), L-1)

边界为L0,return 1L \leqslant 0, \quad \text{return} \ 1
所求的答案为f(0,L)f(0, L)

另外值得注意的是,构建 AC 自动机last\text{last} 优化处理的时候,令word(u)=word(fail(u))\text{word}(u) \mid = \text{word}(\text{fail}(u))

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
101
const int maxn = 400 + 5;
const int N = 100 + 5, SZ = 64;
string P[N];
int K, n, L;
double prob[SZ];

inline int get(const char ch) {
if (isupper(ch)) return ch-'A';
else if (islower(ch)) return 26 + ch-'a';
else return 52 + ch-'0';
}

class AC {
public:
int t[maxn][SZ], word[maxn], fail[maxn];
int tot = 0;
void clear() {
tot = 0;
memset(t, 0, sizeof t);
memset(word, 0, sizeof word);
memset(fail, 0, sizeof fail);
}

void insert(const string &str) {
int p = 0;
for (auto x : str) {
int c = get(x);
if (!t[p][c]) t[p][c] = ++tot;
p = t[p][c];
}
word[p] = 1;
}

void build() {
queue<int> que;
int p = 0;
for (int i = 0; i < SZ; i++) if (t[p][i]) {
que.push(t[p][i]);
}

while (que.size()) {
auto u = que.front(); que.pop();
for (int i = 0; i < SZ; i++) {
if (t[u][i]) {
fail[ t[u][i] ] = t[ fail[u] ][i], que.push(t[u][i]);
}
else t[u][i] = t[fail[u]][i];
}
word[u] |= word[fail[u]];
}
}
} ac;

double dp[maxn][N];
int vis[maxn][N];
double f(int u, int L) {
if (L <= 0) return 1.0;
if (vis[u][L]) return dp[u][L];
vis[u][L] = 1;

double &ans = dp[u][L];
ans = 0.0;
for (int i = 0; i < SZ; i++) {
if (!ac.word[ ac.t[u][i] ]) ans += prob[i] * f(ac.t[u][i], L-1);
}
return ans;
}

int main() {
freopen("input.txt", "r", stdin);
int T;
cin >> T;
int kase = 0;
while (T--) {
// init
printf("Case #%d: ", ++kase);
ac.clear();
memset(prob, 0, sizeof prob);
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);

cin >> K;
for (int i = 1; i <= K; i++) {
cin >> P[i];
ac.insert(P[i]);
}
cin >> n;
for (int i = 1; i <= n; i++) {
char ch;
cin >> ch;
scanf("%lf", &prob[get(ch)]);
// debug(prob[get(ch)]);
}
cin >> L;

// then solve
ac.build();
double res = f(0, L);
printf("%.6lf\n", res);
}
}

AC 自动机与二维匹配

二维哈希实现矩阵匹配

求矩阵哈希的时候,注意行和列要用不同的哈希值,根据前缀和思想

h(i,j)=h(i1,j)P1+h(i,j1)P2h(i1,j1)P1P2+a(i,j)h(i, j) = h(i-1, j) \cdot P_1 + h(i, j-1) \cdot P_2 - h(i-1, j-1) \cdot P_1 \cdot P_2 + a(i, j)

对于任意矩形(x1,y1,x2,y2)(x_1, y_1, x_2, y_2),可以根据前缀和求出哈希值

Hash(x1,y1,x2,y2)=h(x2,y2)h(x11,y2)P1x2x1+1h(x2,y11)P2y2y1+1+h(x11,y11)P1x2x1+1P2y2y1+1\begin{gathered} \text{Hash}(x_1, y_1, x_2, y_2) = h(x_2, y_2) - h(x_1-1, y_2) \cdot P_1^{x_2-x_1+1} - h(x_2, y_1 - 1) \cdot P_2^{y_2 - y_1 + 1} \\ + h(x_1-1, y_1 - 1) \cdot P_1^{x_2 - x_1 + 1} \cdot P_2^{y_2-y_1 + 1} \end{gathered}

Matrix Matcher

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
typedef unsigned long long ull;
const int P1 = 13331, P2 = 131;
int n1, m1, n2, m2;
const int maxn = 1000 + 10;
char s1[maxn][maxn], s2[maxn][maxn];
ull h1[maxn][maxn], h2[maxn][maxn], p1[maxn*maxn], p2[maxn*maxn];

void pre() {
p1[0] = p2[0] = 1;
for (int i = 1; i <= maxn; i++) {
p1[i] = p1[i-1] * P1;
p2[i] = p2[i-1] * P2;
}
}

void getHash(const char s1[][maxn], ull h[][maxn], int n, int m) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
h[i][j] = h[i-1][j] * P1 + h[i][j-1] * P2 - h[i-1][j-1] * P1 * P2 + (s1[i][j]-'a');
}
}
}

ull Hash(const ull h[][maxn], int x1, int y1, int x2, int y2) {
return h[x2][y2] - h[x1-1][y2] * p1[x2-x1+1] - h[x2][y1-1] * p2[y2-y1+1]
+ h[x1-1][y1-1] * p1[x2-x1+1] * p2[y2-y1+1];
}

void solve() {
ll ans = 0;
for (int i = 1; i + n2 - 1 <= n1; i++) {
for (int j = 1; j + m2 - 1 <= m1; j++) {
if (Hash(h1, i, j, i+n2-1, j+m2-1) == h2[n2][m2]) ans++;
}
}
printf("%lld\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
// get mi
pre();

int T;
cin >> T;
while (T--) {
// init
scanf("%d%d", &n1, &m1);
for (int i = 1; i <= n1; i++) scanf("%s", s1[i]+1);
getHash(s1, h1, n1, m1);

scanf("%d%d", &n2, &m2);
for (int i = 1; i <= n2; i++) scanf("%s", s2[i]+1);
getHash(s2, h2, n2, m2);

// then solve
ull res = Hash(h1, 0, 0, 1, 1);
solve();
}
}

AC 自动机实现二维匹配

矩阵P(x×y),T(n×m)\bold{P}(x \times y), \bold{T}(n \times m)
很容易想到,将PP 的第ii 行,i[1,x], P[i]\forall i \in [1, x], \ P[i] 插入 AC 自动机中
执行insert(P[i],i)\text{insert}(P[i], i),这里需要在行结尾(即字符串末尾节点)uu,维护一个vector\text{vector}
vec[u]={}\text{vec}[u] = \{\cdots \},存储uu 这个点是哪些行的结尾?
如果遍历 AC 自动机走到了某个行尾节点,vec[u]\text{vec}[u] 表示PPTT 匹配上的行有哪些

查询的时候,对TT 的每一行执行find(T[u])\text{find}(T[u])
接着根据字符串T[u]T[u] 执行标准的 AC 自动机查找
len(T[u])=m,i[1len(T[u])]\text{len}(T[u]) = m, \quad \forall i \in [1 \cdots \text{len}(T[u])],遍历 AC 自动机
p=0p = 0 开始沿着c=T[u][i]c = T[u][i]
对于某个ii,此时走到了 AC 自动机的pp 节点

  • 如果pp 为串尾节点,val(p)0val(p) \neq 0,那么遍历vec[p],  rvec[p]\text{vec}[p], \ \forall \ r \in \text{vec}[p]
    此时P\bold{P} 中第rr 行能够匹配上,也就是说
    T(ur+1,iy+1)T(u-r+1, i-y+1) 为左上角的x×yx \times y 矩形,能匹配上的行数+1+1
    cnt(ur+1,iy+1)+=1\text{cnt}(u-r+1, i-y+1) += 1
  • 否则的话,如果last(p)0last(p) \neq 0,同样遍历rvec[last(p)]\forall r \in \text{vec}[last(p)],执行cnt(ur+1,iy+1)+=1\text{cnt}(u-r+1, i-y+1) += 1

最后只要遍历(i,j)T(n×m)(i, j) \in \bold{T}(n \times m),如果满足cnt(i,j)=xcnt(i, j) = x
那么ans+=1ans += 1

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
101
102
103
104
105
106
107
108
109
110
const int maxn = 1000 + 10;
const int N = 10000 + 10, SZ = 27;
char P[maxn][maxn], T[maxn][maxn];
int n, m, x, y, cnt[maxn][maxn];

class AC {
public:
int t[N][SZ], fail[N], val[N], last[N];
vector<int> vec[N];
int tot = 0;

void clear() {
tot = 0;
for (int i = 0; i < N; i++) vec[i].clear();
memset(t, 0, sizeof t);
memset(fail, 0, sizeof fail);
memset(val, 0, sizeof val);
memset(last, 0, sizeof last);
}

void insert(const char *str, int idx) {
int p = 0;
assert(strlen(str) == y);
for (int i = 0; i < strlen(str); i++) {
int c = str[i] - 'a';
if (!t[p][c]) t[p][c] = ++tot;
p = t[p][c];
}
val[p] = idx, vec[p].push_back(idx);
}

void build() {
queue<int> que;
for (int i = 0; i < SZ; i++) {
if (t[0][i]) que.push(t[0][i]);
}

while (que.size()) {
auto u = que.front(); que.pop();
for (int i = 0; i < SZ; i++) {
if (t[u][i]) {
fail[t[u][i]] = t[fail[u]][i];
que.push(t[u][i]);
}
else t[u][i] = t[fail[u]][i];
}
last[u] = val[fail[u]] ? fail[u] : last[fail[u]];
}
}

void find(int u) {
int p = 0;
for (int i = 1; i <= m; i++) {
int c = T[u][i] - 'a';
p = t[p][c];
if (val[p]) {
for (auto r : vec[p]) {
if (u-r+1 >= 1) ++cnt[u-r+1][i-y+1];
}
}
else if (last[p]) {
for (auto r : vec[last[p]]) {
if (u-r+1 >= 1) ++cnt[u-r+1][i-y+1];
}
}
}
}
} ac;

void solve() {
for (int u = 1; u <= n; u++) ac.find(u);
int ans = 0;
for (int i = 1; i + x - 1 <= n; i++) {
for (int j = 1; j + y - 1 <= m; j++) {
if (cnt[i][j] == x) ans++;
}
}
printf("%d\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
cin >> kase;
while (kase--) {
// init
ac.clear();
memset(cnt, 0, sizeof cnt);

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", T[i]+1), assert(strlen(T[i]+1) == m);

scanf("%d%d", &x, &y);
for (int i = 1; i <= x; i++) {
scanf("%s", P[i]+1);
ac.insert(P[i]+1, i);
}

if (n < x || m < y) {
puts("0");
continue;
}

// build
ac.build();

// solve
solve();
}
}

AC 自动机和 dp

AC 自动机和 dp 有关的算法,经常需要借助last\text{last} 指针写状态转移方程
NVWLS
给出一个字典,每个单词去掉元音字母A, E, I, O, U\text{A, E, I, O, U} 之后形成了一个新字典
先给出一个只有辅音字母的串,用原字典(包含元音字母)的单词还原该串
如果存在多种还原方式,输出还原后元音字母数量最多的结果

  • 很容易想到,将初始单词插入AC\text{AC} 自动机中,不插入元音字母
  • for i\textbf{for} \ \forall i 遍历模版串str(i)\text{str}(i),并且找到 AC 自动机中表示str(i)\text{str}(i) 的节点pp
    for kplast(p)\textbf{for} \ \forall k \in p \to \text{last}(p),如果kk 为单词节点
    AC 自动机维护单词节点编号id,End(k)=idid, \quad \text{End}(k) = id
    同时还需要维护cnt(id)\text{cnt}(id),表示idid 这个单词有多少个元音字母
    len(id)\text{len}(id) 表示idid 这个单词除掉元音字母的长度,由此可以写出状态转移方程
    f(i)f(i) 表示str(i)\text{str}(i) 这个位置还原补上元音字母后str[0i]\text{str}[0\cdots i] 的最长长度,那么
    f(i)=max(f(ilen[id]))+cnt(id)f(i) = \max (f(i - \text{len}[id])) + \text{cnt}(id)
    dp\text{dp} 更新的时候记录状态used(i)=id\text{used}(i) = id,表示ii 这个位置用了idid 这个单词
  • 输出结果的时候递归输出print(plen(used(p)))\text{print}(p - \text{len}(\text{used}(p)))

另外,值得注意的是,有可能单词去掉元音字母后,得到一样的单词
但是,cnt(A)>cnt(B)\text{cnt}(A) > \text{cnt}(B)AA 还原成的单词元音字母大于BB
在 AC 自动机中维护End(p)=id\text{End}(p) = id 以及val(p)\text{val}(p) 的最大值
其中val(p)\text{val}(p) 表示pp 这个节点能够还原成的最多的元音字母数

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
101

const int maxn = 3e5 + 10, SZ = 26;
int n, cnt[maxn], len[maxn], f[maxn], used[maxn];
string S[maxn];
char str[maxn];

class AC {
public:
int t[maxn][SZ], fail[maxn], End[maxn], last[maxn];
int tot = 0;

void clear() {
memset(t, 0, sizeof t);
memset(fail, 0, sizeof fail);
memset(End, 0, sizeof End);
memset(last, 0, sizeof last);
tot = 0;
}

void insert(const string &str, int id) {
int p = 0;
for (auto x : str) {
int c = x - 'A';
if (!t[p][c]) t[p][c] = ++tot;
p = t[p][c];
}
if (cnt[id] >= cnt[End[p]]) End[p] = id;
}

void build() {
queue<int> que;
for (int i = 0; i < SZ; i++) {
if (t[0][i]) que.push(t[0][i]);
}
while (que.size()) {
auto u = que.front(); que.pop();
for (int i = 0; i < SZ; i++) {
if (t[u][i]) {
fail[t[u][i]] = t[fail[u]][i];
que.push(t[u][i]);
}
else t[u][i] = t[fail[u]][i];
}
last[u] = End[fail[u]] ? fail[u] : last[fail[u]];
}
}
} ac;

void dp(const char *str) {
int N = strlen(str+1);
for (int i = 1; i <= N; i++) f[i] = -1;
f[0] = 0;

int p = 0;
for (int i = 1; i <= N; i++) {
int c = str[i] - 'A';
p = ac.t[p][c];

for (int j = p; j; j = ac.last[j]) {
if (!ac.End[j]) j = ac.last[j];
int id = ac.End[j];
if (id && f[i - len[id]] != -1 && f[i - len[id]] + cnt[id] > f[i]) {
f[i] = f[i-len[id]] + cnt[id], used[i] = id;
}
}
}
}

void print(const int p) {
if (p < 1) return;
print(p - len[used[p]]);
printf("%s ", S[used[p]].c_str());
}

inline bool vowel(const char ch) {
return ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
}

int main() {
freopen("input.txt", "r", stdin);
ac.clear();

cin >> n;
for (int i = 1; i <= n; i++) {
cin >> S[i];
string t;
for (auto c : S[i]) {
if (!vowel(c)) t += c;
else cnt[i]++;
}
len[i] = t.length();
ac.insert(t, i);
}
ac.build();

scanf("%s", str+1);
dp(str);

print(strlen(str+1));
puts("");
}