trie树

用于字符串的插入和查询

1.acwing835

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 100010;
 5 int son[N][26]; //trie树中每个点的所有儿子
 6 int cnt[N],idx; // 以当前这个点为结尾的单词有多少个;表示当前用到了哪个下标,idx = 0即是根节点又是空节点
 7 char str[N];
 8 
 9 void insert(char str[]) //插入即存储
10 {
11     int p = 0; //从根节点开始
12     for (int i = 0; str[i]; i ++ ) //遍历字符串的每一个字母
13     {
14         int u = str[i] - 'a'; //把字母映射成0~25的数字
15         if(!son[p][u]) son[p][u] = ++ idx; //如果p这个节点不存在u这个儿子的话，那么把他创建出来
16         p = son[p][u]; //走到下一个节点去
17     }
18     
19     cnt[p] ++; //以当前字母结尾的单词数量 + 1
20     
21 }
22 
23 int query(char str[]) //查询当前字符串出现了多少次
24 {
25     int p = 0;
26     for (int i = 0; str[i]; i ++ )
27     {
28         int u = str[i] - 'a'; //得到当前子节点对应的数字编号
29         if(!son[p][u]) return 0; //如果不存在这个点直接为0，否则的话走过去
30         p = son[p][u];
31     }
32     
33     return cnt[p]; //返回以p结尾的单词的数量
34 }
35 
36 int main()
37 {
38     int n;
39     scanf("%d", &n);
40     while (n -- ){
41         char op[2]; //两种操作类型
42         scanf("%s%s", op, str); //读入操作类型和字符串
43         
44        if(*op == 'I')  insert(str);
45        else printf("%d\n",query(str));
46     }
47     return 0;
48 }