Trie树
作者:
成理第一深情
,
2024-01-23 09:00:22
,
所有人可见
,
阅读 42
N = 100010
son = [[0] * 26 for _ in range(N)] # 创建存单词的数据结构,每个词后面最多26个位置
cnt = [0] * N # 用于记录当前位置是否有单词结尾
idx = 0 # 根结点为0
def insert(str):
global son, cnt, idx
p = 0 # 从根结点开始插入
for s in str: # 遍历整个单词,一个一个字母插入
u = ord(s) - ord('a') # 将26个字母映射到0-25
# 如果结点不存在,就去创建这个结点,模拟字母插入的过程
if son[p][u] == 0:
idx += 1
son[p][u] = idx
p = son[p][u]
cnt[p] += 1 # 以当前字母结尾的单词个数+1
def query(str):
global son, cnt, idx
p = 0
for s in str:
u = ord(s) - ord('a')
if son[p][u] == 0:
return 0
p = son[p][u]
return cnt[p]
if __name__ == "__main__":
n = int(input())
for i in range(n):
opt, str = input().rstrip().split(' ')
if opt == "I":
insert(str)
else:
print(query(str))