洛谷P3121 [USACO15FEB] Censoring G 题解

题目链接：P3121 [USACO15FEB] Censoring G

题意：给出文本串 $t$ 和$n$ 个模式串 $s$ ，删除在 $t$ 中第一次出现的子串 $s_i$ ，并重复这个过程（在产生的新串 $t’$ 上继续删除操作），求最后的结果（所有模式串都要删掉）

多模式串匹配很容易想到是AC自动机

那删除操作怎么处理呢？

注意到删除子串后，在删除的子段后继续匹配可能需要该子段前的已经算出（显然）的匹配值

那么我们可以用两个栈分别维护匹配时的经过的点和答案

在每次删除后我们只要跳回原来的点即可

时间复杂度 $O(|t| + \sum |s_i|)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(1e5+5)
int n,tot,top,trie[MAXN][32];
char ans[MAXN];
char t[MAXN],s[MAXN];
int fail[MAXN],e[MAXN],dep[MAXN],stk[MAXN];
void insert(int l,char *s)
{
	int u=0;
	for(int i=1; i<=l; i++)
	{
		int c=s[i]-'a';
		if(!trie[u][c])trie[u][c]=++tot;
		u=trie[u][c];
	}
	e[u]=1;
}
queue<int> q;
void build()
{
	for(int i=0; i<26; i++)
		if(trie[0][i])
		{
			q.push(trie[0][i]);
			dep[trie[0][i]]=1;
		}
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int i=0; i<26; i++)
		{
			if(trie[u][i])
			{
				fail[trie[u][i]]=trie[fail[u]][i];
				q.push(trie[u][i]);dep[trie[u][i]]=dep[u]+1;
			}else
				trie[u][i]=trie[fail[u]][i];
		}
	}
}
void AC(int l,char *t)
{
	int u=0;stk[0]=u; // 根节点不要忘了
	for(int i=1; i<=l; i++)
	{
		u=trie[u][t[i]-'a'];
		stk[++top]=u;
		ans[top]=t[i];
		if(e[u])top-=dep[u],u=stk[top];
	}
	ans[top+1]='\0'; // 不要忘了哦！
}
signed main()
{
	scanf("%s\n",t+1);
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)
		scanf("%s",s+1),insert(strlen(s+1),s);
	build();AC(strlen(t+1),t);
	printf("%s",ans+1);
	return 0;
}