Trie树

困惑1：什么是idx？这是干嘛用的？

idx作为当前能插入节点的索引指针，这个思想与之前的很多算法类似。
son[N][26]数组里每一行都是一个结点，son[p][u]则代表了当前结点某个子节点的索引（对应于数组的哪一行）
所以++idx的操作就相当于新建了一个结点（到下一行）
用这个办法新建结点出来的Trie树在物理结构上是紧凑的，不存在碎片（优点）

困惑2：取cnt[p]的时候，一定就是我们想要的那一个字符串的数量吗？有没有可能两个字符串有相同结尾，而我们取的cnt值是这两个字符串的和呢？

这个想法现在看来是显然不成立的，可以从两个角度来解释：
（1）Trie树是一个树，而不是图，所以一个结点的父节点至多只能有一个，所以不存在两个字符串合并到一个结点
     的情况。
（2）cnt[]存储的是以每个节点结尾的单词数量，注意这里是节点，而不是字母，从(1)可以知道，不同字符串之间
     相同的字母不可能是一个节点，所以说，Trie树中会有很多不同的节点存储相同的字母，这其实就保证了某个
     字符串中的某个字母在Trie树中一定是唯一的。既然是唯一的，那么cnt[]中的值也就一定是当前字符串的数
     量，而不可能是多个字符串数量的和。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

int son[N][26] = {0}, cnt[N]={0}, 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;
    char op[2];
    cin>>n;
    while(n --){
        scanf("%s%s", op, str);
        if(op[0]=='I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}