题目描述
维护一个字符串集合,支持两种操作:
I x
向集合中插入一个字符串 $x$;Q x
询问一个字符串在集合中出现了多少次。
共有 $N$ 个操作,所有输入的字符串总长度不超过 $10^5$,字符串仅包含小写英文字母。
输入格式
第一行包含整数 $N$,表示操作数。
接下来 $N$ 行,每行包含一个操作指令,指令为 I x
或 Q x
中的一种。
输出格式
对于每个询问指令 Q x
,都要输出一个整数作为结果,表示 $x$ 在集合中出现的次数。
每个结果占一行。
数据范围
$1 \le N \le 2*10^4$
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1
Trie树
时间复杂度 $O(n)$
这段代码实现的是一个称为 Trie(也被称为前缀树或字典树)的数据结构。Trie是一种树形结构,它是一种哈希树的变种,特别适用于查找和存储字符串。Trie 的每个节点都包含一个字符数组(这里是son[N][26]),数组的每个元素都是一个指向下一个节点的指针。这里的数组大小为26,对应英文字母的数量。在这个Trie中,每个字符串都是从根节点到某个叶节点的路径。插入和查询字符串的操作都是通过遍历这个路径来完成的。
insert 函数的工作原理如下:
1. 从根节点(索引为0)开始。
2. 遍历输入的字符串,对于字符串中的每个字符,计算它在数组中的位置(’a’ 对应0,’b’ 对应1,等等)。
3. 如果当前字符对应的子节点不存在,就创建一个新的节点(即,分配一个新的索引)。
4. 移动到当前字符对应的子节点。
5. 重复步骤2-4,直到遍历完整个字符串。
6. 在最后一个字符对应的节点上,增加计数。
query 函数的工作原理如下:
1. 从根节点(索引为0)开始。
2. 遍历输入的字符串,对于字符串中的每个字符,计算它在数组中的位置。
3. 如果当前字符对应的子节点不存在,就返回0(表示字符串在 Trie 中不存在)。
4. 移动到当前字符对应的子节点。
5. 重复步骤2-4,直到遍历完整个字符串。
6. 返回最后一个字符对应的节点的计数(表示字符串在 Trie 中的出现次数)。
这种数据结构的优点是,插入和查询操作的时间复杂度都是O(n),其中n是字符串的长度。这比在数组或链表中查找字符串要快得多。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int son[N][26],cnt[N],idx; // son数组用于存储字典树的节点,cnt数组用于存储每个节点的计数,idx用于记录当前节点的索引
char str[N]; // str数组用于存储输入的字符串
// 插入函数,用于将一个字符串插入到字典树中
void insert(char *str){
int p=0; // p是当前节点的索引
for(int i=0;str[i];i++){ // 遍历输入的字符串
int u=str[i]-'a'; // 将字符转换为0-25的整数
if(!son[p][u]) son[p][u]=++idx; // 如果当前字符对应的节点不存在,就创建一个新的节点
p=son[p][u]; // 移动到下一个节点
}
cnt[p]++; // 增加当前节点的计数
}
// 查询函数,用于查询一个字符串在字典树中出现的次数
int query(char *str){
int p=0; // p是当前节点的索引
for(int i=0;str[i];i++){ // 遍历输入的字符串
int u=str[i]-'a'; // 将字符转换为0-25的整数
if(!son[p][u]) return 0; // 如果当前字符对应的节点不存在,就返回0
p=son[p][u]; // 移动到下一个节点
}
return cnt[p]; // 返回当前节点的计数
}
int main(){
int m;
cin>>m;
while(m--){
char s[2];
cin>>s>>str;
if(*s=='I') insert(str);
else cout<<query(str)<<endl;
}
return 0;
}