好久都没敲过KMP和AC自动机了。以前只会敲个kuangbin牌板子套题。现在重新写了自己的板子加深了印象。并且刷了一些题来增加自己的理解。
KMP网上教程很多,但我的建议还是先看AC自动机(Trie图)的构造后再去理解。板子的话大家大同小异。
而AC自动机的构造则是推荐王贇的。
前面的备用知识则是字典树。推荐董华星的。董聚聚不仅仅是介绍了字典树,包括一些常见的应用也有论述,介绍的挺详细的。
接下来就是刷题的部分了。
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
1 #include2 #include 3 #include 4 #include 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
然后是按照论文里面bfs的构造法写的:
1 #include2 #include 3 #include 4 #include 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