AcWing 835. Trie字符串统计
原题链接
简单
作者:
随风随心
,
2021-01-12 10:35:07
,
所有人可见
,
阅读 272
注意son中每行只会有一列是非0的,idx对应son中的行
C++ 代码
#include<iostream>
#include<string>
using namespace std;
const int N = 1e5+1;//题目中说的是所有字符串的总长度不超过1e5,不是每个字符串不超过1e5.
int n , son[N][26] , cnt[N] , idx;//son存储的是子串编号,cnt是计数,idx是标识一种子串相当于用树表示的一个新的节点.
//son[N][i],每层只能存一个子串即每层次只能有一个单元不为0;
void insert(string s){
int p = 0;
for(int i = 0;s[i];i++){
int j = s[i] - 'a';
if(son[p][j] == 0) son[p][j] = ++idx;
p = son[p][j];
}
cnt[p]++;
}
int query(string s){
int p = 0;
for(int i = 0; s[i]; i ++)
{
int j = s[i] - 'a';
if(son[p][j] == 0) return 0;
p = son[p][j];
}
return cnt[p];
}
int main(){
//ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
char op;
string s;
while(n--){
cin>>op>>s;
if(op == 'I') insert(s);
else printf("%d\n" , query(s));
}
return 0;
}