AcWing 835. Trie字符串统计
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-15 10:26:12
,
所有人可见
,
阅读 293
#include <iostream>
const int N = 100010;
using namespace std;
//son二维数组中存储的是每一个节点有多少个儿子的情况
//cnt存储的的是以当前节点结尾的单词的数量
//idx表示此时使用的是哪一个下标--下标为0的节点,既是根节点,有时空节点。
//此时同样是使用数组的方式来进行节点的存储
int son[N][26], cnt[N], idx;
char str[N];
void insert(char str[]) {
int p = 0;
//在c ++当中,字符串是以'\0'结尾,此时以这种方式来判断一个字符串是否已经到了结尾了。
//其实此时来写判断条件的话就是str[i] != 0的时候, 此时都是需要进行遍历的, 但是, 巧合的是
//当未到字符串结尾的时候, 此时的str[i] > 0, 所以使用这种方式可以来进行字符串的扫描。
////此时未到结尾的时候, str[i]在判断语句中为大于0的, 此时表示true
for (int i = 0; str[i]; i ++) {
//此时首先将a~z的小写字母映射成为0~25.
int u = str[i] - 'a';
//从根节点开始走, 如果此字母不存在的话, 创建这个节点
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
//此时表示以这个字母结尾的单词的数量多了一个。
cnt[p] ++;
}
//此时来查询一个字符串出现了多少次
int query(char 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];
}
//返回以p结尾的单词的数量
return cnt[p];
}
int main() {
int n;
scanf("%d", &n);
while (n --) {
//每一次读入的是长度为2的字符串
//c++ 中使用字符数组来存储多个字符串。
char op[2];
scanf("%s%s", op, str);
if (op[0] == 'I') {
insert(str);
} else {
printf("%d\n", query(str));
}
}
return 0;
}