HDU 5384 字典树、AC自动机

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5384

用字典树、AC自动机两种做法都可以做

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<string>
 4 #include<iostream>
 5 using namespace std;
 6 struct node{
 7     int cnt;
 8     node *next[26];
 9     node(){
10         cnt = 0;
11         for(int i = 0;i<26;i++)
12             next[i] = NULL;
13     }
14 }*a;
15 void insert(char *str){
16     node *head = a;
17     int len = strlen(str);
18     for(int i = 0;i<len;i++){
19         int temp = str[i]-'a';
20         if(head->next[temp] == NULL)
21             head->next[temp] = new node;
22         head = head->next[temp];
23     }
24     head->cnt++;
25 }
26 int find(string t){
27     node *head = a;
28     int ans = 0;
29     for(int i = 0;i<t.size();i++){
30         if(head->next[t[i]-'a']){
31             if(head->next[t[i]-'a']->cnt){
32                 ans++;
33                 
34             }
35         }else
36             break;
37         head = head->next[t[i]-'a'];
38     }
39     head->cnt--;
40     return ans;
41 }
42 int main(){
43     int t;
44     scanf("%d",&t);
45     while(t--){
46         a = new node;
47         int n;
48         scanf("%d",&n);
49         char s[55];
50         for(int i = 0;i<n;i++){
51             scanf(" %s",s);
52             insert(s);
53         }
54         string des;
55         cin >> des;
56         int ans = 0;
57         for(int i = 0;i<des.size();i++){
58             ans += find(des.substr(i));
59         }
60         printf("%d
",ans);
61     }
62     return 0;
63 }

字典树

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<string>
 4 #include<iostream>
 5 using namespace std;
 6 struct node{
 7     int cnt;
 8     node *next[26];
 9     node(){
10         cnt = 0;
11         for(int i = 0;i<26;i++)
12             next[i] = NULL;
13     }
14 }*a;
15 void insert(char *str){
16     node *head = a;
17     int len = strlen(str);
18     for(int i = 0;i<len;i++){
19         int temp = str[i]-'a';
20         if(head->next[temp] == NULL)
21             head->next[temp] = new node;
22         head = head->next[temp];
23     }
24     head->cnt++;
25 }
26 int find(string t){
27     node *head = a;
28     int ans = 0;
29     for(int i = 0;i<t.size();i++){
30         if(head->next[t[i]-'a']){
31             if(head->next[t[i]-'a']->cnt){
32                 ans++;
33                 
34             }
35         }else
36             break;
37         head = head->next[t[i]-'a'];
38     }
39     head->cnt--;
40     return ans;
41 }
42 int main(){
43     int t;
44     scanf("%d",&t);
45     while(t--){
46         a = new node;
47         int n;
48         scanf("%d",&n);
49         char s[55];
50         for(int i = 0;i<n;i++){
51             scanf(" %s",s);
52             insert(s);
53         }
54         string des;
55         cin >> des;
56         int ans = 0;
57         for(int i = 0;i<des.size();i++){
58             ans += find(des.substr(i));
59         }
60         printf("%d
",ans);
61     }
62     return 0;
63 }

AC自动机