AcWing 835. Trie字符串统计
原题链接
简单
作者:
阿飞被注册了
,
2021-06-13 21:15:44
,
所有人可见
,
阅读 255
用途:高效地存储和查找字符串的数据结构
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
//son[N]~:表示每个节点;son~[26]:每个节点只可能会延伸出来26个分支
//cnt[N]:表示次节点的单词个数
//idx:作用和单链表一样,通过++来进行对节点编号
int son[N][26], idx, cnt[N];
char s[N];
char op[2];
//插入操作
void insert(char str[])
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';//A~Z --> 0~25
if(!son[p][u]) son[p][u] = ++idx;//若此时没有这个节点就创建出来
p = son[p][u];//继续向下走
}
cnt[p]++;//记录改字符串有多少个
}
//查找和插入像的一批,因为要沿着创建出来的路走下去
void find(char str[])
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
//如果不存在这条路就返回0
if(!son[p][u])
{
cout << 0 << '\n';
return;
}
//如存在就像下继续走下去
p = son[p][u];
}
//最终输出该字符串的个数
cout << cnt[p] << '\n';
return;
}
int main()
{
int n;
cin >> n;
while(n--)
{
cin >> op >> s;
if(*op == 'I')
insert(s);
else
find(s);
}
return 0;
}