Theme NexT works best with JavaScript enabled

关于一副对联

横批:cslnb

AC 自动机 fail 树上 DFS 序建可持久化线段树

题意

题目来源:Codeforce 547E

给定 $ n $ 个模式串。共 $ m $ 次询问,每次询问给定 $ l, r, k $ ,询问从模式串 $ l $ 到模式串 $ r $ 中主串 $ k $ 作为其子串共出现了多少次(同一个串中可能多次出现,且允许重叠)。

解法

从 AC 自动机的角度考虑,我们知道对于字符串 $ s $ ,记它对应的节点为 $ p $ ,那么 fail 树上以 $ p $ 为根节点的的子树的节点数量即为 $ s $ 出现的总次数。其中利用 DFS 序即可线性计算每一棵子树的大小。

不过这里的总次数是指在当前所有的模式串中出现的总次数,而非特定区间的。所以用可持久化线段树维护每一个版本的 DFS 序,用第 $ r $ 个版本的总数量减去第 $ l-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
#include <bits/stdc++.h>
using namespace std;
#define N 200007
// Trie
int ch[N][26], trie_num;

// fail tree
int fail[N];
vector<int> son[N];

// pattern string
int trie_add[N], lens[N];
vector<int> rec[N];

void insert(char *s, int id) {
lens[id] = strlen(s);
int p = 0;
for (int i = 0; i < lens[id]; i++) {
int x = s[i] - 'a';
rec[id].push_back(x);
if (!ch[p][x]) ch[p][x] = ++trie_num;
p = ch[p][x];
}
trie_add[id] = p;
}

void get_fail() {
queue<int> que;
for (int i = 0; i < 26; i++)
if (ch[0][i]) fail[ch[0][i]] = 0, que.push(ch[0][i]);
while (!que.empty()) {
int p = que.front();
que.pop();
son[fail[p]].push_back(p);
for (int i = 0; i < 26; i++)
if (ch[p][i])
fail[ch[p][i]] = ch[fail[p]][i], que.push(ch[p][i]);
else
ch[p][i] = ch[fail[p]][i];
}
}

// DFS order
int dfs_l[N], dfs_r[N], dfs_num;
void dfs(int x) {
dfs_l[x] = ++dfs_num;
for (auto i : son[x]) dfs(i);
dfs_r[x] = dfs_num;
}

// Persistent segment tree
int root[N];
struct node {
int l, r, val;
} tree[N << 5];
int tree_num;

void change(int &p, int q, int l, int r, int add) {
p = ++tree_num, tree[p] = tree[q];
tree[p].val++;
if (l == r) return;
int mid = (l + r) >> 1;
if (add <= mid)
change(tree[p].l, tree[q].l, l, mid, add);
else
change(tree[p].r, tree[q].r, mid + 1, r, add);
}

void build(int &root_p, int root_q, int id) {
int p = 0, q = root_q;
for (int i = 0; i < lens[id]; i++) {
p = ch[p][rec[id][i]];
change(root_p, q, 1, dfs_num, dfs_l[p]);
q = root_p;
}
}

int query(int p, int q, int l, int r, int L, int R) {
if (L <= l && r <= R) return tree[p].val - tree[q].val;
int mid = (l + r) >> 1, ret = 0;
if (L <= mid) ret += query(tree[p].l, tree[q].l, l, mid, L, R);
if (R > mid) ret += query(tree[p].r, tree[q].r, mid + 1, r, L, R);
return ret;
}

char s[N];
int main() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
insert(s, i);
}
get_fail();
dfs(0);
for (int i = 1; i <= n; i++) build(root[i], root[i - 1], i);
int l, r, k;
while (q--) {
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", query(root[r], root[l - 1], 1, dfs_num,
dfs_l[trie_add[k]], dfs_r[trie_add[k]]));
}
return 0;
}

后缀自动机 next 指针 DAG 图上求 SG 函数

题意

题目来源:ACRush:是男人就过八题

给定字符串 $ s $ 以其 $ n $ 个子串 $ t[i] $ ,Alice 与 Bob 进行博弈,每次可以选择任意一个子串 $ t[i] $ ,并在其后添加一个字符,使其仍然是 $ s $ 的子串。两人轮流进行操作,Alice先行,最先不能进行操作的人输。

解法

把 $ n $ 个子串的模型转化为为 $ n $ 堆石子,把每一个子串看作是转台,那每次状态的变化,即为对一堆石子取走若干个石子,无法操作,即为没有石子可以取。这样这个问题就转化为经典的 nim 博弈。

于是利用后缀自动机线性表示 $ s $ 的每一个子串,利用后缀自动的 DAG 图进行记忆化搜索,记录 SG 函数值即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
#define ll long long
int last, num;
int ch[N][26], link[N], occur[N], maxlen[N];
void extend(int x) {
int p = last, np = last = ++num;
maxlen[np] = maxlen[p] + 1, occur[np] = 1;
while (p && !ch[p][x]) ch[p][x] = np, p = link[p];
if (!p)
link[np] = 1;
else {
int q = ch[p][x];
if (maxlen[q] == maxlen[p] + 1)
link[np] = q;
else {
int nq = ++num;
memcpy(ch[nq], ch[q], sizeof ch[nq]);
link[nq] = link[q], link[q] = link[np] = nq;
maxlen[nq] = maxlen[p] + 1;
while (p && ch[p][x] == q) ch[p][x] = nq, p = link[p];
}
}
}
char s[N];
int t[N], A[N], vis[N], sg[N];
int main() {
while (~scanf("%s", s + 1)) {
int len = strlen(s + 1);
memset(ch, 0, 4 * 26 * (num + 1));
memset(t, 0, 4 * (len + 1));
last = num = 1;
for (int i = 1; i <= len; i++) extend(s[i] - 'a');
for (int i = 1; i <= num; i++) t[maxlen[i]]++;
for (int i = 1; i <= num; i++) t[i] += t[i - 1];
for (int i = 1; i <= num; i++) A[t[maxlen[i]]--] = i;
memset(vis, 0, 4 * (num + 1));
for (int i = num; i; i--) {
int add = A[i];
for (int j = 0; j < 26; j++)
if (ch[add][j]) vis[sg[ch[add][j]]] = add;
sg[add] = 0;
while (vis[sg[add]] == add) sg[add]++;
}
int nim = 0, q;
scanf("%d", &q);
while (q--) {
scanf("%s", s + 1);
len = strlen(s + 1);
int add = 1;
for (int i = 1; i <= len; i++) add = ch[add][s[i] - 'a'];
nim ^= sg[add];
}
puts(nim ? "Alice" : "Bob");
}
return 0;
}