长乐 Day 4

今天学trie树和AC自动机
我把昨天的KMP弄懂后，因为trie有点简单，所以在看了无数CSDN后，AC自动机就废了

这有题我觉得有点难的题，但过了
D. 【例题4】屏蔽词删除

#include <bits/stdc++.h>
using namespace std;
const int L = 1e5 + 10;
char s[L], a[L];
int trie[L][26], v[L], nxt[L], q[L], xk[L], xl[L];
int l, r, cnt, idx = 1, n, al;
void ins() {
    int k = 1;
    for (int i = 1; i <= al; i++) {
        int x = a[i] - &#039;a&#039;;
        if (!trie[k][x])
            trie[k][x] = ++idx;
        k = trie[k][x];
    }
    v[k] = al;
    return;
}
void AC_Do_first() {
    q[++r] = 1;
    nxt[1] = 0;
    for (int i = 0; i < 26; i++) trie[0][i] = 1;
    while (l < r) {
        int x = q[++l];
        for (int i = 0; i < 26; i++) {
            if (!trie[x][i])
                trie[x][i] = trie[nxt[x]][i];
            else {
                nxt[trie[x][i]] = trie[nxt[x]][i];
                q[++r] = trie[x][i];
            }
        }
    }
    return;
}
void AC_Do_second() {
    int m = strlen(s + 1), x = 1;
    for (int i = 1; i <= m; i++) {
        xk[++cnt] = i;
        int h = s[i] - &#039;a&#039;, Q = trie[x][h];
        if (trie[x][h]) {
            if (v[trie[x][h]]) {
                cnt -= v[trie[x][h]];
                x = xl[xk[cnt]];
                continue;
            }
        }
        x = xl[i] = Q;
    }
    return;
}
int main(void) {
    scanf("%s", s + 1);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%s", a + 1);
        al = strlen(a + 1);
        ins();
    }
    AC_Do_first();
    AC_Do_second();
    for (int i = 1; i <= cnt; i++) printf("%c", s[xk[i]]);
    return 0;
}

我觉得那个 AC_Do_second 有点难写，其余还好
太晚了，回宿舍了