基本概念#

定义：快速插入和查询字符串的数据结构
特点：利用字符串的公告前缀，将字符串组成树形结构
优势：相比map，可以高效查找公共前缀

数据结构准备#

头文件

1
#include <iostream>
2
#include <cstring>
3
using namespace std;

核心数组定义

1
const int N = 1e6 + 10;  // 总节点数上限
2

3
int tree[N][26];  // Trie树结构，26个字母，
4
                  // tree[cur][path]从节点cur出发，走path边到达下一节点；
5
int p[N];         // 记录经过该节点的次数（前缀统计）
6
int e[N];         // 记录以该节点结尾的单词数量
7
int idx;          // 当前可用的节点编号

核心操作#

插入字符串#

1
void insert(string &s) {
2
    int cur = 0;        // 从根节点开始
3
    p[cur]++;           // 根节点经过次数+1
4

5
    for (auto ch : s) {
6
        int path = ch - 'a';  // 计算字符对应的路径
7

8
        // 如果没有这条路，创建新节点
9
        if (tree[cur][path] == 0) {
10
            tree[cur][path] = ++idx;
11
        }
12

13
        cur = tree[cur][path];  // 移动到下一个节点
14
        p[cur]++;               // 当前节点经过次数+1
15
    }
16

17
    e[cur]++;  // 标记单词结尾
18
}

1
插入"abc"：
2
根(0) --a--> 节点1 --b--> 节点2 --c--> 节点3
3
p[0]++, p[1]++, p[2]++, p[3]++
4
e[3]++  // 标记单词结尾

查询完整单词出现次数#

1
int find(string &s) {
2
    int cur = 0;
3

4
    for (auto ch : s) {
5
        int path = ch - 'a';
6

7
        // 如果路径不存在，说明单词不存在
8
        if (tree[cur][path] == 0) {
9
            return 0;
10
        }
11

12
        cur = tree[cur][path];  // 沿着路径移动
13
    }
14

15
    return e[cur];  // 返回以该节点结尾的单词数量
16
}

查询前缀出现次数#

1
int find_pre(string &s) {
2
    int cur = 0;
3

4
    for (auto ch : s) {
5
        int path = ch - 'a';
6

7
        // 如果路径不存在，说明没有以此前缀开头的单词
8
        if (tree[cur][path] == 0) {
9
            return 0;
10
        }
11

12
        cur = tree[cur][path];  // 沿着路径移动
13
    }
14

15
    return p[cur];  // 返回经过该节点的次数（即前缀数量）
16
}

使用示例#

1
int main() {
2
    // 初始化
3
    idx = 0;
4
    memset(tree, 0, sizeof(tree));
5
    memset(p, 0, sizeof(p));
6
    memset(e, 0, sizeof(e));
7

8
    // 插入单词
9
    string word1 = "apple";
10
    string word2 = "app";
11
    insert(word1);
12
    insert(word2);
13

14
    // 查询
15
    cout << find("apple") << endl;    // 输出: 1
16
    cout << find("app") << endl;      // 输出: 1
17
    cout << find_pre("app") << endl;  // 输出: 2 (apple和app都以app开头)
18

19
    return 0;
20
}