y总源代码加个人理解,希望对跟我一样的萌新有帮助。
PS:我(不是号主)水平很低,大佬勿进
#include <iostream>
using namespace std;
const int N = 100010; //本来应该是100000,但是为了避免边界问题,所以加上10
int son[N][26]; //“26”表示每个节点(son[N])中接下来不同步的(就是与下个字母不一样的)单词
int cnt[N]; //表示每个节点中以该节点字母结尾的单词数量
int idx; //对每个字母进行单独编号,是唯一的。其中,下标是0的话,既是根节点,又是空节点
char str[N]; //进行插入的单词,方便后面for循环的结束条件(str[i] = "/0",for循环结束)
void insert(char str[])
{
int p = 0; //(普通节点+普通节点的子节点)初始化根节点
for(int i = 0; str[i]; i ++)
{
int u = str[i] - 'a'; //(普通节点的子节点)将26个字母映射成0~25的数字,结合son[N][26]考虑易得,为了后面判断节点的子节点是否有数
if(!son[p][u]) son[p][u] = ++ idx; //开创普通节点的子节点“路径”,并附上唯一的编号
p = son[p][u];
}
cnt[p] ++; //表示以p代表的编号结束的单词(str[])的数量+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]; //在上述判断不成立的条件下,最终将最后一个字母的病号给p
}
return cnt[p]; //输出以p代表的编号结束的单词(str[])的数量
}
int main()
{
int n;
scanf("%d", &n);
while(n --) //共有n个操作
{
char op[2];
scanf("%s%s", op, str); //注意:以char 数组的,用scanf不用加&取地址
if(op[0] == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}