[USACO15FEB] Censoring

给定文章串 (S)，要从 (S) 中删去由 (n) 个单词构成的单词簿中的所有单词。每次找到最早出现的单词并且删除，重复操作到没有单词簿中的单词为止。输出最后的 (S)。

Solution

可以理解为每次碰到对应的单词就按若干下退格键

于是一个直观的想法是：我们把 (S) 扔到 ACAM 上跑，跑到匹配的结点就往父亲上跳若干次？

显然这样并不正确，我们应当要记录每个时刻所在的结点来实现退格

不难想到用栈来维护

一个栈记录结点编号，一个栈记录输出串

遇到匹配的情况，就两个栈一起弹出长度次

#include <bits/stdc++.h>
using namespace std;

int val[100005],ch[100005][26],fi[100005],n,m,ind,top,num[100005];
char str[100005],art[100005],pri[100005];

void insert(char *s){
	int len=strlen(s),p=0;
	for(int i=0;i<len;i++){
		int v=s[i]-'a';
		if(!ch[p][v]) ch[p][v]=++ind;
		p=ch[p][v];
	}
	val[p]=len; 
}

void build(){
	queue <int> q;
	for(int i=0;i<26;i++)
		if(ch[0][i])
			q.push(ch[0][i]);
	while(!q.empty()){
		int p=q.front(); q.pop();
		for(int i=0;i<26;i++)
			if(ch[p][i]) fi[ch[p][i]]=ch[fi[p]][i], q.push(ch[p][i]);
			else ch[p][i]=ch[fi[p]][i];
	}
}

int query(char *s){
	int len=strlen(s), p=0, ans=0;
	for(int i=0;i<len;i++){
		p=ch[p][s[i]-'a'];
		++top;
		num[top]=p;
		pri[top]=s[i];
		if(val[p]>0) {
			top-=val[p];
			if(!top) p=0; 
			else p=num[top];
		}
	}
	return top;
}

int main(){
	scanf("%s",&art);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",str), insert(str);
	build();
	query(art);
	for(int i=1;i<=top;i++) printf("%c",pri[i]);
}