AcWing 835. Trie字符串统计
原题链接
简单
作者:
sca
,
2023-10-08 20:36:46
,
所有人可见
,
阅读 52
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N];
int idx = 0; //全局唯一
// char str[N];
string str;
// void insert (char str[])
// void insert (char *str)
// void insert (char (&str)[]) //不知道为什么报错,在Clion里c++20能跑通
void insert (string &str)
{
int p = 0;
// for (int i = 0; str[i]; i++)
for (int i = 0; i < str.size(); i++)
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
// int query (char str[])
// int query (char *str)
// int query (char (&str)[])
int query (string &str)
{
int p = 0;
// for (int i = 0; str[i]; i++)
for (int i = 0; i < str.size(); i++)
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
//能走到这说明整个str串均读到了,现在就看结尾字符是否被打过标记,直接返回该结尾字符的标记次数即可(没打过是0,即return 0;打过...)
return cnt[p];
}
int main ()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
char op;
while (n--)
{
cin >> op;
if (op == 'I')
{
cin >> str;
insert(str);
}
if (op == 'Q')
{
cin >> str;
cout << query(str) << endl;
}
}
return 0;
}