Trie树

Trie树是用来快速存储和查找字符串集合的数据结构

#include<iostream>
using namespace std;
const int N  = 1e6;
int n;
int son[N][26];//26为存储字符的个数
int cnt[N];//以当前字符结尾的单词有多少个
int idx;//当前用到的下标，注意下标是0的点，既是根节点，又是空节点。
char s[N];
void insert(char *s)
{
    int p = 0;//p表示的是第几个节点
    for(int i = 0; s[i] != '\0'; i ++)
    {
        int u = s[i] - 'a';
        if(!son[p][u])son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;
}

int qurry(char *s)
{
    int p = 0;//p表示的是第几个节点
    for(int i = 0; s[i] != '\0'; i ++)
    {
        int u = s[i] - 'a';
        if(!son[p][u])return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        char op;
        cin >> op >> s;
        if(op == 'I')insert(s);
        else cout <<qurry(s)<<endl;
    }
}