142. 前缀统计 AcWing

原题链接

Trie的基本运用

错误思路:

       将要查找前缀的字符串构建字典树,这样的结果是每个字符串都要重新构建一次树,并且我们需要预先保存要匹配前缀的单词,但题目单词数目没有讲明,所以我们必须将建树的字符串互换.(这样建树会导致MLE)

正解思路:

       将前缀建树,如果达到一个结点有单词就+1,如果没有单词就跳出

易错:

      我们需要再当前结点的下一节点处看是否有单词,否则会少计数

      可能会有重复单词

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 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<s.size();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<t.size();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 }

 

142. 前缀统计 AcWing

上一篇:记一次在virtualbox中安装windows7遇到增强功能安装分辨率的问题


下一篇:网页中控制ActiveX插件高度