AcWing 835

发表于 更新于 分类于 ， 阅读次数： 本文字数： 165 阅读时长 ≈ 1 分钟

题目

AcWing 835

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*Trie tree,AcWing 835*/

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

//idx 当前用的下标
int son[N][26], cnt[N], idx;//下标是0的点，既是根节点，又是空节点 
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] ++;
}

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 argc, char const *argv[])
{
	int n;
	scanf("%d", &n);
	while (n --){
		char op[2];
		scanf("%s%s", op, str);
		if (op[0] == 'I')insert(str);
		else printf("%d\n", query(str));
	}
}