trie树 又名字典树
存储单词的集合 在一些特定的问题里 非常有用 比如寻找相同前缀的单词数量等
通常附加上题目中有特别强调字符都是小写字母或者大写字母时 就会用到tire树

核心数据结构就是一个son[p][u]
其中第一维 表示这个当前字母所在的位置

1
p = son[p][u] =idx

第二维 表示这个位置所存储的单词

核心操作

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
# 插入操作
def insert(s: str):
    p = 0
    for i in range(len(s)):
        # 将字母映射成数字
        u = ord(s[i]) - ord("a")
        # 如果当前单词结尾的这个字母不存在
        # 则创建新的枝条
        if not son[p][u]:
			# 这里用global 是因为 idx通常会定义成全局的 
			# 如果用是在一个class内 比如力扣的那种情况 其实nonlocal也可以
            global idx
            idx = idx + 1
            son[p][u] = idx
        # 走到下一个点
        p = son[p][u]
    # 单词s的存在数量+1
    cnt[p] = cnt[p] + 1
	
# 查询操作
def find(s: str):
    p = 0
    for i in range(len(s)):
        u = ord(s[i]) - ord('a')
        if not son[p][u]:
            return 0
        p = son[p][u]
    # 返回该单词的存在数量
    return cnt[p]

基础应用:
acwing835
原题链接: https://www.acwing.com/problem/content/description/837/

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
N = 100010
idx = 0
# trie树 每条枝代表一个单词 假设出现的字母只有26个小写字母
son = [[0 for i in range(26)] for _ in range(N)]
# 记录 编号为idx 的单词 出现的次数
cnt = N * [0]


def insert(s: str):
    p = 0
    for i in range(len(s)):
        # 将字母映射成数字
        u = ord(s[i]) - ord("a")
        # 如果当前单词结尾的这个字母不存在
        # 则创建新的枝条
        if not son[p][u]:
            global idx
            idx = idx + 1
            son[p][u] = idx
        # 走到下一个点
        p = son[p][u]
    # 单词s的存在数量+1
    cnt[p] = cnt[p] + 1


def find(s: str):
    p = 0
    for i in range(len(s)):
        u = ord(s[i]) - ord('a')
        if not son[p][u]:
            return 0
        p = son[p][u]
    # 返回该单词的存在数量
    return cnt[p]


T = int(input())
while T:
    T = T - 1
    op,s = input().split(' ')
    if op == 'I':
        insert(s)
    else:
        print(find(s))