[笔记] Trie字典树

思路

操作：

1. 插入节点：不断开辟自定义地址的节点，并确定是谁的子节点。
2. 查询节点：按要求通过父子关系向下查询。

代码

//插入一个新的字符串
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];
}
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