博客

trie树是一种快速存储，查找字符串的数据结构，比如我想存储abc，adc，bca时，我可以创建一个trie树来简化字符串的查找

head既是一个头节点也是一个空节点，同时由于最多只有26个字母，所以我们tried树的每个节点最多只有26个，这样就可以保证能够表示所有可能的字符串。

问题引入

向一个字符串集合插入一个新的字符串；

#include<iostream>
const int N = 1e5+10;
int son[N][26];//第一维表示的当前的节点数个数，第二维表示的是当前节点存的的子节点是第几个字母，son[i][j]表示的是这个子节点的编号
int cnt[N];//表示的是以当前节点为终点的个数，N是编号
int idx;//表示当前使用的节点编号
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]++;//以当前节点为字符串结束终点的个数
    
}

我个人认为最难懂的地方就在于son[N][26]的意义了，N代表的是当前操作节点的个数，26为26个字母的数字映射，整体来看son[N][26]就是代表这个子节点的编号了，比如son[i][2] = 8；表示的是当前这个第i编号的节点有个子节点b，且这个子节点的编号就是8，也就是第8个添加到trie树的节点，

cnt[N]存储的就是以当前编号的节点为字符串终点的个数，比如cnt[8] = 3时，也就意味这当前8编号的节点为终点的字符串个数为3个；

idx就代表当前的操作的节点编号了，个人认为这个比较好理解