首页 > 代码库 > Bzoj3940 [Usaco2015 Feb]Censoring
Bzoj3940 [Usaco2015 Feb]Censoring
Submit: 391 Solved: 183
Description
Farmer John has purchased a subscription to Good Hooveskeeping magazine for his cows, so they have plenty
of material to read while waiting around in the barn during milking sessions. Unfortunately, the latest
issue contains a rather inappropriate article on how to cook the perfect steak, which FJ would rather his
cows not see (clearly, the magazine is in need of better editorial oversight).
FJ has taken all of the text from the magazine to create the string S of length at most 10^5 characters.
He has a list of censored words t_1 ... t_N that he wishes to delete from S. To do so Farmer John finds
the earliest occurrence of a censored word in S (having the earliest start index) and removes that instance
of the word from S. He then repeats the process again, deleting the earliest occurrence of a censored word
from S, repeating until there are no more occurrences of censored words in S. Note that the deletion of one
censored word might create a new occurrence of a censored word that didn‘t exist before.
Farmer John notes that the censored words have the property that no censored word appears as a substring of
another censored word. In particular this means the censored word with earliest index in S is uniquely
defined.Please help FJ determine the final contents of S after censoring is complete.
FJ把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过10^5的字符串S。他有一个包含n个单词的列表，列表里的n个单词
记为t_1...t_N。他希望从S中删除这些单词。
FJ每次在S中找到最早出现的列表中的单词(最早出现指该单词的开始位置最小)，然后从S中删除这个单词。他重复这个操作直到S中
没有列表里的单词为止。注意删除一个单词后可能会导致S中出现另一个列表中的单词
FJ注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在S中出现的开始位置是互不相同的
请帮助FJ完成这些操作并输出最后的S
Input
The first line will contain S. The second line will contain N, the number of censored words. The next N lines contain the strings t_1 ... t_N. Each string will contain lower-case alphabet characters (in the range a..z), and the combined lengths of all these strings will be at most 10^5.
第一行包含一个字符串S
第二行包含一个整数N
接下来的N行，每行包含一个字符串，第i行的字符串是t_i
Output
The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.
一行，输出操作后的S
Sample Input
begintheescapexecutionatthebreakofdawn
2
escape
execution
2
escape
execution
Sample Output
beginthatthebreakofdawn
HINT
Source
Gold
字符串 AC自动机
把待匹配的串建成AC自动机，记录每个串的长度。
用原串在AC自动机上转移，记录每一个位置所在的结点，并把该位置的字符压入栈中，如果在位置x匹配到一个串i，就回溯到x-len[i]位置的那个结点，同时弹对应层数的栈
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std; 10 const int mxn=200010; 11 int len[mxn]; 12 int st[mxn],top=0; 13 struct ACa{ 14 int t[mxn][26],fail[mxn],end[mxn]; 15 int pre[mxn],pos[mxn]; 16 int S,cnt; 17 void init(){S=cnt=1;return;} 18 void insert(char *s,int id){ 19 int now=S; 20 int len=strlen(s); 21 for(int i=0;i<len;i++){ 22 if(!t[now][s[i]-‘a‘])t[now][s[i]-‘a‘]=++cnt; 23 pre[t[now][s[i]-‘a‘]]=now; 24 now=t[now][s[i]-‘a‘]; 25 } 26 end[now]=id; 27 return; 28 } 29 void Build(){ 30 queue<int>q; 31 for(int i=0;i<26;i++){ 32 if(t[S][i]) {fail[t[S][i]]=S,q.push(t[S][i]);} 33 else t[S][i]=S; 34 } 35 while(!q.empty()){ 36 int u=q.front();q.pop(); 37 for(int i=0;i<26;i++){ 38 if(t[u][i]){ 39 fail[t[u][i]]=t[fail[u]][i]; 40 q.push(t[u][i]); 41 } 42 else { 43 t[u][i]=t[fail[u]][i]; 44 // pre[t[u][i]]=u; 45 // printf("pre of %d is %d\n",t[u][i],pre[t[u][i]]); 46 } 47 } 48 } 49 } 50 void debug(char *s){ 51 int now=S;int len=strlen(s); 52 for(int i=0;i<len;i++){ 53 now=t[now][s[i]-‘a‘]; 54 printf("%d ",now); 55 } 56 printf("fin\n"); 57 return; 58 } 59 void solve(char *s){ 60 int Len=strlen(s); 61 int now=S; 62 int i,j; 63 for(i=0;i<Len;i++){ 64 pos[i]=now; 65 st[++top]=i; 66 now=t[now][s[i]-‘a‘]; 67 // printf("now:%d end:%d\n",now,end[now]); 68 if(end[now]){ 69 int id=end[now]; 70 top-=len[id]-1; 71 now=pos[st[top]]; 72 top--; 73 /* for(j=1;j<len[id];j++){ 74 now=pre[now]; 75 top--; 76 } 77 top--;*/ 78 // printf("st:%d now:%d\n",st[top],now); 79 } 80 } 81 for(i=1;i<=top;i++){ 82 printf("%c",s[st[i]]); 83 } 84 printf("\n"); 85 return; 86 } 87 }ac; 88 char s[mxn]; 89 int n; 90 char c[mxn]; 91 int main(){ 92 int i,j; 93 scanf("%s",s); 94 scanf("%d",&n); 95 ac.init(); 96 for(i=1;i<=n;i++){ 97 scanf("%s",c); 98 // printf("%s ",c); 99 len[i]=strlen(c);100 // printf("len:%d\n",len[i]);101 ac.insert(c,i);102 }103 // scanf("%s",c);104 // ac.debug(c);105 ac.Build();106 ac.solve(s);107 return 0;108 }109
Bzoj3940 [Usaco2015 Feb]Censoring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。