Trie前缀树

发表于 更新于 分类于 Artalk： loading...

有关Trie字典树/前缀树也可参照「转载」字典树/前缀树的实现

简概

Trie\textit{Trie} 是用来高效地存储和查找 字符串集合 的数据结构

示例

例如要存储以下字符串节点

image-20211124134620253image-20211124134859423

存储完毕时，在每个单词的末尾进行标记isEnd = true

查找时就简单了，一般分为两种类型：

  1. 查找目标单词是否被包含在集合中
  2. 查找集合中是否有以目标单词为前缀的字符串

例题

acwing 835. Trie字符串统计

问题描述

维护一个字符串集合，支持两种操作：

  1. I x 向集合中插入一个字符串 xx
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 NN个操作，输入的字符串总长度不超过 10510^5 ，字符串仅包含小写英文字母。

输入格式

第一行包含整数 NN，表示操作数。

接下来NN行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 xx 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2×1041\le N\le2\times10^4

输入样例：

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
2
3
1
0
1

代码

这里不同于之前的实现方案，没有采用结构体

y总搞竞赛的，可能考虑速度比较重要

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
#include <iostream>

using namespace std;

const int N = 100010; // 设定集合中字符串总长度的上限

int next[N][26], cnt[N], idx;
char str[N];

void insert(char *str) {
    int p = 0;
    // c++字符串结尾是'\0'，可以用来判断是否到结尾了
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a'; // 将小写字母映射到0-25
        if (!next[p][u]) next[p][u] = ++ idx; // 若无，则创建新节点
        // 这里巧妙地利用了idx这个全局变量，实现了每一个字符有一个自己的idx值
        // “唯一地址”,妙啊！
        p = next[p][u]; 
    }
    cnt[p] ++ ; // 表明以这个p点（插入字符串的最后一个字符）结尾的字符串数量+1
}

int query(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i ++ ) {
        int u = str[i] - 'a';
        if (!next[p][u]) return 0;
        p = next[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    scanf("%d", &n);
    while (n -- ) {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

aciwng 143. 最大异或对

问题描述

在给定的NN个整数A1,A2⋯ANA_1,A_2 \cdots A_N中选出两个进行 ⊕\oplus（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 NN 。

第二行输入 NN 个整数A1∼ANA_1 \sim A_N。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051 \le N \le 10^5
0≤Ai≤231−10 \le A_i \le 2^{31} - 1

输入样例：

1
2
3
1 2 3

输出样例：

1
3

解题思路

还是老办法：先用暴力做法去做，然后考虑从何种角度去优化

暴力方法代码：

1
2
3
4
5
6
7
int res = 0;
for (int i = 0; i < n; ++ i) {
    for (int j = i + 1; j < n; ++ j) {
        res = max(res, q[i] ^ q[j]);
    }
}
cout << res << endl;

先固定一个AiA_i，然后从Ai+1∼An−1A_{i+1}\sim A_{n-1}，选出AjA_j使得Ai⊕Aj{A_i}\oplus{A_j}最大。

优化第二步，即：如何更高效地选出一个 AjA_j 使得异或值最大

二进制表示 AiA_i ，若最高位为1，则尽量找一个最高位为0的 AjA_j ，这样最高位的异或值为1

image-20211124150050662

则可以按照前缀树的思想来存储每个数：

将每个整数按照「二进制」形式从高位到低位存储，数中每个节点的 nextnext 数组存0和1两个子节点（与之前的0-25，26个英文字母a∼za \sim z比较）

对于每个 AiA_i ，以二进制形式，从最高位开始与前缀树中元素进行比较，找其反码（Ex ：AiA_i当前二进制位是0，则找1，0⊕1=10\oplus1=1），积累结果。如果不存在，则继续顺着找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int query(int x) {
    int pos = 0, res = 0;
    for (int i = 30; i >= 0; i -- ) {
        // 找当前二进制位的反码
        // 以下x代表一个二进制位
        // because : x ^(~x) = 1
        int u = (x >> i & 1); // 取第i位的值
        // 注意: 这里的u是个32bit的int型变量，用取反～运算符的话，例如：1: 0000 0000 0000 0000 0000 0000 0000 0001
        // 会变成～1: 1111 1111 1111 1111 1111 1111 1111 1110 
        // 所以这里用逻辑运算符 ！来具体操作 0-->false, 1-->true
        if (ne[pos][!u] == 0) { // 反码不存在，则继续顺着往下
            pos = ne[pos][u]; 
            // ~(~(x >> i & 1)) = x >> i & 1即A_i当前的二进制位
        }
        else { // 如果存在，积累结果
            res += (1 << i);
            pos = ne[pos][!u];
        }
    }
    return res;
}

举例模拟：

image-20211124162239810

例如，query(6)时，扫描到6的第二个二进制位1时，发现，前缀树当前层中没有0节点，只能顺着1继续往下走，最终query(6)的结果为6⊕3=56\oplus3=5，即当前6异或值最大的结果。

代码

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
46
47
#include <iostream>

using namespace std;

const int N = 100010, M = 3100010;

int n;
int a[N], ne[M][2], idx;

void insert(int x) {
    int pos = 0;
    for (int i = 30; i >= 0; i -- ) {
        int u = x >> i & 1;
        if (ne[pos][u] == 0) ne[pos][u] = ++ idx;
        pos = ne[pos][u];
    }
}

int query(int x) {
    int pos = 0, res = 0;
    for (int i = 30; i >= 0; i -- ) {
        int u = x >> i & 1;
        if (ne[pos][!u] == 0) {
            pos = ne[pos][u];
        }
        else {
            res += (1 << i);
            pos = ne[pos][!u];
        }
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, query(a[i]));

    printf("%d\n", res);

    return 0;
}

1803. 统计异或值在范围内的数对有多少

问题描述

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。

漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length且 low <= (nums[i] XOR nums[j]) <= high 。

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 2 * 104
  • 1 <= low <= high <= 2 * 104

简要分析

本题和acwing 143是类似的思路，不再赘述，参见代码注释

代码

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
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    class Trie {
        int cnt;
        Trie[] next;
        public Trie() {
            this.cnt = 0;
            this.next = new Trie[2];
        }
        void add(int x) {
            Trie cur = this;
            for (int i = 14; i >= 0; --i) {
                int u = x >> i & 1;
                if (cur.next[u] == null) cur.next[u] = new Trie();
                cur = cur.next[u];
                cur.cnt++;
            }
        }
        int query(int x, int limit) {
            int ans = 0;
            Trie cur = this;
            for (int i = 14; i >= 0; --i) {
                int u = x >> i & 1;
                /**
                limit 当前数位为1
                如果XOR 的结果为0，则符合小于的限制，积累结果；
                然后走向 XOR 结果为1的子节点，保证前缀和limit相同
                如果没有，直接返回结果
                 */
                if ((limit >> i & 1) == 1) {
                    if (cur.next[u] != null) ans += cur.next[u].cnt;
                    if (cur.next[u ^ 1] == null) return ans;
                    cur = cur.next[u ^ 1];
                } else {
                    // limit 当前数位为0
                    if (cur.next[u] == null) return ans;
                    // 注意，XOR 的当前数位为0，顶多是相同，不一定小于，不要积累结果
                    cur = cur.next[u];
                }
            }
            ans += cur.cnt;
            return ans;
        }
    }
    public int helper(int[] q, int limit) {
        Trie trie = new Trie();
        int n = q.length;
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            trie.add(q[i - 1]);
            ans += trie.query(q[i], limit);
        }
        return ans;
    }
    public int countPairs(int[] nums, int low, int high) {
        return helper(nums, high) - helper(nums, low - 1);
    }
}

leetcode 208. 实现 Trie (前缀树)

问题描述

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]

解释

1
2
3
4
5
6
7
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 10<sup>4</sup> 次

代码

y总教的二维数组实现

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
46
47
48
49
const int N = 1e5+10;
bool isEnd[N];
int ne[N][26], idx;
class Trie {
public:
    Trie() {
        memset(isEnd, false,sizeof(isEnd));
        memset(ne, 0, sizeof(ne));
        idx = 0;
    }
    
    void insert(string word) {
        int pos = 0;
        for (auto ch : word) {
            int u = ch - 'a';
            if (ne[pos][u] == 0) ne[pos][u] = ++ idx;
            pos = ne[pos][u];
        }
        isEnd[pos] = true;
    }
    
    bool search(string word) {
        int pos = 0;
        for (auto ch : word) {
            int u = ch - 'a';
            if (ne[pos][u] == 0) return false;
            pos = ne[pos][u];
        }
        return isEnd[pos];
    }
    
    bool startsWith(string prefix) {
        int pos = 0;
        for (auto ch : prefix) {
            int u = ch - 'a';
            if (ne[pos][u] == 0) return false;
            pos = ne[pos][u];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

利用TrieNode节点，结构体做法。

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
46
47
48
49
50
51
52
class Trie {
public:
    /** Initialize your data structure here. */
    bool isEnd;
    vector<Trie*> children;

    Trie() {
        children = vector<Trie*>(26, NULL);
        isEnd = false;
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* node = this;
        for (auto c : word){
            if (node->children[c - 'a'] == NULL){
                node->children[c - 'a'] = new Trie();
            }
            node = node->children[c - 'a'];
        }
        node->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* node = this;
        for (auto c : word){
            node = node->children[c - 'a'];
            if (node == NULL) return false;
        }
        return node->isEnd;

    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* node = this;
        for (auto c : prefix){
            node = node->children[c - 'a'];
            if (node == NULL) return false;
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */