0xfaner's Blog

Just something trivial

关于一副对联

Posted on Edited on In ,
Symbols count in article: 4.2k Reading time ≈ 4 mins.

横批：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;
}