题目描述

要求维护一个字符串的集合，要求满足两种类型的操作：
+ 可以插入一个任意的字符串；
+ 可以查询任意一个字串在此集合中出现的次数

样例

5
I abc
Q abc
Q ab
I ab
Q ab

1
0
1

算法1

Trie树(节点做法) $O(n*s.size())$

trie树(字典树)是一种哈希树的变种，基本上是为了统计、排序、保存大量字符串而特化的；
+ 除根节点外，它的每一个节点本身代表了一个元素；
+ 每一层对应字符串的第几个元素，从根节点到某一节点路径上所有于是怒连成的一个字符串即为该节点所对应的字符串；
+ 每一个节点的子节点包含的元素都应不同；

数组模拟Tire树有点抽象，这里先摆一个正经树节点做法；

时间复杂度

对每一个字符串都是线性的时间

C++ 代码

#include<iostream>
using namespace std;

struct TNode{
    int cnt;
    TNode *child[26];
};      //因为只有26个字母，可以通过指针数组的索引确定，所以结构体里可以不放元素而是放次数统计；

void insert(TNode *p,const string &s){
    for(int i = 0; i < s.size(); ++i){
        int idx = s[i] - 'a';
        if(p->child[idx] == nullptr) p->child[idx] = new TNode();   //若没有该元素，则动态创建；
        p = p->child[idx];
    }
    p->cnt++;           //在字符串结尾元素处进行统计，表明这个节点表示的字符串的数量；
}

int query(TNode *p,const string &s){
    for(int i = 0; i < s.size(); ++i){
        int idx = s[i] - 'a';
        if(p->child[idx] == nullptr) return 0;
        p = p->child[idx];
    }
    return p->cnt;
}

int main()
{
    ios::sync_with_stdio(false);

    TNode *root = new TNode();
    int n;
    cin>>n;
    char op;
    string s;
    while(n--){
        cin>>op>>s;
        if(op == 'I') insert(root, s);
        else cout<<query(root, s)<<endl;
    }
    return 0;
}

算法2

Trie树(数组模拟)

数组模拟时
+ son[][]二维数组其实模拟的就是节点，第一维与p配合定位节点，第二维是模拟节点的指针数组；
+ idx是用作表示第几个创造出来的节点；
+ cnt[]是与p配合表示某节点表示的字符串的统计；

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e5+10;
int son[N][26], cnt[N], idx;

void insert(const string &s){
    int p = 0;
    for(int i = 0; i < s.size(); ++i){
        int u = s[i] - 'a';
        if(!son[p][u]) son[p][u] = ++idx;       //++idx这里模拟动态创建节点的操作；
        p = son[p][u];
    }
    ++cnt[p];
}

int query(const string &s){
    int p = 0;
    for(int i = 0; i < s.size(); ++i){
        int u = s[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    char op;
    string s;
    while(n--){
        cin>>op>>s;
        if(op == 'I') insert(s);
        else cout<<query(s)<<endl;
    }
    return 0;
}