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;}