字典树(Tire)模板

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 struct node
 5 {
 6     node *ne[26];
 7     int cnt;
 8 }*head;
 9 void insert(char *s)
10 {
11     node *p=head,*q;
12     for(int i=0;s[i];i++)
13     {
14         int id=s[i]-'a';
15         if(p->ne[id]!=NULL)
16         {
17             p=p->ne[id];
18             p->cnt++;
19         }
20         else
21         {
22             q=(node*)malloc(sizeof(node));
23             for(int i=0;i<26;i++)
24                 q->ne[i]=NULL;
25             q->cnt=1;
26             p->ne[id]=q;
27             p=p->ne[id];
28         }
29     }
30 }
31 int Q(char *s)//查询有多少以该串为前缀的串的数量
32 {
33     node *p=head;
34     for(int i=0;s[i];i++)
35     {
36         int id=s[i]-'a';
37         if(p->ne[id]!=NULL)
38             p=p->ne[id];
39         else
40             return 0;
41     }
42     return p->cnt;
43 }
44 void clean(node *p)//释放空间
45 {
46     if(p==NULL)    return ;
47     for(int i=0;i<26;i++)
48     {
49         if(p->ne[i]!=NULL)
50             clean(p->ne[i]);
51     }
52     free(p);
53     return ;
54 }
55 int main()
56 {
57     int n,m;
58     char s[11];
59     while(scanf("%d",&n)!=EOF)
60     {
61         head=(node*)malloc(sizeof(node));
62         for(int i=0;i<26;i++)
63             head->ne[i]=NULL;
64         while(n--)
65         {
66             scanf("%s",s);
67             insert(s);
68         }
69         scanf("%d",&m);
70         while(m--)
71         {
72             scanf("%s",s);
73             printf("%d
",Q(s));
74         }
75         clean(head);
76     }
77     return 0;
78 }

hiho1014

#include<stdio.h>
#include<string.h>
const int N=1e5+11;
int t[N*11][27],cnt;
void insert(char *s){
    int now=0;
    for(int i=0;s[i];i++){
        int id=s[i]-'a';
        if(!t[now][id]){
            t[now][id]=++cnt;
        }
        now=t[now][id];
        t[now][26]++;
    }
}
int Q(char *s){
    int now=0;
    for(int i=0;s[i];i++){
        int id=s[i]-'a';
        if(t[now][id])
            now=t[now][id];
        else
            return 0;
    }
    return t[now][26];
}
int main(){
    int n;
    char s[20];
    while(scanf("%d",&n)!=EOF){
        memset(t,0,sizeof(t));cnt=0;
        while(n--){
            scanf("%s",s);
            insert(s);
        }
        scanf("%d",&n);
        while(n--){
            scanf("%s",s);
            printf("%d
",Q(s));
        }
    }
    return 0;
}