前言

倒腾了一天，慢慢的理解了y总的思路，记录分享一下，有误之处，还请多多包涵与指正

字典树 / 前缀树

• 来源

“Trie这个名字取自“retrieval”，检索，因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。”

• 功能 ： 高效的存储insert和查找query字符串集合的数据结构

  • 因为某节点的儿子存在共同的前缀

• 核心思想 ： 空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的

• 应用场景 ： 统计和排序大量的字符串 【注意有比较多的公共前缀这些字符串】

  • 文本词频统计
  • 前缀匹配
  • 字符串检索
• 复杂度分析
  • 时间 ： 插入| 查找 均为$O(n)$，其中n为字符串长度。
  • 空间 ： $o(26^n)$非常庞大（可采用双数组实现改善）。

yxc 上课代码

难点

理解int son[N][26] 和 idx

• Tire树本质上一个多叉树，最多可以分多少叉呢？因为此题存的都是小写字母，所以是26叉.

• 这里就解释了son这个二维数组的第二维的含义，就是他最多有26个孩子，那么他是谁呢，他当然是结点了，那结点之间怎么区分，或者这些孩子的爸爸叫啥，爸爸们用下标来区别，所以第一维就是爸爸们的id，son[0][1]含义就是0号爸爸有个儿子b ，那son[0][1] = 2，就是0号爸爸有个儿子b，儿子的id是2； 这些id就是由idx 来统一管理分配

• 把idx理解为派出所上户口的，生一个孩子上个户口，id为 idx + 1 ，姓名为26个小写字母中的其中一个

• 对于每个结点而言，可以知道他有没有这个孩子，有的话叫啥，id是啥；

• 那么对于查询，从根节点一路查下来，就可以找到某个字符串在不在；

• 对于插入字符串，也是一路下来，看有没有这个儿子，没有了给你生个儿子，有了继续给下面找，所以只插入该字符串中原来不存在的字符即可； 也就是利用了公共前缀来降低查询时间的开销以达到提高效率的目的;

#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26];     
int cnt[N];         
int idx;            // idx 当前用到了哪个下标 初值为0 即为空节点 也是根节点
char str[N];       // 要操作的字符串

void insert(char *str)
{
    int p  = 0; // 从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); 
        // 用scanf读入字符不能过滤空白字符，也就是op会把空格和回车都读进来。
        if(op[0] == 'I') insert(str);
        else printf("%d\n",query(str));
    }


    return 0;
}

总结

字典树是 后缀树、AC自动机等算法和复杂数据结构的基础，需熟练掌握。

参考资料

https://mp.weixin.qq.com/s?src=11&timestamp=1586240803&ver=2263&signature=5iXJ8o863u9hRXpKwqD0OnP1-5D59lf4aTShlvnwXvi2-WsyQFU3MNEceXadxFhvOK6kid3xOvjzeQa6Aw4EBEjUKzegFD4BBmSWMA-GZoxKO1SCYFYnfy2Pab0tKzF7&new=1