计算next数组的方法是对于长度为n的匹配串，从0到n-1位依次求出前缀后缀最大匹配长度。
下面的写法是仅仅检测有没有匹配然后返回第一个匹配位置，而不是返回所有匹配位置。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N=100; char str[100],ptr[100];//父串str和子串ptr int next[100]; string ans; void getnext()//获取next数组 { int i,n,k; n=strlen(ptr); memset(next,0,sizeof(next)); k=0; for(i=1;i<n;i++) { while(k>0 && ptr[k]!=ptr[i]) k=next[k]; if(ptr[k]==ptr[i]) k++; next[i+1]=k; //next表示的是匹配长度 } } int kmp(char *a,char *b)//匹配ab两串，a为父串 { int i=0,j=0; int len1=strlen(a); int len2=strlen(b); getnext(); while(i<len1&&j<len2) { if(j==0||a[i]==b[j]) { i++;j++; } else j=next[j+1];//到前一个匹配点 } if(j>=len2) return i-j; else return -1; } int main(){ while( scanf( "%s%s", str, ptr ) ) { int ans = kmp(str,ptr); if(ans>=0) printf( "%d\n", kmp( str,ptr )); else printf("Not find\n"); } return 0; }
字典树 - 一对多
其实Trie也叫做前缀树。
基本性质
1，根节点不包含字符，除根节点意外每个节点只包含一个字符。
2，从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3，每个节点的所有子节点包含的字符串不相同。
优点：
可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。
跟哈希表比较：
1，最坏情况时间复杂度比hash表好
2，没有冲突，除非一个key对应多个值（除key外的其他信息）
3，自带排序功能（类似Radix Sort），先序遍历Trie可以得到排序。
可以用来得到字符串最长公共前缀（转成LCA问题/最近公共祖先问题，用Tarjan算法，dfs某个节点的子树，子树之间的相互的最近公共祖先就是这个节点）
#include<queue> #include<set> #include<cstdio> #include <iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; /* trie字典树 */ struct tnode{ int sum;//用来判断是否是终点的 tnode* next[26]; tnode(){ for(int i =0;i<26;i++) next[i]=NULL; sum=0; } }; tnode *root; tnode* newnode(){ tnode *p = new tnode; for(int i =0;i<26;i++) p->next[i]=NULL; p->sum=0; return p; } //插入函数 void Insert(char *s) { tnode *p = root; for(int i = 0 ; s[i] ; i++) { int x = s[i] - ‘a‘; if(p->next[x]==NULL) { tnode *nn=newnode(); for(int j=0;j<26;j++) nn->next[j] = NULL; nn->sum = 0; p->next[x]=nn; } p = p->next[x]; } p->sum++;//这个单词终止啦 } //匹配函数 bool Compare(char *ch) { tnode *p = root; int len = strlen(ch); for(int i = 0; i < len; i++) { int x = ch[i] - ‘a‘; p = p->next[x]; if(p==NULL) return false; if(i==len-1 && p->sum>0 ){ return true; } } return false; } void DELETE(tnode * &top){ if(top==NULL) return; for(int i =0;i<26;i++) DELETE(top->next[i]); delete top; } int main() { int n,m; cin>>n; char s[20]; root = newnode(); for(int i =0;i<n;i++){ scanf("%s",s); Insert(s); } cin>>m; for(int i =0;i<m;i++){ scanf("%s",s); if(Compare(s)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } DELETE(root);//看见指针就要想到释放,然而这东西会花时间，所以网上很多人写ACM题就不delete了，我很看不惯这一点。 return 0; }
AC自动机
#include<queue> #include<set> #include<cstdio> #include <iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; /* ac自动机 */ struct acnode{ int sum; acnode* next[26]; acnode* fail; acnode(){ for(int i =0;i<26;i++) next[i]=NULL; fail= NULL; sum=0; } }; acnode *root; int cnt; acnode* newnode(){ acnode *p = new acnode; for(int i =0;i<26;i++) p->next[i]=NULL; p->fail = NULL; p->sum=0; return p; } //插入函数 void Insert(char *s) { acnode *p = root; for(int i = 0; s[i]; i++) { int x = s[i] - ‘a‘; if(p->next[x]==NULL) { acnode *nn=newnode(); for(int j=0;j<26;j++) nn->next[j] = NULL; nn->sum = 0; nn->fail = NULL; p->next[x]=nn; } p = p->next[x]; } p->sum++; } //获取fail指针，在插入结束之后使用 void getfail(){ queue<acnode*> q; for(int i = 0 ; i < 26 ; i ++ ) { if(root->next[i]!=NULL){ root->next[i]->fail = root; q.push(root->next[i]); } } while(!q.empty()){ acnode* tem = q.front(); q.pop(); for(int i = 0;i<26;i++){ if(tem->next[i]!=NULL) { acnode *p; if(tem == root){ tem->next[i]->fail = root; } else { p = tem->fail; while(p!=NULL){ if(p->next[i]!=NULL){ tem->next[i]->fail = p->next[i]; break; } p=p->fail; } if(p==NULL) tem->next[i]->fail = root; } q.push(tem->next[i]); } } } } //匹配函数 void ac_automation(char *ch) { acnode *p = root; int len = strlen(ch); for(int i = 0; i < len; i++) { int x = ch[i] - ‘a‘; while(p->next[x]==NULL && p != root)//没匹配到，那么就找fail指针。 p = p->fail; p = p->next[x]; if(!p) p = root; acnode *temp = p; while(temp != root) { if(temp->sum >= 0) /* 在这里已经匹配成功了，执行想执行的操作即可，怎么改看题目需求+ */ { cnt += temp->sum; temp->sum = -1; } else break; temp = temp->fail; } } } int main() { cnt = 0; int n; cin>>n; char c[101]; root = newnode(); for(int i = 0 ;i < n;i++){ scanf("%s",c); Insert(c); } getfail(); int m ; cin>> m; for(int i = 0;i<m;i++){ scanf("%s",c); ac_automation(c); } cout<<cnt<<endl; return 0; }
原文：https://www.cnblogs.com/Yinku/p/10453621.html