首页 > 代码库 > [USACO15FEB] Censoring

[USACO15FEB] Censoring

2024-10-04 18:52:02   227人阅读

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.

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.

Output

The string S after all deletions are complete. It is guaranteed that S will not become empty during the deletion process.

Sample Input

begintheescapexecutionatthebreakofdawn 
2 
escape 
execution

Sample Output

beginthatthebreakofdawn

damn it！以后没事别逞强写指针，除非空间限制卡得特别厉害

可以记录每个字母在ac自动机上的位置，用栈维护当前句子

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<queue>
 5 #include<iostream>
 6 using namespace std;
 7 char s[100010],t[100010];
 8 struct node{
 9     int cnt;
10     struct node *fail,*nxt[26];
11     node(){
12         cnt=0;
13         fail=NULL;
14         memset(nxt,0,sizeof(nxt));
15     }
16 }*h,*p,*q,*sign[100010],*vis[200010][30];
17 int n,top,stk[100010],len[100010];
18 void insert(int x){
19     p=h;
20     for(int i=0,i_end=strlen(t);i<i_end;++i){
21         if(p->nxt[t[i]-‘a‘]==NULL)p->nxt[t[i]-‘a‘]=new node;
22         p=p->nxt[t[i]-‘a‘];
23     }
24     p->cnt=strlen(t);
25 }
26 void Getf(){
27     queue<node*> q;
28     q.push(h);
29     while(!q.empty()){
30         node *now=q.front();q.pop();
31         for(int i=0;i<26;++i)if(now->nxt[i]!=NULL){
32             if(now==h)now->nxt[i]->fail=h;
33             else{
34                 for(p=now->fail;p!=NULL;p=p->fail)if(p->nxt[i]!=NULL){
35                     now->nxt[i]->fail=p->nxt[i];
36                     break;
37                 }
38                 if(p==NULL)now->nxt[i]->fail=h;
39             }
40             q.push(now->nxt[i]);
41         }
42     }
43 }
44 
45 node *F(node *now,int loc){
46     int x=s[loc]-‘a‘;
47     if(stk[top-1]>=0&&vis[stk[top-1]][x]!=NULL)return vis[stk[top-1]][x];
48     while(now->nxt[x]==NULL&&now!=h)now=now->fail;
49     now=now->nxt[x];
50     if(now==NULL)now=h;
51     if(stk[top-1]>=0)vis[stk[top-1]][x]=now;
52     return now;
53 }
54 void solve(){
55     sign[stk[0]=100005]=h;
56     for(int i=0,i_end=strlen(s);i<i_end;++i){
57         stk[++top]=i;
58         sign[i]=F(sign[stk[top-1]],i);
59         if(sign[i]->cnt)
60             top-=sign[i]->cnt;
61     }
62 }
63 int main(){
64     scanf("%s",s);
65     scanf("%d",&n);
66     h=new node;
67     for(int i=1;i<=n;++i)
68         scanf("%s",t),insert(i);
69     Getf();
70     solve();
71     for(int i=1;i<=top;++i)
72         printf("%c",s[stk[i]]);
73     return 0;
74 }

 

[USACO15FEB] Censoring


联系
我们