数据结构--Trie字符串统计

1、“Trie树” 作用：

• 高效地存储和查找字符串集合的数据结构。

2、“Trie树” 存储字符串的形式如下：

1. 用 “0” 来表示 “根节点（root）”。
2. 存入一个字符串时，会在字符串最后结尾的那个字符节点打上标记。比如：字符串 “abcd” 是以字符 “d” 结尾的，那么就在字符节点 “d” 打上标记。

具体例子理解

左边数组初始全是0
添加字符串`”abc“，

1. 首先``p = 0`
   p 指的是当前所遍历到的节点
   index 指的是最后一个可用的节点
2. 依次获取每个字符(首先获取字符'a')映射的数字(0~25)
   
3. 由于当前节点，并没有'a'这个节点指向的节点， 我们就需要新建一个节点，然后我们把 ++idx 填写到这个节点上，第一次是1
   
   
   
   
   
   AcWing 835. Trie字符串统计

#include 

using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

int query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n --)
    {
        char op[2];
        scanf("%s%s", op, str);
        if(op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47