题目描述

blablabla

第一种 经典的 字典树

#include<iostream>
#include<cstdio>

using namespace std;//trie 数 高效存储和查询  画个字典树 比较容易理解!!!!!!!!
const int maxn=1e5+10;
int son[maxn][26];  //全为小写
int cnt[maxn*26];
int idx;
void insert(string str)
{
    int p=0;  //每次都从根节点开始
    for(int i=0;str[i];i++)
    {
        int u=0;
        u=str[i]-'a'; //
        if(son[p][u]==0)//如果字母不存在
        son[p][u]=++idx; //创建一个存储字母
        p=son[p][u]; // 然后再从这个开始创建下一个
    }
    cnt[p]++; //标记这个单词的末尾
}
int query(string str)
{
    int p=0; // 每次都从头开始遍历
    for(int i=0;str[i];i++)
    {
        int u=0;
        u=str[i]-'a';
        if(son[p][u]==0)
        return 0; //如果当前字母不存在
        p=son[p][u]; //再从下一个  开始找
    }
    return cnt[p];
}
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)//对于每个询问指令”Q x”，都要输出一个整数作为结果
    {   char s;
        string str;//“I x”向集合中插入一个字符串x；
        cin>>s>>str;
        if(s=='I')
        {
            insert(str);
        }
        else if(s=='Q')
        {
            printf("%d\n",query(str));
        }
    }
    return 0;
}

算法2

可以使用 字符串哈希 来写

(马上开学了 回头开始看看之前 写过的题 才发现 还有另一种写法😂)

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std; //用 哈希 来写  字符串哈希
const int P = 131;
const int maxn = 1e5 + 5;
const int mod = 1e7;
typedef unsigned long long ull;
ull h[maxn];
int cnt[mod];
ull hash_cc(string str)
{
    h[0] = 0;  //把他 哈希 成 下标 放入cnt 中
    int len = str.length();
    for(int i = 1 ; i <= len ; i ++)
    {
        h[i] = h[i - 1] * P + str[i - 1];//
    }
    return h[len] % mod;
}
int main()
{
    int N;
    scanf("%d", &N);
    while(N --)
    {
        string a, b;
        cin >> a;
        cin >> b;//“I x”向集合中插入一个字符串x；
        if(a=="I")
        {
            cnt[hash_cc(b)]++;
        }
        else if(a == "Q")
        {
            printf("%d\n",cnt[hash_cc(b)]);
        }
    }
    return 0;
}