Trie树

在印象笔记中记有详细思路，在这里就只记录第二次做的时候的疑问
cnt是如何表示字符串出现的次数的：
假如现在有 abc , dc , ad,三个字符串，其中cnt[1]表示以”a”出现的次数,cnt[2]表示 “ab”出现的次数,cnt[3]表示”abc”出现的次数,cnt[4]表示”d”出现的次数，cnt[5]表示”dc”出现的次数
cnt[6]表示”ad”出现的次数

C++ 代码

#include <iostream>
using namespace std;

const int N = 20010;
int p[N][26];
int idx,cnt[N];

void insert(string str){
    int ne = 0;
    for(int i = 0;i < str.size();++i){
        int temp = str[i] - 'a';
        if(!p[ne][temp]){
            p[ne][temp] = ++idx;
        }
        ne = p[ne][temp];
    }
    cnt[ne]++;
}

int query(string str){
    int ne = 0;
    for(int i = 0;i < str.size();++i){
        int temp = str[i] - 'a';
        if(!p[ne][temp]){
            return 0;
        }
        ne = p[ne][temp];
    }
    return cnt[ne];
}

int main(){
    int n;
    cin >> n;
    while(n--){
        char c;
        string str;
        cin >> c >> str;
        if(c == 'I'){
            insert(str);
        }else{
            cout << query(str) << endl;
        }
    }
    return 0;
}