142. 前缀统计 AcWing
标签：iostream href oid 否则 rgb str return names string
原题链接
Trie的基本运用
错误思路：
将要查找前缀的字符串构建字典树,这样的结果是每个字符串都要重新构建一次树,并且我们需要预先保存要匹配前缀的单词,但题目单词数目没有讲明,所以我们必须将建树的字符串互换.(这样建树会导致MLE)
正解思路：
将前缀建树,如果达到一个结点有单词就+1,如果没有单词就跳出
易错：
我们需要再当前结点的下一节点处看是否有单词,否则会少计数
可能会有重复单词
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){
34 string s;
35 cin>>s;
36 insert(s);
37 }
38 for(int i=1;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
标签：iostream href oid 否则 rgb str return names string
原文地址：https://www.cnblogs.com/newblg/p/14220256.html
评论