AcWing 835. Trie字符串统计(自己对y总代码理解)
原题链接
简单
作者:
刘晓昱
,
2020-05-12 11:33:58
,
所有人可见
,
阅读 739
#include<iostream>
using namespace std;
const int N =100010;
int son[N][26]; //二维数组,来模仿树
int cnt[N];//记录出现次数
int idx; //每个串的下一个字母的位置
char str[N]; //原串
void insert(char str[])
{
int p = 0; //第一次插入肯定从第一层走
for(int i = 0;str[i];++i)
{
int u = str[i] -'a'; //第一个字母在第一层的哪个位置
if(!son[p][u]) son[p][u] = ++idx; //如果第一层这个位置没有,那么填充,填充的是下一个字母的层数
//如果有,直接走到下一层
p = son[p][u]; //层数变到下一个字母的出现的层数的位置
}
cnt[p]++; //整个串弄完后,计数+1
}
int query(char str[])
{
int p = 0;
for(int i=0;str[i];++i)
{
int u = str[i] -'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin>>n;
while(n--)
{
string op;
cin>>op;
if(op == "I")
{
cin>>str;
insert(str);
}
else
{
cin>>str;
cout<<query(str)<<endl;
}
}
return 0;
}
为什么要函数参数要有char str [],,外面已经定义了,不能够直接用吗