105 字典树(Trie)

视频链接：

#include 
using namespace std;

const int N = 100010;
int n;
char s[N];
// ch[p][e]: p父节点, e边, ch子节点
int ch[N][26], cnt[N], idx;

void insert(char *s){ // 插入字符串
    int p = 0;
    for(int i = 0; s[i]; i ++){
        int e = s[i]-'a'; //字母映射
        if(!ch[p][e]) ch[p][e]= ++idx;
        p = ch[p][e];
    }
    cnt[p]++; //词尾计数
}
int query(char *s){ // 查询字符串
    int p = 0;
    for(int i = 0; s[i]; i ++ ){
        int e = s[i] - 'a';
        if(!ch[p][e]) return 0;
        p = ch[p][e];
    }
    return cnt[p];
}
int main(){
    scanf("%d", &n);
    while(n -- ){
        char op;
        scanf("%s%s", &op, s);
        if(op == 'I') insert(s);
        else printf("%d\n", query(s));
    }
    return 0;
}