题目链接：USACO 2015 Feb. Gold 2

有一个字符串 $S$。Farmer John 希望在 $S$ 中删掉 $n$ 个屏蔽词（一个屏蔽词可能出现多次），这些词记为 $t_1 \sim t_n$。

FJ 在 $S$ 中从头开始寻找屏蔽词，一旦找到一个屏蔽词，FJ 就删除它，然后又从头开始寻找（而不是接着往下找）。FJ 会重复这一过程，直到 $S$ 中没有屏蔽词为止。注意删除一个单词后可能会导致 $S$ 中出现另一个屏蔽词。这 $n$ 个屏蔽词不会出现一个单词是另一个单词子串的情况，这意味着每个屏蔽词在 $S$ 中出现的开始位置是互不相同的，请帮助 FJ 完成这些操作并输出最后的 $S$。

数据范围：$1 \le \lvert S \rvert, \sum\lvert t_i \rvert \le 10 ^ 5$。

Solution

我们直接对所有的 $t_i$ 建立 AC 自动机。然后用自动机去匹配文本串 $S$，用一个栈记录节点标号和文本串位置，一旦匹配到某个模式串 $t_j$ 结尾，就把栈中 $\lvert t_j \rvert$ 个元素弹出，继续匹配下去。最后的 $S'$ 就是栈中剩下的下标位置。

时间复杂度：$\mathcal O(\lvert S \rvert + 26 \sum \lvert t_i \rvert)$。

Code

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5;

int n;
char s[N], t[N];
std::pair<int, int> stk[N];

template <int N, int S>
struct AhoCorasick {
    int idx, ch[N][S], fail[N], dep[N];
    bool end[N];
    void clear(int x) {
        memset(ch[x], 0, sizeof(ch[x]));
        fail[x] = dep[x] = 0, end[x] = false;
    }
    void clear() {
        clear(idx = 0);
    }
    int id(char c) {
        if (isdigit(c)) return c - '0';
        if (islower(c)) return c - 'a';
        if (isupper(c)) return c - 'A';
        return -1;
    }
    void insert(char *s) {
        int u = 0, n = strlen(s + 1);
        for (int i = 1; i <= n; i++) {
            int &v = ch[u][id(s[i])];
            if (!v) clear(v = ++idx);
            dep[v] = dep[u] + 1;
            u = v;
        }
        end[u] = true;
    }
    void build() {
        std::queue<int> q;
        for (int i = 0; i < S; i++) {
            int u = ch[0][i];
            if (u) fail[u] = 0, q.push(u);
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < S; i++) {
                int &v = ch[u][i];
                if (v) fail[v] = ch[fail[u]][i], q.push(v);
                else v = ch[fail[u]][i];
            }
        }
    }
};

AhoCorasick<N, 26> A;

int main() {
    scanf("%s%d", s + 1, &n);
    A.clear();
    for (int i = 1; i <= n; i++) {
        scanf("%s", t + 1);
        A.insert(t);
    }
    A.build();
    int len = strlen(s + 1), top = 0;
    for (int i = 1, u = 0; i <= len; i++) {
        u = A.ch[u][A.id(s[i])];
        stk[++top] = std::make_pair(i, u);
        if (A.end[u]) {
            u = stk[top -= A.dep[u]].second;
        }
    }
    for (int i = 1; i <= top; i++) {
        putchar(s[stk[i].first]);
    }
    puts("");
    return 0;
}