AC 自动机刷题记录

时间：2023-03-09 00:19:16
AC 自动机刷题记录

简介

这就是用来记录我对于《信息学奥赛一本通 · 提高篇》一书中的习题的刷题记录以及学习笔记。

一般分专题来写（全部写一起可能要加载很久...），比如本章就是用来记录AC自动机的。

再插一句：Loj 真是个不错的 OJ，如果说洛谷是最棒的 OIer 社区，那 Loj 就是最棒的刷题专区。

PS：这里的“最棒的”仅仅指带给我的练习感觉最好，例如画风好康，且仅代表个人意见。

专题介绍：AC 自动机，高效的多模匹配算法，是 trie 与 KMP 的综合运用，主要靠 \(fail[]\) 指针加快速度。

一般 AC 自动机的题目都十分毒瘤（神犇勿喷），如果你还不了解 AC 自动机，可以康康我的文章。

第一题

#10057 「一本通 2.4 例 1」Keywords Search

裸题？确实是裸题，不讲了。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#include <queue>

#define N 10010

#define M 1000010

using namespace std;

int n, T, trie[N][30], cnt[N], fail[N], tot = 1;

long long ans = 0;

char s[N], a[M];

int read() {

    int x = 0, f = 1;

    char c = getchar();

    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();

    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();

    return x * f;

}

void insert(char* a) {

    int p = 1, len = strlen(a);

    for (int i = 0; i < len; i++) {

        int ch = a[i] - 'a';

        if (!trie[p][ch])

            trie[p][ch] = ++tot;

        p = trie[p][ch];

    }

    cnt[p]++;

    return;

}

void get_fail() {

    queue<int> q;

    for (int i = 0; i < 26; i++) {

        if (!trie[1][i]) {

            trie[1][i] = 1;

            continue;

        }

        fail[trie[1][i]] = 1;

        q.push(trie[1][i]);

    }

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        for (int i = 0; i < 26; i++) {

            if (trie[now][i]) {

                fail[trie[now][i]] = trie[fail[now]][i];

                q.push(trie[now][i]);

            } else

                trie[now][i] = trie[fail[now]][i];

        }

    }

    return;

}

void AC_find(char* a) {

    int p = 1, len = strlen(a);

    for (int i = 0; i < len; i++) {

        p = trie[p][a[i] - 'a'];

        for (int j = p; j && cnt[j] != -1; j = fail[j]) {

            ans += cnt[j];

            cnt[j] = -1;

        }

    }

    return;

}

int main() {

    T = read();

    while (T--) {

        tot = 1;

        ans = 0;

        memset(trie, 0, sizeof(trie));

        memset(cnt, 0, sizeof(cnt));

        memset(fail, 0, sizeof(fail));

        n = read();

        for (int i = 1; i <= n; i++) {

            scanf("%s", s);

            insert(s);

        }

        get_fail();

        scanf("%s", a);

        AC_find(a);

        printf("%lld\n", ans);

    }

    return 0;

}

第二题

#10058 「一本通 2.4 练习 1」玄武密码

又是裸题？至少需要一点技巧了。

一开始的想法是 vector + AC 自动机暴力统计，发现 20 分 TLE 滚粗。

所以怎么办？方法如下：

  1. 根据传统的 AC 自动机，在 trie 树上跑母串。
  2. 每到一个点就标记它的每一个 \(fail[]\) 指针。（包括他本身）
  3. 统计答案时，从每个单词的最下方往前跳，第一个被标记的节点的下标即为答案。

证明略。（你都是打 AC 自动机的人了，至少是提高组吧，这点水平应该还是有的）

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <cmath>

#include <queue>

#include <cstring>

#define N 10000010

#define M 100010

using namespace std;

int ch[50], n, m, tot = 0;

int trie[N][5], fail[N], end[M], l[M], pre[N], flag[N];

char a[N], s[110];

void insert(char* a, int x) {

    int p = 0, len = strlen(a);

    l[x] = len;

    for (int i = 0; i < len; i++) {

        int c = ch[a[i] - 'A'];

        if (!trie[p][c]) {

            trie[p][c] = ++tot;

            pre[tot] = p;

        }

        p = trie[p][c];

    }

    end[x] = p;

    return;

}

void get_fail() {

    queue<int> q;

    for (int i = 0; i < 4; i++)

        if (trie[0][i])

            fail[trie[0][i]] = 0, q.push(trie[0][i]);

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        for (int i = 0; i < 4; i++) {

            if (trie[now][i]) {

                fail[trie[now][i]] = trie[fail[now]][i];

                q.push(trie[now][i]);

            } else

                trie[now][i] = trie[fail[now]][i];

        }

    }

    return;

}

void AC_work() {

    int len = strlen(a), p = 0;

    for (int i = 0; i < len; i++) {

        p = trie[p][ch[a[i] - 'A']];

        int k = p;

        while (k > 1) {

            if (flag[k])

                break;

            flag[k] = true;

            k = fail[k];

        }

    }

    return;

}

int get_ans(int x) {

    int p = end[x];

    for (int i = l[x]; i; i--) {

        if (flag[p])

            return i;

        p = pre[p];

    }

    return 0;

}

int main() {

    memset(flag, false, sizeof(flag));

    ch['N' - 'A'] = 0;

    ch['S' - 'A'] = 1;

    ch['W' - 'A'] = 2;

    ch['E' - 'A'] = 3;

    scanf("%d %d", &n, &m);

    scanf("%s", a);

    for (int i = 1; i <= m; i++) {

        scanf("%s", s);

        insert(s, i);

    }

    get_fail();

    AC_work();

    for (int i = 1; i <= m; i++) printf("%d\n", get_ans(i));

    return 0;

}

第三题

#10059 「一本通 2.4 练习 2」Censoring

裸题？不存在的。

经典的 AC 自动机 + 栈 的题目，还记得我们做过一道 KMP + 栈 的题目吗。（不记得）

类似的，在 AC 自动机的同时用栈维护即可啦。

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <cstring>

#include <queue>

#define N 100010

using namespace std;

int n, trie[N][30], fail[N], jl[N], sk[N], tot = 0, cnt = 0, ed[N];

char s[N], t[N], ans[N];

void insert(char* a) {

    int p = 0, len = strlen(a);

    for (int i = 0; i < len; i++) {

        int ch = a[i] - 'a';

        if (!trie[p][ch])

            trie[p][ch] = ++tot;

        p = trie[p][ch];

    }

    ed[p] = len;

    return;

}

void get_fail() {

    queue<int> q;

    for (int i = 0; i < 26; i++)

        if (trie[0][i])

            fail[trie[0][i]] = 0, q.push(trie[0][i]);

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        for (int i = 0; i < 26; i++) {

            if (trie[now][i]) {

                fail[trie[now][i]] = trie[fail[now]][i];

                q.push(trie[now][i]);

            } else

                trie[now][i] = trie[fail[now]][i];

        }

    }

    return;

}

void AC_work() {

    int p = 0, len = strlen(s);

    for (int i = 0; i < len; i++) {

        p = trie[p][s[i] - 'a'];

        jl[i] = p;

        sk[++cnt] = i;

        if (ed[p]) {

            cnt -= ed[p];

            p = jl[sk[cnt]];

        }

    }

    return;

}

int main() {

    memset(ed, 0, sizeof(ed));

    scanf("%s", s);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%s", t);

        insert(t);

    }

    get_fail();

    AC_work();

    for (int i = 1; i <= cnt; i++) printf("%c", s[sk[i]]);

    printf("\n");

    return 0;

}

第四题

#10060 「一本通 2.4 练习 3」单词

用到 fail 树，不知道，康康 这篇文章。

因为题目中 所有的模式串=文本串，所以本题甚至连 fail 树都不用建。

同样的运用 fail 树的思想，通过逆 BFS 序统计答案即可。

为什么是逆 BFS 序？其实就是从下往上想根节点集中，也就是上面的统计子树大小。

但是由于本题的特殊性质（所有的模式串=文本串），只要一个循环就可以搞定了。

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <cstring>

#define N 1000010

using namespace std;

int n, trie[N][30], fail[N], sum[N], match[N];

int tot = 0, head, tail, q[N];

char s[N];

void insert(char* a, int x) {

    int p = 0, len = strlen(a);

    for (int i = 0; i < len; i++) {

        int ch = a[i] - 'a';

        if (!trie[p][ch])

            trie[p][ch] = ++tot;

        p = trie[p][ch];

        sum[p]++;

    }

    match[x] = p;

    return;

}

void get_fail() {

    tail = head = 0;

    for (int i = 0; i < 26; i++)

        if (trie[0][i])

            fail[trie[0][i]] = 0, q[++tail] = trie[0][i];

    while (head < tail) {

        int now = q[++head];

        for (int i = 0; i < 26; i++)

            if (trie[now][i]) {

                fail[trie[now][i]] = trie[fail[now]][i];

                q[++tail] = trie[now][i];

            } else

                trie[now][i] = trie[fail[now]][i];

    }

    return;

}

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%s", s);

        insert(s, i);

    }

    get_fail();

    for (int i = tail; i >= 0; i--) sum[fail[q[i]]] += sum[q[i]];

    for (int i = 1; i <= n; i++) printf("%d\n", sum[match[i]]);

    return 0;

}

第五题

#10062 「一本通 2.4 练习 5」病毒

关键：判断是否有无限长的非病毒串。（废话）

建立 trie 图，显然当有一条路径可以不经过模式串而形成环时有无限长的非病毒串。

然后判环就可以了，怎么判？拓扑排序会不会？DFS 会不会？随便你挑。

这里选择 拓扑排序 判环。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cmath>

#include <queue>

#define N 300010

using namespace std;

int n, trie[N][2], fail[N], tot = 0, ru[N], head[N], cnt = 0;

bool ed[N];

char s[N];

struct node {

    int nxt, to;

} edge[N];

void insert(char* a) {

    int p = 0, len = strlen(a);

    for (int i = 0; i < len; i++) {

        int ch = a[i] - '0';

        if (!trie[p][ch])

            trie[p][ch] = ++tot;

        p = trie[p][ch];

    }

    ed[p] = true;

    return;

}

void get_fail() {

    queue<int> q;

    for (int i = 0; i < 2; i++)

        if (trie[0][i])

            fail[trie[0][i]] = 0, q.push(trie[0][i]);

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        ed[now] |= ed[fail[now]];

        for (int i = 0; i < 2; i++)

            if (trie[now][i]) {

                fail[trie[now][i]] = trie[fail[now]][i];

                q.push(trie[now][i]);

            } else

                trie[now][i] = trie[fail[now]][i];

    }

    return;

}

void addedge(int x, int y) {

    ru[y]++;

    cnt++;

    edge[cnt].nxt = head[x];

    edge[cnt].to = y;

    head[x] = cnt;

    return;

}

bool topo() {

    queue<int> q;

    int sum = 0;

    for (int i = 1; i <= tot; i++) {

        if (ed[i]) {

            sum++;

            continue;

        }

        for (int j = 0; j < 2; j++)

            if (!ed[trie[i][j]])

                addedge(i, trie[i][j]);

    }

    for (int i = 1; i <= tot; i++)

        if (!ed[i] && !ru[i])

            q.push(i);

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        sum++;

        for (int i = head[now]; i; i = edge[i].nxt)

            if (!--ru[edge[i].to])

                q.push(edge[i].to);

    }

    return sum == tot;

}

int main() {

    memset(ed, false, sizeof(ed));

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%s", s);

        insert(s);

    }

    get_fail();

    memset(ru, 0, sizeof(ru));

    if (!topo())

        printf("TAK\n");

    else

        printf("NIE\n");

    return 0;

}

第六题

#10063 「一本通 2.4 练习 6」文本生成器

DP + AC 自动机，很神仙的做法。

AC 自动机的 DP 都非常套路，大部分 \(f[i][j]\) 表示当前在节点 \(j\),且串长为i时的情况，

有时再加一维表示这个状态里面包含了哪些东西，而且 AC 自动机的 DP 会经常让你用矩阵乘法优化。

那么对于这个题，我们可以先将AC自动机建立出来，然后搞一个简单的容斥：用所有的情况减去不可读的情况。

那么那些是不可读的情况呢？当然就是跑不到单词结尾节点的情况喽……

定义 \(f[i][j]\) 表示当前在 \(j\) 点且串长为 \(i\) 时不经过单词结尾的路径条数，然后从父亲往儿子转移即可。

注意如果一个单词的后缀是一个可读单词(即 fail 指针指向可读单词的结尾节点)

那么这个单词一定也是可读的，我们就不能往这个单词走了。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <iostream>

#include <queue>

#define N 10010

#define MOD 10007

using namespace std;

int n, m, f[N][N], tot = 0, ans = 0, trie[N][30], fail[N];

bool ed[N];

char a[110];

void insert(char* a) {

    int p = 0, len = strlen(a);

    for (int i = 0; i < len; i++) {

        int ch = a[i] - 'A';

        if (!trie[p][ch])

            trie[p][ch] = ++tot;

        p = trie[p][ch];

    }

    ed[p] = true;

    return;

}

void get_fail() {

    queue<int> q;

    for (int i = 0; i < 26; i++)

        if (trie[0][i]) {

            fail[trie[0][i]] = 0;

            q.push(trie[0][i]);

        }

    while (!q.empty()) {

        int now = q.front();

        q.pop();

        for (int i = 0; i < 26; i++) {

            if (!trie[now][i]) {

                trie[now][i] = trie[fail[now]][i];

                continue;

            }

            ed[trie[now][i]] |= ed[trie[fail[now]][i]];

            fail[trie[now][i]] = trie[fail[now]][i];

            q.push(trie[now][i]);

        }

    }

    return;

}

int main() {

    scanf("%d %d %d", &n, &m);

    for (int i = 1; i <= n; i++) {

        scanf("%s", a);

        insert(a);

    }

    get_fail();

    f[0][0] = 1;

    for (int i = 1; i <= m; i++)

        for (int j = 0; j <= tot; j++)

            for (int k = 0; k < 26; k++)

                if (!ed[trie[j][k]])

                    (f[i][trie[j][k]] += f[i - 1][j]) %= MOD;

    for (int i = 0; i <= tot; i++) (ans += f[m][i]) %= MOD;

    int sum = 1;

    for (int i = 1; i <= m; i++) sum = sum * 26 % MOD;

    printf("%d\n", (sum - ans + MOD) % MOD);

    return 0;

}

相关文章