解析在图中

代码

#include <iostream>
using namespace std;

const int N =100010;
int son[N][26];//存字符的数组，因为都是小写字符 所以第二维只需要用到26
int index;//作为下标
int count[N];//标记当前字符串出现了几次


void insert(char str[]){
    int p = 0;//每次插入 都先回到根节点
    for(int i = 0;str[i];i++){

        int x = str[i] - 'a';//用数值来代替字符

        if(!son[p][x]) son[p][x] = ++ index;//如果这个点不存在 就创建出来一个 并用index来索引

        p = son[p][x];//往下走
    }
    count[p] ++;//标记当前字符串 出现了几次
    return ;
}


int query(char str[]){
    int p = 0;
    for(int i = 0;str[i];i ++){
        int x = str[i] - 'a';

        if(!son[p][x]) return 0;
        p = son[p][x];
    }
    return count[p];//返回这个字符串出现了几次
}


int main()
{
    int n;
    cin >> n;

    char op[2],str[N];
    while(n--){
        scanf("%s%s",op,str);
        if(op[0] == 'I') insert(str);
        else cout << query(str) << endl;
    }

    return 0;
}