 ac自动机
 1 #include<iostream>
2#include<cstdio>
3#include<cstring>
4using namespace std;
5const int KIND=26,MAXM=30;
6struct node
7 {
8 node *fail; //关键
9 node *next[KIND];
10 int count;
11 node()
12  {
13 fail=NULL;
14 count=0;
15 memset(next,0,sizeof(next));
16 }
17 }*q[500001];
18char keyword[51];
19char str1[1000001];
20int head,tail;
21void insert(node *root,char *s)
22{
23 node *p=root;
24 for(int i=0;s[i];i++)
25 {
26 int x=s[i]-'a';
27 if(p->next[x]==NULL)
28 p->next[x]=new node;
29 p=p->next[x];
30 }
31 p->count++;
32}
33void build_ac_automation(node *root) //这个只要是int构造fail函数，可以画图很好理解的
34{
35 int i;
36 root->fail=NULL;
37 q[head++]=root;
38 while(head!=tail)
39 {
40 node *temp=q[tail++];
41 node *p=NULL;
42 for(int i=0;i<26;i++)
43 {
44 if(temp->next[i]!=NULL)
45 {
46 if(temp==root)
47 {
48 temp->next[i]->fail=root;
49 }
50 else
51 {
52 p=temp->fail;
53 while(p!=NULL)
54 {
55 if(p->next[i]!=NULL)
56 {
57 temp->next[i]->fail=p->next[i];
58 break;
59 }
60 p=p->fail;
61 }
62 if(p==NULL) temp->next[i]->fail=root;
63 }//end of else
64 q[head++]=temp->next[i];
65 }
66 }//end of for
67
68 }//end of while
69
70}
71int query(node *root,char *str)
72{
73 int i=0,cnt=0,index,len=strlen(str);
74 node *p=root;
75 while(str[i])
76 {
77 index=str[i]-'a';
78 while(p->next[index]==NULL&&p!=root) p=p->fail;
79 p=p->next[index];
80 p=(p==NULL?root:p);
81 node *temp=p;
82 while(temp!=root&&temp->count!=-1)
83 {
84 cnt+=temp->count;
85 temp->count=-1;
86 temp=temp->fail;
87 }
88 i++;
89 }
90 return cnt;
91}
92int main()
93{
94 int nCase;
95 //cin>>nCase;
96 scanf("%d",&nCase);
97 // getchar();
98 while(nCase--)
99 {
100 node *root=new node();
101 head=tail=0;
102 int n;
103 // cin>>n;
104 scanf("%d",&n);
105 getchar();
106 for(int i=0;i<n;i++)
107 {
108 //cin>>keyword;
109 gets(keyword);
110 insert(root,keyword);
111 }
112 build_ac_automation(root);
113 g有不知道为什么取这个名字啊，，搞的好像很高深莫测似的 ets(str1);
114 // cin>
1/**//*
2 字典树
3 动态实现和静态实现
4*/
5//#define DONGTAI_TREE
6#define JINGTAI_TREE
7#ifdef DONGTAI_TREE
8#include<iostream>
9using namespace std;
10const int KIND=26,MAXM=30;
11struct node
12{
13 char *s;
14 int prefix; //匹配前缀
15 bool isword;
16 node *next[KIND];
17 node()
18 {
19 s=NULL;
20 prefix=0;
21 isword=false;
22 memset(next,0,sizeof(next));
23 }
24}*root;
25void insert(node *root,char *s)
26{
27 node *p=root;
28 for(int i=0;s[i];i++)
29 {
30 int x=s[i]-'a';
31 p->s=s+i;
32 if(p->next[x]==NULL)
33 p->next[x]=new node;
34 p=p->next[x];
35 p->prefix++;
36 }
37 p->isword=true;
38}
39bool search(node *root,char *s) //查询该字典树是否包含该字母
40{
41 node *p=root;
42 for(int i=0;s[i];i++)
43 {
44 int x=s[i]-'a';
45 if(p->next[x]==NULL)
46 return false;
47 p=p->next[x];
48 }
49 return p->isword;
50}
51int countprefix(node *root,char *s) //统计该字符总共出现了多少次，在字典树当中
52{
53 node *p=root;
54 for(int i=0;s[i];i++)
55 {
56 int x=s[i]-'a';
57 if(p->next[x]==NULL)
58 return 0;
59 p=p->next[x];
60 }
61 return p->prefix;
62}
63bool del(node *root,char *s)
64{
65 node *p=root;
66 for(int i=0;s[i];i++)
67 {
68 int x=s[i]-'a';
69 if(p->next[x]==NULL)
70 return false;
71 p=p->next[x];
72 }
73 if(p->isword)
74 p->isword=false;
75 else
76 return false;
77 return true;
78}
79int main()
80{
81 cout<<"----动态建立----"<<endl;
82 char str[MAXM],str2[MAXM];
83 root=new node;
84 while(gets(str))
85 {
86 if(strcmp(str,"end")==0)
87 break;
88 // assert(strcmp(str,"end"));
89 insert(root,str);
90 }
91 while(gets(str2))
92 {
93 cout<<"该字符总共出现了:"<<countprefix(root,str2)<<endl;
94 }
95 system("pause");
96}
97#endif
98//#ifdef DONGTAI_TREE
99//#undef DONGTAI_TREE
100
101//#ifndef JINGTAI_TREE
102//#define JINGTAI_TREE
103#ifdef JINGTAI_TREE
104#include <iostream>
105using namespace std;
106const int MAXN = 100010,MAXM = 30,KIND = 26;
107int m;
108struct node
109{
110 char* s;
111 int prefix;
112 bool isword;
113 node* next[KIND];
114 void init()
115 {
116 s = NULL;
117 prefix = 0;
118 isword = false;
119 memset(next,0,sizeof(next));
120 }
121}a[MAXN*MAXM],*root;//根
122void insert(node *root,char *s)
123{
124 node *p = root;
125 for (int i = 0;s[i];i++)
126 {
127 int x = s[i] - 'a';
128 p->s = s+i;
129 if (p->next[x] == NULL)
130 {
131 a[m].init();
132 p->next[x] = &a[m++];
133 }
134 p = p->next[x];
135 p->prefix++;
136 }
137 p->isword = true;
138}
139bool del(node *root,char *s)
140{
141 node *p = root;
142 for (int i = 0;s[i];i++)
143 {
144 int x = s[i] - 'a';
145 if (p->next[x] == NULL)
146 return false;
147 p = p->next[x];
148 }
149 if (p->isword)
150 p->isword = false;
151 else
152 return false;
153 return true;
154}
155bool search(node *root,char* s)
156{
157 node* p = root;
158 for (int i = 0;s[i];i++)
159 {
160 int x = s[i]-'a';
161 if (p->next[x] == NULL)
162 return false;
163 p = p->next[x];
164 }
165 return p->isword;
166}
167int count(node *root,char *s)
168{
169 node *p = root;
170 for (int i = 0;s[i];i++)
171 {
172 int x = s[i] - 'a';
173 if (p->next[x] == NULL)
174 return 0;
175 p = p->next[x];
176 }
177 return p->prefix;
178}
179int main()
180{
181 cout<<"----静态建立----"<<endl;
182 m = 0;
183 a[m].init();
184 root = &a[m++];
185 char s[MAXM];
186 while (gets(s))
187 {
188 if (strcmp(s,"") == 0)
189 break;
190 insert(root,s);
191 }
192 while (gets(s))
193 printf("%d\n",count(root,s));
194}
195#endif
196 >str;
115 //cout<<query(root,str)<<endl;
116 printf("%d\n",query(root,str1));
117 }
118 system("pause");
119}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 28 | 29 | 30 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 | | 12 | 13 | 14 | 15 | 16 | 17 | 18 | | 19 | 20 | 21 | 22 | 23 | 24 | 25 | | 26 | 27 | 28 | 29 | 30 | 31 | 1 | | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|
常用链接
留言簿
随笔分类
随笔档案
文章分类
文章档案
友情链接
搜索
最新评论
阅读排行榜
评论排行榜
|
|