Censoring【自动AC机】【水题毁我青春】【20190614】

这题简直比注水猪肉还水QAQ。

以前做过KMP的Censoring单串匹配，果断选择自动AC机w

对短串建自动AC机

长串去机子里匹配

用个栈边匹配边弹出

记得弹出一个串后把匹配点指向栈顶就ojbk

（话说自动AC机也不能自动AC QAQ）

 1 #include<cmath>
 2 #include<queue>
 3 #include<cstdio>
 4 #define Zs 13331
 5 #include<cstring>
 6 #include<iostream>
 7 #define QAQ 100100
 8 #include<algorithm>
 9 #define ull unsigned long long
10 using namespace std;
11 struct node{
12     int c;
13     int num;
14     node *f;
15     node *ch[26];
16     node(){
17         c=0,f=NULL;num=0;
18         memset(ch,NULL,sizeof ch);
19     }
20 }*last[QAQ];
21 int n;
22 char s[2222][QAQ];
23 char stack[QAQ];int top=0;
24 node *root=new node();
25 inline void insert(int id){
26     node *p=root;int i=1,index;
27     while(s[id][i]){
28         index=s[id][i]-'a';
29         if(p->ch[index]==NULL)p->ch[index]=new node();
30         p=p->ch[index];
31         ++i;
32     }
33     p->num=strlen(s[id]+1);
34 }
35 void GetFail(){
36     queue<node*>qwq;
37     for(int i=0;i<26;i++){
38         if(root->ch[i]!=NULL)
39             root->ch[i]->f=root,
40             qwq.push(root->ch[i]);
41         else root->ch[i]=root;
42     }
43     while(!qwq.empty()){
44         node *now=qwq.front();qwq.pop();
45         for(int i=0;i<26;i++){
46             if(now->ch[i]!=NULL)
47                 now->ch[i]->f=now->f->ch[i],
48                 qwq.push(now->ch[i]);
49             else now->ch[i]=now->f->ch[i];
50         }
51     }
52 }
53 void query(char *s){
54     node *now=root;int i=1;
55     while(s[i]){
56         stack[++top]=s[i];
57         if(now==NULL)now=root;last[top]=now;
58         now=now->ch[s[i]-'a'];
59         for(node *j=now;j!=NULL&&j!=root;j=j->f){
60             int out=j->num;
61             if(j->f!=NULL&&!j->f->num)j->f=j->f->f;
62             if(!out)continue;
63             top-=out;
64             now=last[top+1];
65             break;
66         }
67         ++i;
68     }
69 }
70 void puts_out(){
71     for(int i=1;i<=top;i++){
72         printf("%c",stack[i]);
73     }
74 }
75 int main(){
76 //    freopen("cen .in","r",stdin);
77 //    freopen("cen.out","w",stdout);
78     scanf("%s",s[0]+1);
79     scanf("%d",&n);
80     for(int i=1;i<=n;i++){
81         scanf("%s",s[i]+1);
82         insert(i);
83     }
84     GetFail();
85     query(s[0]);
86     puts_out();
87 }

丑比代码QAQ

哦还有，这个啥玩意儿Trie图挺闹心的，还得优化

留坑待填QwQ （waiting......）