[BZOJ3940]:[Usaco2015 Feb]Censoring（AC自动机）

柔光的暖阳◎ 2022-01-10 04:41 153阅读 0赞

[题目传送门][Link 1]

--------------------

题目描述：

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

--------------------

输入格式：

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

--------------------

输出格式：

一行，输出操作后的S。

--------------------

样例：

样例输入：

begintheescapexecutionatthebreakofdawn  
2  
escape  
execution

样例输出：

beginthatthebreakofdawn

--------------------

数据范围与提示：

n≤2000

--------------------

题解：

不难想到这样一道题：

给出两个字符串S和T，每次从前往后找到S的一个子串A=T并将其删除，空缺位依次向前补齐，重复上述操作多次，直到S串中不含T串。输出最终的S串。（[原题见\[BZOJ3942\]:\[Usaco2015 Feb\]Censoring][BZOJ3942_Usaco2015 Feb_Censoring]）

很显然是一道KMP水题，大体思路就是求T的nxt数组，将S依次入栈，跑KMP，在此就不做过多的赘述。

那么这时候出现了多个串，怎么办呢？

暴力hash时间复杂度O(n2)，显然不能接受。（虽说我有个队友直接卡常A掉了叭~）

显然这道题与BZOJ3942的区别在于这道题是多模式串匹配，而那道题是单模式串匹配，不难想到AC自动机。

在此不会AC自动机的大佬可以看我这篇博客：[AC自动机讲解+\[HDU2222\]Keywords Search（AC自动机）][AC_HDU2222_Keywords Search_AC]。

那么我们再结合BZOJ3942的思想，首先Trie树中end数组的意义定义为在当前点结束的串的长度是多少，然后匹配的时候开一个栈，边匹配边压栈，发现匹配到的当前点end\[p\]不为0（即为有串在当前点结束），则需要暴力将栈中后end\[p\]位弹出（即为将栈中的这个单词弹出）。需要注意的一点是，弹栈之后要将当前匹配的节点恢复到栈顶元素的位置，然后从下一个元素开始继续匹配。

--------------------

代码时刻：

#include<bits/stdc++.h>
    using namespace std;
    int cnt,sum,nxt[100001],trie[100001][30],end[100001],que[100001];
    char s[100001],str[100001];
    int ans[100001],ani[100001];
    int n;
    void insert(char *str)
    {
    	int len=strlen(str);
    	int p=1;
    	for(int k=0;k<len;k++)
    	{
    		int ch=str[k]-'a';
    		if(!trie[p][ch])
    			trie[p][ch]=++cnt;
    		p=trie[p][ch];
    	}
    	end[p]=len;//end数组记录在当前点结束的串的长度 
    }
    void _doudou()
    {
    	for(int i=0;i<26;i++)
    		trie[0][i]=1;
    	que[1]=1;
    	for(int head=1,tail=1;head<=tail;head++)
    		for(int i=0;i<26;i++)
    			if(!trie[que[head]][i])trie[que[head]][i]=trie[nxt[que[head]]][i];
    			else
    			{
    				que[++tail]=trie[que[head]][i];
    				nxt[trie[que[head]][i]]=trie[nxt[que[head]]][i];
    			}
    }
    void find(char *str)
    {
    	int len=strlen(str),p=1;
    	for(int i=0;i<len;i++)
    	{
    		int ch=str[i]-'a';
    		p=trie[p][ch];
    		ans[++sum]=p;
    		ani[sum]=i;//记录栈中每一个点在原串中的位置 
    		if(end[p])//发现有单词在这个点结束 
    		{
    			sum-=end[p];//暴力弹栈 
    			p=ans[sum];
    		}
    	}
    }
    int main()
    {
    	scanf("%s",str);
    	cnt=1;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%s",s);
    		insert(s);
    	}
    	_doudou();
    	find(str);
    	for(int i=1;i<=sum;i++)//输出 
    		cout<<str[ani[i]];
    	return 0;
    }

cpp

--------------------

下面是hash暴力O(n2)过掉这道题的队友，疯狂register卡常，想打正解的大佬就不要往下看啦哈哈

#include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<set>
    #include<map>
    #define ull unsigned long long 
    using namespace std;
    const int p=131;
    char s[100050];
    char s1[100050];
    ull h[2005];
    ull hstack[100050];
    ull base[100050];
    int istack[100050];
    int l[2005];
    int top,n,len;
    int main(){
    	scanf("%s",s+1);
    	len=strlen(s+1);
    	scanf("%d",&n);
    	base[0]=1;
    	for(register int i=1;i<=n;i++){
    		scanf("%s",s1+1);
    		l[i]=strlen(s1+1);
    		for(int j=1;j<=l[i];j++)
    			h[i]=h[i]*p+s1[j]-'a'+1;
    	}
    	for(register int i=1;i<=100050;i++)
    		base[i]=base[i-1]*p;
    	for(register int i=1;i<=len;i++){
    		istack[++top]=i;
    		hstack[top]=hstack[top-1]*p+s[i]-'a'+1;
    		for(register int j=1;j<=n;j++)
    			if(hstack[top]-hstack[top-l[j]]*base[l[j]]==h[j]){
    				top-=l[j];break;
    			}
    	}
    	for(register int i=1;i<=top;i++)
    		putchar(s[istack[i]]);
    	return 0;
    }

--------------------

rp++

转载于:https://www.cnblogs.com/wzc521/p/11025246.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=3940
[BZOJ3942_Usaco2015 Feb_Censoring]: https://www.lydsy.com/JudgeOnline/problem.php?id=3942
[AC_HDU2222_Keywords Search_AC]: https://www.cnblogs.com/wzc521/p/11021155.html