142. 前缀统计 AcWing

 1 #include 
 2 #include <string>
 3 #include 
 4 using namespace std;
 5 const int N = 1e6+10;
 6 int son[N][28],idx,cnt[N*28];
 7 void insert(string s)
 8 {
 9     int p = 0;
10     for(int i=0;i){
11         int u = s[i]-‘a‘;
12         if(!son[p][u]) son[p][u] = ++idx;
13         p = son[p][u];
14     }
15     cnt[p]++;
16 }
17 int query(string t)
18 {
19     int p = 0,ans = 0;
20     for(int i=0;i){
21         int u = t[i]-‘a‘;
22         if(!son[p][u]) break;
23         if(cnt[p]) ans+=cnt[p];
24         printf("当t[i]==%c,p==%d\n",t[i],p);
25         p = son[p][u];
26     }
27     return ans;
28 }
29 int main()
30 {
31     int n,m;
32     scanf("%d%d",&n,&m);
33     for(int i=1;i<=n;i++){
34         string s;
35         cin>>s;
36         insert(s);
37     }
38     for(int i=1;i<=m;i++){
39         string s;
40         cin>>s;
41         int ans = query(s);
42         printf("%d\n",ans);
43     }
44     
45     return 0;
46 }