hiho1014(trie树)

题目连接：https://hihocoder.com/problemset/problem/1014

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=110;
 4 struct trie
 5 {
 6     char a;
 7     int cnt;
 8     trie* nex[26];
 9     trie()
10     {
11         cnt=0;
12         memset(nex,NULL,sizeof(nex));
13     }
14     void init()
15     {
16         cnt=0;
17         memset(nex,NULL,sizeof(nex));
18     }
19 };
20 trie rt;
21 int ans;
22 
23 inline int id(char c)
24 {
25     return c-'a';
26 }
27 
28 void inser(char *s)
29 {
30     int len=strlen(s);
31     trie* head=&rt;
32     for(int i=0;i<len;i++)
33     {
34         if(head->nex[id(s[i])]==NULL)
35         {
36             trie *node=new trie;
37             node->a=s[i];
38             head->nex[id(s[i])]=node;
39         }
40         head=head->nex[id(s[i])];
41         head->cnt++;
42     }
43 }
44 void fin(char *s)
45 {
46     int len=strlen(s);
47     trie *head=&rt;
48     ans=0;
49     for(int i=0;i<len;i++)
50     {
51         if(head->nex[id(s[i])]==NULL) return;
52         head=head->nex[id(s[i])];
53     }
54     ans=head->cnt;
55 }
56 int main()
57 {
58     char s[maxn];
59     int n,m;
60     while(scanf("%d",&n)!=EOF)
61     {
62         rt.init();
63         for(int i=0;i<n;i++)
64         {
65             scanf("%s",s);
66             inser(s);
67         }
68         scanf("%d",&m);
69         while(m--)
70         {
71             scanf("%s",s);
72             fin(s);
73             printf("%d
",ans);
74         }
75     }
76 }

View Code

上面是之前用指针写的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define CLR(m,a) memset(m,a,sizeof(m))
 4 const int maxnode=1000010;
 5 const int sigma=26;
 6 
 7 struct Trie
 8 {
 9     int ch[maxnode][sigma];
10     int val[maxnode];
11     int sz;
12 
13     int ans;
14     void init(){sz=1;CLR(ch[0],0);val[0]=0;}
15     int idx(char c) {return  c-'a';}
16     void inser(char *s,int v)
17     {
18         int u=0,n=strlen(s);
19         for(int i=0;i<n;i++){
20             int c=idx(s[i]);
21             if(!ch[u][c]){
22                 CLR(ch[sz],0);
23                 val[sz]=0;
24                 ch[u][c]=sz++; //建立新节点
25             }
26             u=ch[u][c];
27             val[u]++;  //有单词经过
28         }
29       //  val[u]+=v;  //更新节点挂载的信息
30     }
31 
32     int fin(char *s)
33     {
34         ans=0;
35         int u=0,n=strlen(s);
36         for(int i=0;i<n;i++){
37             int c=idx(s[i]);
38             if(!ch[u][c]) return 0;
39             u=ch[u][c];
40         }
41         return val[u];
42     }
43 };
44 
45 Trie trie;
46 
47 int main()
48 {
49     int n,m;
50     while(scanf("%d",&n)!=EOF){
51         trie.init();
52         char s[15];
53         for(int i=0;i<n;i++){
54             scanf("%s",s);
55             trie.inser(s,1);
56         }
57         scanf("%d",&m);
58         while(m--){
59             scanf("%s",s);
60             int ans=trie.fin(s);
61             printf("%d
",ans);
62 
63         }
64     }
65 }

非指针版