题目描述

维护一个字符串集合，支持两种操作：

I x向集合中插入一个字符串 x ；
Q x询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过105 ，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为I x或Q x中的一种。

输出格式

对于每个询问指令Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗104

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

使用数组构建树

int p[N][27],cnt[N],idx=1;
//p[N][27]：树，N表示多少层，27表示每一层中字母是否存在
//cnt[N]：标记，记录当前多少个相同字符串
//idx=1：地址

⭐⭐insert函数

void add(char *s){
    int j=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(p[j][u]==0) p[j][u]=idx++;
        j=p[j][u];
    }
    cnt[j]++;
}

⭐⭐find函数

int  find(char *s){
    int j=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(p[j][u]!=0) j=p[j][u];
        else return 0;

    }
    return cnt[j];
}

C++ 代码

#include<iostream>

using namespace std;

const int N=1e5;
int p[N][27],cnt[N],idx=1;
char s[N];
void add(char *s){
    int j=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(p[j][u]==0) p[j][u]=idx++;
        j=p[j][u];
    }
    cnt[j]++;
}
int  find(char *s){
    int j=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(p[j][u]!=0) j=p[j][u];
        else return 0;

    }
    return cnt[j];
}
int main(){
    int n;
    cin>>n;
    while(n--){
        char op;
        cin>>op;
        if(op=='I'){
            cin>>s;
            add(s);
        }
        else if(op=='Q'){
            cin>>s;
            cout<<find(s)<<endl;
        }

    }

    return 0;
}