题目描述
此题目斗胆将yxc的思想进行翻译一下,方便大家理解,有误之处,还请大家指出,共同成长。
要理解代码,需要明白以下三个问题?
- 这里的N他的作用范围是什么?
- idx,它到底是个啥?在程序中的作用是什么?
- son[][]这个二维数组,每一个维代表的是什么,其中son存放的值是个什么含义?
- 以上弄明白,那cnt[]这个就很容易推出来了?
解答
- 这里的N从题目描述中,就可以察觉到,他是代表字符串的总长度。所以idx他是永远在这个范围之内;那么son的一维为何是N,也很容易理解。
- 关于剩下的问题,可以直接看代码中的注释去理解。
hh,其实,感觉有点像做阅读理解。
样例
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26]; // 其中存放的是:子节点对应的idx。其中son数组的第一维是:父节点对应的idx,第第二维计数是:其直接子节点('a' - '0')的值为二维下标。
int cnt [N]; // 以“abc”字符串为例,最后一个字符---‘c’对应的idx作为cnt数组的下标。数组的值是该idx对应的个数。
int idx; // 将该字符串分配的一个树结构中,以下标来记录每一个字符的位置。方便之后的插入和查找。
char str[N];
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i++)
{
int u = str[i] - '0';
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
// 此时的p就是str中最后一个字符对应的trie树的位置idx。
cnt[p]++;
}
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i++)
{
int u = str[i] - '0';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
scanf("%d", &n);
char op[2];
while (n--)
{
scanf("%s%s", op, str);
if (op[0] == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
看懂了!(应该
请教一下 如果是abc abd 查abd是不是cnt[p]就变成了2了?
同问
注意这里的idx是全局变量,idx是一直增加的
不会,cnt数组记录的是结尾的字母的数量查abd,cnt[p]也是1
而且此时的p是为4
不是 那个-‘0’讲道理是不可以 开得是son[N][26] a-‘0’这样计算肯定会有数组越界
数组越界不是语法错误不会报 只能说测试样例小
字符串的长度应该只限制了树的深度吧,节点数可以比树的深度大很多吧,所以son开N是不是不够用呢
我感觉也是,感觉会出现越界啊😥
N在这里定义了1e5+10,而实际的N的范围是≤2∗104,而且字符串之间还存在重复现象。
son[N][26]注释里面,第二维是不是应该为’x’ - ‘a’
无所谓 反正只要映射是双射就行
。。。仔细看有没有所谓
会越界的,二维最大26,’a’-‘0’肯定比26大
你这阅读理解确实可以!
op为什么要开两个单位啊(萌新瑟瑟发抖)
%s读取字符串 会有一个’\0’作为字符串的结束 op[1]就是‘\0’
谢谢大佬!
手动模拟下就更明白了!
谢谢注释君!
注释太清晰了牛逼
谢谢总结!
# 大佬 是sir i-a吧……
应该不影响
为啥不影响
我觉得饿是-‘a’ 数组越界
### u越界了 (son[N][26];
感谢总结!