hdu2222 Keywords Search
题意：每组数据中有n个子串，给出目标串，求出共有多少个子串在目标串中出现过，输出数量。
题解：妥妥的ac自动机（多模匹配算法），是个模板题。
ac自动机学习参考链接（大佬的图画的太棒了）：
https://blog.csdn.net/weixin_40317006/article/details/81327188
https://blog.csdn.net/creatorx/article/details/7110084
链表版
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<malloc.h> 5 using namespace std; 6 7 const int maxn=1e7+10; 8 9 struct node 10 { 11 node *next[26]; //下一个字母 12 node *fail; //失败指针 13 int sum; //几个单词结点 14 }; 15 16 node *root; 17 node *newnode; 18 int head,tail; 19 node *q[maxn]; 20 char pattern[maxn]; 21 char key[100]; 22 int cnt; 23 24 void insert(char *s) 25 { 26 node *p=root; 27 for(int i=0;s[i];i++){ 28 int x=s[i]-'a'; 29 if(p->next[x]==NULL){ 30 newnode=(struct node*)malloc(sizeof(struct node)); 31 for(int j=0;j<26;j++) newnode->next[j]=0; 32 newnode->sum=0; 33 newnode->fail=0; 34 p->next[x]=newnode; 35 } 36 p=p->next[x]; 37 } 38 p->sum++; 39 } 40 41 void build_fail() 42 { 43 head=0; 44 tail=1; 45 q[head]=root; 46 node *p;node *temp; 47 while(head<tail){ 48 temp=q[head++]; 49 for(int i=0;i<26;i++){ 50 if(temp->next[i]){ 51 if(temp==root){ 52 temp->next[i]->fail=root; 53 } 54 else{ 55 p=temp->fail; 56 while(p){ 57 if(p->next[i]){ 58 temp->next[i]->fail=p->next[i]; 59 break; 60 } 61 p=p->fail; 62 } 63 if(!p) temp->next[i]->fail=root; 64 } 65 q[tail++]=temp->next[i]; 66 } 67 } 68 } 69 } 70 71 void ac_chicken(char *ch) 72 { 73 node *p=root; 74 int len=strlen(ch); 75 for(int i=0;i<len;i++){ 76 int x=ch[i]-'a'; 77 while(!p->next[x]&&p!=root) p=p->fail; //找到这个字母 78 p=p->next[x]; //p到这个节点 79 if(!p) p=root; //没有的话就是根节点 80 node *temp=p; 81 while(temp!=root){ 82 if(temp->sum){ 83 cnt+=temp->sum; 84 temp->sum=0; 85 } 86 else break; 87 temp=temp->fail; 88 } 89 } 90 } 91 92 int main() 93 { 94 int t,n; 95 scanf("%d",&t); 96 while(t--){ 97 root=(struct node*)malloc(sizeof(struct node)); 98 for(int i=0;i<26;i++) root->next[i]=0; 99 root->fail=0; 100 root->sum=0; 101 cnt=0; 102 scanf("%d",&n); 103 for(int i=0;i<n;i++){ 104 scanf("%s",key); 105 insert(key); 106 } 107 build_fail(); 108 scanf("%s",pattern);
109 ac_chicken(pattern);
110 printf("%d\n",cnt); 111 } 112 return 0; 113 }
数组版（一定记得初始化！！不初始化会mle 鬼知道为什么-_-!!）
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<queue> 5 using namespace std; 6 7 const int maxn=1e6+10; 8 int n,cnt=1; 9 int tree[maxn][26],color[maxn],fail[maxn]; 10 char pattern[2*maxn]; 11 char key[100]; 12 queue<int> q; 13 14 void init() 15 { 16 memset(tree,0,sizeof(tree)); 17 memset(color,0,sizeof(color)); 18 memset(fail,0,sizeof(fail)); 19 memset(key,0,sizeof(key)); 20 memset(pattern,0,sizeof(pattern)); 21 cnt=1; 22 while(!q.empty()) q.pop(); 23 } 24 25 void insert(char *s) 26 { 27 int u=1,len=strlen(s); 28 for(int i=0;i<len;i++){ 29 int v=s[i]-'a'; 30 if(!tree[u][v]) tree[u][v]=++cnt; 31 u=tree[u][v]; 32 } 33 color[u]++; 34 } 35 36 void build_fail() 37 { 38 for(int i=0;i<26;i++) tree[0][i]=1; //一个非常重要的细节处理，我们加一个虚拟节点0，并将它的所有边都连到1，方便以后的运算 39 q.push(1); //将根压入队列 40 fail[1]=0; 41 while(!q.empty()){ 42 int u=q.front(); 43 q.pop(); 44 for(int i=0;i<26;i++){ //遍历所有儿子 45 if(!tree[u][i]){ //不存在该节点 46 tree[u][i]=tree[fail[u]][i]; 47 continue; 48 } 49 fail[tree[u][i]]=tree[fail[u]][i]; 50 q.push(tree[u][i]); //存在实节点才压入队列 51 } 52 } 53 } 54 55 int ac_chicken(char *ch) 56 { 57 int u=1,ans=0,len=strlen(ch); 58 for(int i=0;i<len;i++){ 59 int v=ch[i]-'a'; 60 int k=tree[u][v]; 61 while(k>1&&color[k]){ 62 ans+=color[k]; 63 color[k]=0; 64 k=fail[k]; 65 } 66 u=tree[u][v]; 67 } 68 return ans; 69 } 70 71 int main() 72 { 73 int t; 74 scanf("%d",&t); 75 while(t--){ 76 init(); 77 scanf("%d",&n); 78 for(int i=0;i<n;i++){ 79 scanf("%s",pattern); 80 insert(pattern); 81 } 82 build_fail(); 83 scanf("%s",key); 84 printf("%d\n",ac_chicken(key)); 85 } 86 return 0; 87 }
查看12道真题和解析
得物app公司福利 402人发布
