好久都没敲过KMP和AC自动机了。以前只会敲个kuangbin牌板子套题。现在重新写了自己的板子加深了印象。并且刷了一些题来增加自己的理解。
KMP网上教程很多,但我的建议还是先看AC自动机(Trie图)的构造后再去理解。板子的话大家大同小异。
而AC自动机的构造则是推荐王贇的《Trie图的构建、活用与改进》。
前面的备用知识则是字典树。推荐董华星的《浅析字母树在信息学竞赛中的应用》。董聚聚不仅仅是介绍了字典树,包括一些常见的应用也有论述,介绍的挺详细的。
接下来就是刷题的部分了。
hdu 5880
Family View
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2660 Accepted Submission(s): 577
Take an MMORPG game as an example, given a sentence T, and a list of forbidden words {P}, your job is to use '*' to subsititute all the characters, which is a part of the substring matched with at least one forbidden word in the list (case-insensitive).
For example, T is: "I love Beijing's *, the sun rises over *. Our great leader Chairman Mao, he leades us marching on."
And {P} is: {"*", "eat"}
The result should be: "I love Beijing's *********, the sun rises over *********. Our gr*** leader Chairman Mao, he leades us marching on."
The first line contains an integer n , represneting the size of the forbidden words list P . Each line of the next n lines contains a forbidden words Pi (1≤|Pi|≤1000000,∑|Pi|≤1000000) where Pi only contains lowercase letters.
The last line contains a string T (|T|≤1000000) .
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #define clr(x) memset(x,0,sizeof(x)) 6 #define clr_1(x) memset(x,-1,sizeof(x)) 7 #define INF 0x3f3f3f3f 8 #define mod 1000000007 9 #define LL long long 10 #define next nexted 11 using namespace std; 12 const int N=1e6+100; 13 const int type=26; 14 struct node 15 { 16 int pre; 17 int dep; 18 int tag; 19 int next[type]; 20 }trie[N]; 21 int tot; 22 int pos[N]; 23 int newnode() 24 { 25 trie[++tot]=(node){}; 26 return tot; 27 } 28 void add(int root,char *s) 29 { 30 int len=strlen(s); 31 int now=root; 32 int p; 33 for(int i=0;i<len;i++) 34 { 35 p=s[i]-'a'; 36 if(!trie[now].next[p]) 37 { 38 trie[now].next[p]=newnode(); 39 } 40 now=trie[now].next[p]; 41 trie[now].dep=i+1; 42 } 43 trie[now].tag=now; 44 } 45 void init() 46 { 47 tot=0; 48 trie[0]=(node){}; 49 clr(pos); 50 return ; 51 } 52 void getfail() 53 { 54 queue<int> que; 55 int now,nowto,j; 56 for(int i=0;i<type;i++) 57 if(trie[0].next[i]) 58 que.push(trie[0].next[i]); 59 while(!que.empty()) 60 { 61 now=que.front(); 62 que.pop(); 63 for(int i=0;i<type;i++) 64 { 65 nowto=trie[now].next[i]; 66 if(nowto) 67 { 68 que.push(nowto); 69 j=trie[now].pre; 70 while(j && !trie[j].next[i]) 71 j=trie[j].pre; 72 trie[nowto].pre=trie[j].next[i]; 73 if(trie[trie[j].next[i]].tag && !trie[nowto].tag) 74 trie[nowto].tag=trie[trie[j].next[i]].tag; 75 } 76 } 77 } 78 return ; 79 } 80 void acm(char *s) 81 { 82 int j=0,p,tmp; 83 int len=strlen(s); 84 for(int i=0;i<len;i++) 85 if((s[i]>='a' && s[i]<='z')||(s[i]>='A' && s[i]<='Z')) 86 { 87 p=(s[i]>='a' && s[i]<='z')?s[i]-'a':s[i]-'A'; 88 while(j && !trie[j].next[p]) 89 { 90 j=trie[j].pre; 91 } 92 j=trie[j].next[p]; 93 if(trie[j].tag) 94 { 95 pos[i+1]--; 96 pos[i-trie[trie[j].tag].dep+1]++; 97 } 98 } 99 else 100 { 101 j=0; 102 continue; 103 } 104 j=0; 105 for(int i=0;i<len;i++) 106 { 107 j+=pos[i]; 108 if(j>0) 109 s[i]='*'; 110 } 111 return ; 112 } 113 int T,n,m; 114 char s[N]; 115 int main() 116 { 117 scanf("%d",&T); 118 while(T--) 119 { 120 init(); 121 scanf("%d",&n); 122 gets(s); 123 for(int i=1;i<=n;i++) 124 { 125 gets(s); 126 add(0,s); 127 } 128 getfail(); 129 gets(s); 130 acm(s); 131 printf("%s\n",s); 132 } 133 return 0; 134 }
然后是按照论文里面bfs的构造法写的:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 #define clr(x) memset(x,0,sizeof(x)) 6 #define clr_1(x) memset(x,-1,sizeof(x)) 7 #define INF 0x3f3f3f3f 8 #define mod 1000000007 9 #define LL long long 10 #define next nexted 11 using namespace std; 12 const int N=1e6+100; 13 const int type=26; 14 struct node 15 { 16 int pre; 17 int dep; 18 int tag; 19 int next[type]; 20 }trie[N]; 21 int tot; 22 int pos[N]; 23 int newnode() 24 { 25 trie[++tot]=(node){}; 26 return tot; 27 } 28 void add(int root,char *s) 29 { 30 int len=strlen(s); 31 int now=root; 32 int p; 33 for(int i=0;i<len;i++) 34 { 35 p=s[i]-'a'; 36 if(!trie[now].next[p]) 37 trie[now].next[p]=newnode(); 38 now=trie[now].next[p]; 39 trie[now].dep=i+1; 40 } 41 trie[now].tag=now; 42 } 43 void init() 44 { 45 tot=0; 46 trie[0]=(node){}; 47 clr(pos); 48 return ; 49 } 50 void build() 51 { 52 queue<int> que; 53 int now,nowto; 54 for(int i=0;i<type;i++) 55 if(trie[0].next[i]) 56 que.push(trie[0].next[i]); 57 while(!que.empty()) 58 { 59 now=que.front(); 60 que.pop(); 61 for(int i=0;i<type;i++) 62 { 63 nowto=trie[now].next[i]; 64 if(nowto) 65 { 66 que.push(nowto); 67 trie[nowto].pre=trie[trie[now].pre].next[i]; 68 if(trie[trie[nowto].pre].tag && !trie[nowto].tag) 69 trie[nowto].tag=trie[trie[nowto].pre].tag; 70 } 71 else 72 trie[now].next[i]=trie[trie[now].pre].next[i]; 73 } 74 } 75 return ; 76 } 77 void acm(char *s) 78 { 79 int now=0,p,tmp; 80 int len=strlen(s); 81 for(int i=0;i<len;i++) 82 if((s[i]>='a' && s[i]<='z')||(s[i]>='A' && s[i]<='Z')) 83 { 84 p=(s[i]>='a' && s[i]<='z')?s[i]-'a':s[i]-'A'; 85 now=trie[now].next[p]; 86 if(trie[now].tag) 87 { 88 pos[i+1]--; 89 pos[i-trie[trie[now].tag].dep+1]++; 90 } 91 } 92 else 93 { 94 now=0; 95 continue; 96 } 97 now=0; 98 for(int i=0;i<len;i++) 99 { 100 now+=pos[i]; 101 if(now>0) 102 s[i]='*'; 103 } 104 return ; 105 } 106 int T,n,m; 107 char s[N]; 108 int main() 109 { 110 scanf("%d",&T); 111 while(T--) 112 { 113 init(); 114 scanf("%d",&n); 115 gets(s); 116 for(int i=1;i<=n;i++) 117 { 118 gets(s); 119 add(0,s); 120 } 121 build(); 122 gets(s); 123 acm(s); 124 printf("%s\n",s); 125 } 126 return 0; 127 }
tips: 虽然题目给的模式串总长不超过106然而实际不超过5*105,trie数组可以不开那么大,或者你改成孩子兄弟链法也是可行的。因为你一旦开那么大就会MLE。
然而你们看我代码为什么就不超呢。。我也是弄了好久才明白。。原来杭电他测内存占用的映射机制,只有当你使用过这个变量才会计算他是占用内存的。。所以你不写memset()或者对trie数组写指针引用的话,就不会超内存。
bzoj 2938
2938: [Poi2000]病毒
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1300 Solved: 647
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
01
11
00000
Sample Output
论文题。把Trie图构造出来以后dfs跑他的安全图看有没有环就行。有环说明能在这个环里一直跑,构造的字符串能无限长,无环则必定在某个位置到达词尾节点结束。
1 #include<bits/stdc++.h> 2 #define clr(x) memset(x,0,sizeof(x)) 3 #define clr_1(x) memset(x,-1,sizeof(x)) 4 #define INF 0x3f3f3f3f 5 #define mod 1000000007 6 #define LL long long 7 #define next nexted 8 using namespace std; 9 const int N=3e4+10; 10 const int type=2; 11 char s[N]; 12 int n,m,T,tot; 13 int vis[N]; 14 struct node 15 { 16 int pre,tag,dep,next[2]; 17 }trie[N]; 18 void init() 19 { 20 tot=0; 21 clr(trie); 22 clr(vis); 23 return ; 24 } 25 int makenode() 26 { 27 return ++tot; 28 } 29 void add(int root,char *s) 30 { 31 int now=root,len=strlen(s),p; 32 for(int i=0;i<len;i++) 33 { 34 p=s[i]-'0'; 35 if(!trie[now].next[p]) trie[now].next[p]=makenode(); 36 now=trie[now].next[p]; 37 trie[now].dep=i+1; 38 } 39 trie[now].tag=now; 40 return ; 41 } 42 void build() 43 { 44 queue<int> que; 45 for(int i=0;i<type;i++) 46 if(trie[0].next[i]) que.push(trie[0].next[i]); 47 int now,nowto; 48 while(!que.empty()) 49 { 50 now=que.front(); 51 que.pop(); 52 for(int i=0;i<type;i++) 53 { 54 nowto=trie[now].next[i]; 55 if(nowto) 56 { 57 trie[nowto].pre=trie[trie[now].pre].next[i]; 58 que.push(nowto); 59 if(trie[trie[nowto].pre].tag && !trie[nowto].tag) 60 trie[nowto].tag=trie[trie[nowto].pre].tag; 61 } 62 else 63 trie[now].next[i]=trie[trie[now].pre].next[i]; 64 } 65 } 66 return ; 67 } 68 bool dfs(int now) 69 { 70 if(trie[now].tag || vis[now]==2) return 0; 71 if(vis[now]==1) return 1; 72 vis[now]=1; 73 bool inf=0; 74 for(int i=0;i<type;i++) 75 inf=(inf || dfs(trie[now].next[i])); 76 vis[now]=2; 77 return inf; 78 } 79 int main() 80 { 81 scanf("%d",&n); 82 init(); 83 for(int i=1;i<=n;i++) 84 { 85 scanf("%s",s); 86 add(0,s); 87 } 88 build(); 89 if(dfs(0)) 90 printf("TAK\n"); 91 else 92 printf("NIE\n"); 93 return 0; 94 }