Repository HDU - 2846 字典树

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=500010;
 4 struct Trie{
 5     int ch[maxn][27];
 6     int num[maxn];
 7     int lastnum[maxn];
 8     int size=1;
 9     void init(){
10         memset(ch,0,sizeof(ch));
11         memset(num,0,sizeof(num));
12         memset(lastnum,0,sizeof(lastnum));
13         size=1;
14     }
15     void insert(char*s,int ok){
16         int i=0,rc=0;
17         for(;s[i]!='\0';i++){
18             int id=s[i]-'a';
19             //coutr<<rc<<endl;
20             if(ch[rc][id]==0){
21                 ch[rc][id]=size++;
22             }
23             rc=ch[rc][id];
24               if(lastnum[rc]==0||lastnum[rc]!=ok)num[rc]++,lastnum[rc]=ok;
25             //cout<<" "<<num[rc]<<" "<<rc<<endl;
26         }
27     }
28     int  find(char*s){
29         int i=0,rc=0;
30         for(;s[i]!='\0';i++){
31             int id=s[i]-'a';
32             if(ch[rc][id]==0)return 0;
33             rc=ch[rc][id];
34         }
35         return num[rc];
36     }
37 }trie;
38 char s[100];
39 char s1[100];
40 int main(){
41     int n;
42     trie.init();
43     scanf("%d",&n);
44     for(int i=0;i<n;i++){
45         scanf("%s",s);
46         int len=strlen(s);
47         for(int j=0;j<len;j++){
48             trie.insert(s+j,i+1);
49         }
50     }
51     int t;
52     scanf("%d",&t);
53     while(t--){
54         scanf("%s",s);
55         printf("%d\n",trie.find(s));
56     }
57     return 0;
58 }