USACO 2015 Feb Gold 检查 （AC自动机+栈）

发表于 |
字数统计: 840字 | 阅读时长 ≈ 4min

【USACO 2015 Feb Gold】检查

问题描述

FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表，列表里的n个单词记为t_1…t_N。他希望从S中删除这些单词。
FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词
FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的
请帮助FJ完成这些操作并输出最后的S

输入格式

第一行包含一个字符串S
第二行包含一个整数N
接下来的N行，每行包含一个字符串，第i行的字符串是t_i

输出格式

一行，输出操作后的S

样例输入

begintheescapexecutionatthebreakofdawn
2
escape
execution

样例输出

beginthatthebreakofdawn

提示

t_1…t_N的长度和不超过10^5
所有字符串都只包含小写字母

显然建立AC自动机进行匹配，那么考虑删除操作，用一个栈来存已匹配过的主串，那么删除时直接退栈即可，问题在于退栈后应该从AC自动机的哪一个节点开始讨论，因此需要存下主串每一个位置匹配后在AC自动机上的位置，那么退栈时只要跑到之前存下的位置即可。

需要注意的是建立Fail指针的时候，某些写法会超时，背一个优秀的模板。（有限状态自动机）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 100005
using namespace std;
struct node{int Son[26],k,Fail,dep;};
node trie[N*10];
char S[N],s[N];
int C[N],D[N],Top;
int n,l,tot=1;
queue<int>Q;
void Ins()
{
	int i,p=1,le=strlen(s)-1;
	for(i=1;i<=le;i++)
	{
		int t=s[i]-'a';
		if(!trie[p].Son[t])trie[p].Son[t]=++tot,trie[tot].dep=trie[p].dep+1;
		p=trie[p].Son[t];
	}
	trie[p].k=1;
}
void BUF()
{
	int i,p,son,tmp;
	for(i=0;i<26;i++)
	{
		if(trie[1].Son[i])trie[trie[1].Son[i]].Fail=1,Q.push(trie[1].Son[i]);
		else trie[1].Son[i]=1;
	}
	while(Q.size())
	{
		p=Q.front();Q.pop();
		for(i=0;i<26;i++)
		if(trie[p].Son[i])trie[trie[p].Son[i]].Fail=trie[trie[p].Fail].Son[i],Q.push(trie[p].Son[i]);
		else trie[p].Son[i]=trie[trie[p].Fail].Son[i];
	}
}
void Find()
{
	int i=0,p=1,t;D[0]=1;
	while(++i<=l)
	{
		t=S[i]-'a';
		p=D[C[Top]];
		C[++Top]=i;
		while(p&&(!trie[p].Son[t]))p=trie[p].Fail;
		p=trie[p].Son[t];
		if(!p)p=1;
		if(trie[p].k==1)Top-=trie[p].dep;
		D[i]=p;
	}
}
int main()
{
	int i;
	scanf("%s",&S[1]);S[0]='%';
	l=strlen(S)-1;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%s",&s[1]);s[0]='%';
		Ins();
	}
	BUF();Find();
	for(i=1;i<=Top;i++)printf("%c",S[C[i]]);
}