ZOJ 3228 AC自动机 重叠和不重叠

点击打开链接

题意：给定模式串，问下面的串最多出现多少次，0代表可以重叠，1代表不能重叠

思路：正常的0可以用模版直接实现，1的可以再写一个查询的，不能重叠，尽量先取前面，结果是最优的，所以我就记录这个串上一次出现的位置，然后在走了串这么长的长度才可以在+1.

[html] view plain copy

1. #include <stdio.h>  
2. #include <string.h>  
3. #include <memory.h>  
4. struct node{  
5.     node *fail;  
6.     node *next[26];  
7.     int id;  
8.     node(){  
9.         fail=NULL;  
10.         id=0;  
11.         memset(next,NULL,sizeof(next));  
12.     }  
13. }*q[100000],*root;  
14. char str1[100003][7],str2[100003];  
15. int A[100003],cnt[100003][2],pos[100003],Len[100003],n;  
16. void insert_Trie(char *str,int num1){  
17.     node *p=root;  
18.     int i=0,id;  
19.     while(str[i]){  
20.         id=str[i]-'a';  
21.         if(p->next[id]==NULL) p->next[id]=new node();  
22.         p=p->next[id];i++;  
23.     }  
24.     p->id=num1;  
25. }  
26. int search_1(char *str){  
27.     node *p=root;  
28.     int m,i=0;  
29.     while(str[i]){  
30.         m=str[i]-'a';  
31.         if(p->next[m]==NULL) return -1;  
32.         p=p->next[m];  
33.         i++;  
34.     }  
35.     return p->id;  
36. }  
37. void build_ac(){  
38.     int head=0,tail=0;  
39.     root->fail=NULL;  
40.     q[head++]=root;  
41.     node *p,*temp;  
42.     while(head!=tail){  
43.         temp=q[tail++];  
44.         tail%=100000;  
45.         for(int i=0;i<26;i++){  
46.             if(temp->next[i]!=NULL){  
47.                 if(temp==root) temp->next[i]->fail=root;  
48.                 else{  
49.                     p=temp->fail;  
50.                     while(p!=NULL){  
51.                         if(p->next[i]!=NULL){  
52.                             temp->next[i]->fail=p->next[i];  
53.                             break;  
54.                         }  
55.                         p=p->fail;  
56.                     }  
57.                     if(p==NULL) temp->next[i]->fail=root;  
58.                 }  
59.                 q[head++]=temp->next[i];  
60.                 head%=100000;  
61.             }  
62.         }  
63.     }  
64. }  
65. void query(){  
66.     int i=0;  
67.     node *p=root,*temp;  
68.     while(str2[i]){  
69.         int id=str2[i]-'a';  
70.         while(p->next[id]==NULL&&p!=root) p=p->fail;  
71.         p=p->next[id];  
72.         p=(p==NULL)?root:p;  
73.         temp=p;  
74.         while(temp!=root){  
75.             if(temp->id){  
76.                 cnt[temp->id][0]++;  
77.             }  
78.             temp=temp->fail;  
79.         }  
80.         i++;  
81.     }  
82. }  
83. void query1(){  
84.     int i=0;  
85.     node *p=root,*temp;  
86.     while(str2[i]){  
87.         int id=str2[i]-'a';  
88.         while(p->next[id]==NULL&&p!=root) p=p->fail;  
89.         p=p->next[id];  
90.         p=(p==NULL)?root:p;  
91.         temp=p;  
92.         while(temp!=root){  
93.             if(temp->id&&i-pos[temp->id]>=Len[temp->id]){  
94.                 pos[temp->id]=i;  
95.                 cnt[temp->id][1]++;  
96.             }  
97.             temp=temp->fail;  
98.         }  
99.         i++;  
100.     }  
101. }  
102. int query_num(char *str,int aa){  
103.     int i=0;  
104.     node *p=root;  
105.     while(str[i]){  
106.         int id=str[i]-'a';  
107.         p=p->next[id];  
108.         i++;  
109.     }  
110.     return cnt[p->id][aa];  
111. }  
112. void del(node *p){  
113.      if(p==NULL)return ;  
114.      for(int i=0;i<26;i++)del(p->next[i]);  
115.      delete p;  
116. }  
117. int main(){  
118.     int t=1;  
119.     while(scanf("%s",str2)!=-1){  
120.         scanf("%d",&n);  
121.         root=new node();  
122.         memset(cnt,0,sizeof(cnt));  
123.         memset(pos,-1,sizeof(pos));  
124.         for(int i=1;i<=n;i++){  
125.             scanf("%d%s",&A[i],str1[i]);  
126.             Len[i]=strlen(str1[i]);  
127.             insert_Trie(str1[i],i);  
128.         }  
129.         build_ac();  
130.         query();  
131.         query1();  
132.         printf("Case %d\n",t++);  
133.         for(int i=1;i<=n;i++){  
134.             int ttt=query_num(str1[i],A[i]);  
135.             printf("%d\n",ttt);  
136.         }  
137.         printf("\n");  
138.         del(root);  
139.     }  
140.     return 0;  
141. }