Step One:代码中出现的变量:
son[N][26],cnt[N],idx,p,u;
Step Two:庖丁解牛
0、游戏过程:p = 0;就好像一个小人走迷宫,p = 0就像是迷宫入口,从根节点p开始走,每走到路口就要从新选择方向(p = son[p][u]),走到最后遇到’‘\0’,即到达终点
1、son[N][26],通过u = str[i] - ‘a’(0-25),转换成下标,即son[p][u];(字符转换成下标,巧妙的一步 )
2、转换成下标后,通过if语句,判断先前是否已经使用过该节点(判断语句如下:)
if(!son[p][u]) son[p][u] = ++idx;//当前儿子节点先前未被使用,此处又要使用,故idx++
若已经使用过则直接进入下一个路口(高效的一步)
3、p = son[p][u],通过一个关卡,到达另外一个路口时,需要重新选择方向,调整弹道,继续闯关
4、(每一个节点都可以从终点倒退回起点,也就是每一个终点都会对于一个字符串,故只要拿到终点的位
置【即p】就可以查询字符串是否存在,或者记录字符串存在)cnt[p]++;该语句就是记录以当
前节点为终点的字符串出现几次,return cnt[p];就是返回查询的字符串出现几次
(ps:写的不是很完美,再结合下方的代码与注释应该大概可以看懂了)
Step Three:回头看看先前第一步的变量是否熟悉了点
代码:
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx;
//trie数存储字符串
void insert(string str)
{
int p = 0;//设置根节点
for(int i = 0; str[i]; i++) //扫描字符串
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;//当前儿子节点先前未被使用,此处又要使用,故idx++
p = son[p][u];//进入当前节点的儿子节点
}
cnt[p]++;//记录以当前节点为终点的字符串的个数(trie数中的终点节点代表着一个字符串【因为可以从终点往回退】,cnt数组的作用实际上就是记录以当前终点的字符串出现的次数)
}
//query查询字符串
int query(string str)
{
int p = 0;//设置根节点
for(int i = 0; str[i]; i++)//扫描字符串
{
int u = str[i] - 'a'; //将字符转换成下标,将字符是否出现转换成下标对应值是否为0(最巧妙)
if(!son[p][u]) return 0;
p = son[p][u];//进入当前节点的儿子节点(作用:进入下一个儿子节点,用于比较下一个字符串的下一个字符是否出现)
}
//字符串读取结束
return cnt[p];//将以当前节点为终点的字符串的个数返回
}
int main()
{
int n;
char op[2];
string str;
cin >> n;
cin.tie(0);
ios::sync_with_stdio(false);
while(n--)
{
cin >> op;
if(op[0] == 'I')
{
cin >> str;
insert(str);
}
if(op[0] == 'Q')
{
cin >> str;
cout << query(str) << endl;
}
}
}