弱鸡的算法基础课题解更新中 算法基础课
点击关注催更

用二维数组模拟了一个链树

插入abfd,acbb,bca后的树:

注意trie树是不存char的,存的是对应的数字(也不是ascii码)

#include<iostream>
using namespace std;
//trie树
const int N=1e6+10;
int trie[N][26];
int cnt[N],idx;

void insert(char b[])
{
    int p=0;
    for(int i=0;b[i]!='\0';i++)
    {
        int u=b[i]-'a';
        if(trie[p][u]==0) trie[p][u]=++idx;
        p=trie[p][u];
    }
    cnt[p]++;
}

int find(char b[])
{
    int p=0;
    for(int i=0;b[i]!='\0';i++)
    {
        int u=b[i]-'a';
        if(trie[p][u] == 0) return 0;
        p=trie[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string a;
        char b[N];
        cin>>a;
        if(a=="I"){
            scanf("%s",b);
            insert(b);
        }else
        {
            scanf("%s",b);
            cout<<find(b)<<endl;
        }
    }
    return 0;
}