本文共 2270 字，大约阅读时间需要 7 分钟。

屏蔽词删除

题目链接：

题目大意

有一个字符串，然后又一些指定的小串。

你会从头开始找到第一个字符串的子串使得它是某个小串，然后把这个串从字符串中删除。
然后继续重复这个操作，知道找不到这些小串在字符串中出现。

问你最后的字符串。

思路

那你看到这种这个每次都要查询众多小串在一个串中是否出现，自然想到 AC 自动机。

但是也不是每次暴力查询啊。
我们考虑变形。
你想，如果把一个串的某个子串删除了，那会怎么样。
（其实你会想到它一定是删除当前的一个后缀）

那每次删除后缀其实就是一个栈的过程。（这是我 A 了才发现的）
我做的时候是觉得它删除就相当于你跑串在 Trie 树上的位置后退了，退回了删除之后的串所在的位置。
那因为你只回删后缀，那我们可以记录每个前缀最后的位置，然后你删了后缀得到的前缀就可以找到位置了。

然后因为做的时候没有想到栈，我删除是暴力跑标记，然后碰到已经标记的就跳到它前面第一个没有标记的地方。（这个东西可以维护）

然后你最后只要跑字符串，然后把没有标记过的输出即可。

代码

#include<queue>#include<cstdio>#include<cstring>using namespace std;struct Trie {   	int son[30], fail, size, fa;}tree[200001];char s[100001], c[100001];int tot, n, np[100001], bef[100001], end[100001];bool no[100001];queue <int> q;void insert() {   //用小串构成 Trie 树	int size = strlen(c);	int now = 0;		for (int i = 0; i < size; i++) {   		int go = c[i] - 'a';		if (!tree[now].son[go]) tree[now].son[go] = ++tot, tree[tree[now].son[go]].fa = now;		now = tree[now].son[go];	}		tree[now].size = size; }void get_fail() {   //建 Trie 树上的 fail 边	for (int i = 0; i < 26; i++)		if (tree[0].son[i]) {   			q.push(tree[0].son[i]);			tree[tree[0].son[i]].fail = 0;		}		while (!q.empty()) {   		int now = q.front();		q.pop();				for (int i = 0; i < 26; i++)			if (tree[now].son[i]) {   				q.push(tree[now].son[i]);				tree[tree[now].son[i]].fail = tree[tree[now].fail].son[i];			}			else tree[now].son[i] = tree[tree[now].fail].son[i];	}}void cut(int ed, int size) {   	int rc = ed;	while (size--) {   		while (no[ed]) {   			ed = bef[ed];		}		no[ed] = 1;		ed--;	}	bef[rc] = ed;}void work() {   	int size = strlen(s);	int now = 0;		for (int i = 0; i < size; i++) {   		int go = s[i] - 'a';		if (tree[now].son[go]) {   //有这个串			now = tree[now].son[go];			if (tree[now].size) {   				cut(i, tree[now].size);//把这个字符串抹掉				now = end[bef[i]];//跳回到字符串第一个没有被抹掉的最右的位置			}		}		else {   			while (now && !tree[tree[now].fail].son[go]) {   				now = tree[now].fail;//跳找有没有这个串			}			if (!now) now = tree[now].son[go];//没有，重新走				else now = tree[tree[now].fail].son[go];//否则就从找到的串继续		}				end[i] = now;//记录最后的位置	}}int main() {   	scanf("%s", &s);	scanf("%d", &n);		for (int i = 1; i <= n; i++) {   		scanf("%s", &c);		insert();	}		get_fail();		work();		int size = strlen(s);	for (int i = 0; i < size; i++)		if (!no[i]) putchar(s[i]);		return 0;}