字典树入门

用处

字典树在字符串的匹配上有很好的优势，这里的字符串也不一定是字符，也可以是别的东西，目前感觉只要是按照字符串的形式

字典树结点数组要开多大呢？

假设节点的分支数为node_Branch,字符串数量为n，字符串最大长度为len,

那么最大节点数组=$ n * len$，这个是重点。

具体讲解可以看这个B站上的视频橙子讲算法，感觉不错。

代码实现

void insert(char *str)
{
    int len=strlen(str);
    int root=0;
    for(int i=len-1; i>=0; i--)
    {
        int id=str[i]-'a';
        if(!tree[root][id])
            tree[root][id]=++tot;
        root=tree[root][id];
    }
    flag[root]++; //这里标记函数的位置也是可以多种多样
}

int find(char *str) //需要根据需要进行匹配
{
    int len=strlen(str);
    int root=0;
    for(int i=0; i<len; i++)
    {
        int id=str[i]-'a';
        if(!tree[root][id])
            return 0;
        root=tree[root][id];
    }
    return flag[root];
}