C++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include  <string>

using namespace std;

const int N = 1e5 + 5;
int n;
int a[N][26];
//第一维表示当前前缀，第二维表示当前前缀的当前字母，存放以p为前缀的子节点的下标
int cnt[N];//每个前缀（或已插入单词）对应的个数
char s[N];
int idx;
void insert()
{
    int p = 0;
    for(int i = 0; i < strlen(s); i ++)
    {
        int d = s[i] - 'a';
        if(a[p][d] == 0)
            a[p][d] = ++ idx;
        p = a[p][d];
    }
    cnt[p] ++;//完整插入后，p表示插入的单词
}
int query()
{
    int p = 0;
    for(int i = 0; i < strlen(s); i ++)
    {
        int d = s[i] - 'a';
        if(a[p][d] == 0)
            return 0;
        p = a[p][d];
    }
    return cnt[p];
}
int main()
{
    cin >> n;
    getchar();
    while(n --)
    {
        char c;
        cin >> c >> s;
        if(c == 'I')
            insert();
        else if( c == 'Q')
            cout << query() << endl;
        getchar();
    }
    return 0;
}