AcWing 835. Trie字符串统计
原题链接
简单
作者:
叱咤月海鱼鱼猫
,
2023-11-13 16:06:06
,
所有人可见
,
阅读 50
#include <iostream>
using namespace std ;
const int N = 1e5 + 10 ;
/* son用来存储各个节点的子节点,由于字符串只包含26个小写字母,因此每个节点最多26个子节点
* 将字符'a'-'z'映射0-25,0即是根节点,也是空节点
* idx用于为节点编号,表明当前trie树中的节点数
* cnt用来记录已当前节点结尾的字符串的数量*/
int son[N][26] ,idx;
int cnt[N] ;
void insert(const string &str){
int p = 0 ; // 指针,用于表明当前处于哪个节点,从根节点开始
for(auto ch : str){
int u = ch - 'a' ; // 将a-z映射为0-25
if(!son[p][u]) son[p][u] = ++idx ; // 如果当前节点的对应子节点不存在,则进行创建
p = son[p][u] ; // 移动到下一个节点
}
cnt[p]++ ; // 记录以该节点结束的字符串数
}
int query(const string &str){
int p = 0 ;
for(auto ch : str){
int u = ch - 'a' ;
if(!son[p][u]) return 0 ; // 如果对应的子节点不存在,则说明该字符串不在集合中
p = son[p][u] ;
}
return cnt[p] ; // 返回该字符串的数量
}
int main(){
/*加快IO*/
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n = 0 ;
cin >> n ;
while(n--){
char op ;
string str ;
cin >> op >> str ;
if(op == 'I') insert(str) ;
if(op == 'Q') cout << query(str) << endl ;
}
return 0 ;
}