835. Trie字符串统计
摘要
Title: 835. Trie字符串统计
Tag: Trie
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
835. Trie字符串统计
-
题意
维护一个字符串集合，支持两种操作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。 -
思路
Trie字典树板子题
高效地存储和查找字符串
-
代码
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'''
Author: NEFU AB-IN
Date: 2022-02-28 23:16:38
FilePath: \ACM\Acwing\835.py
LastEditTime: 2022-02-28 23:32:18
'''
N = int(1e5 + 10)
son = [[0] * 26 for _ in range(N)] # N代表最多有多少个结点，由于题目中说最多10^5个字符，所以1e5即可
# 26代表结点的广度
cnt, idx = [0] * N, 0
def insert(s):
global idx
p = 0 #根节点，同时也是空节点
for i in range(len(s)):
u = ord(s[i]) - ord('a') #结点的字典序
if not son[p][u]: #如果不存在
idx += 1
son[p][u] = idx #就创建
p = son[p][u] #切换根，即往下走
cnt[p] += 1 #尾部加1计数
def query(s):
p = 0
for i in range(len(s)):
u = ord(s[i]) - ord('a')
if not son[p][u]: #如果不存在就返回0
return 0
p = son[p][u]
return cnt[p]
n = int(input())
for i in range(n):
op, s = input().split()
if op == 'I':
insert(s)
else:
print(query(s))