trie（字典树、前缀树）

1. trie原理

原理

• trie树，又被称为字典树、前缀树，是一种高效地存储和查找字符串集合的数据结构。
• 一般来说，用到trie的题目中的字母要么全是小写字母，要么全是大写字母，要么全是数字，要么就是0和1。也就是说字母的个数不是很多。
• 如下是一个trie树的例子：

• 真实存储中，图中的每个字符都是被存储在边上的，节点是不存储字符信息的。
• 查询某个字符串S是否在这个字符串集合中是否存在的话，可以从根开始遍历，当遍历到空节点或者S已经遍历结束但是trie树中对应节点不是字符串的话，说明不存在该字符串。

2. AcWing上的trie题目

AcWing 835. Trie字符串统计

问题描述

• 问题链接：AcWing 835. Trie字符串统计

  

分析

• 在trie树的每个节点上记录一下以当前字母结尾的单词的出现次数即可。

• 代码实现中使用一个cnt数据记录每个字符串出现的次数即可。

代码

• C++

#include <iostream>using namespace std;const int N = 1e5 + 10;
int son[N][26];  // 存储树中每个节点的子节点
int cnt[N];  // 存储以每个节点结尾的单词数量
int idx;  // 0号点既是根节点，又是空节点
char str[N];void insert(char *str) {int p = 0;for (int i = 0; str[i]; i++) {int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++idx;  // 如果 p 不存在孩子 u, 则创建p = son[p][u];}cnt[p]++;
}int query(char *str) {int p = 0;for (int i = 0; str[i]; i++) {int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}int main() {int n;scanf("%d", &n);char op[2];while (n--) {scanf("%s%s", op, str);if (op[0] == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}

• Java

import java.io.*;public class Main {public static final int N = 100010;public static int[][] son = new int[N][26];  // 存储树中每个节点的子节点public static int[] cnt = new int[N];  // 存储以每个节点结尾的单词数量public static int idx;  // 0号点既是根节点，又是空节点private static void insert(String s) {int p = 0;for (char c : s.toCharArray()) {int u = c - 'a';if (son[p][u] == 0) son[p][u] = ++idx;  // 如果 p 不存在孩子 u, 则创建p = son[p][u];}cnt[p]++;}private static int query(String s) {int p = 0;for (char c : s.toCharArray()) {int u = c - 'a';if (son[p][u] == 0) return 0;p = son[p][u];}return cnt[p];}public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());while (n-- != 0) {String[] t = br.readLine().split(" ");String op = t[0], s = t[1];if (op.equals("I")) insert(s);else System.out.println(query(s));}}
}

AcWing 143. 最大异或对

问题描述

• 问题链接：AcWing 143. 最大异或对

  

分析

• 这里题如果暴力求解的话，相当于让任意两个不同的数进行异或运算，然后记录最大的结果输出即可，伪码如下：

int res = 0;  // 最小是0
for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++)res = max(res, a[i] ^ a[j]);
}

• 我们分析内层循环，其实在寻找和a[i]异或值最大的另一个数据，我们可以使用字典树（trie）优化这一步，因为所有的数据范围在$[0,2^{31})$之间，二进制位数最长是31位，我们可以将这31位二进制数看做一个字符串，最高位是字符串的第一个字符，然后将所有的这些字符串插入trie树中。

• 这样操作之后，我们如何得到与某个数据A异或值最大的数呢？数据A可以看成一个31的二进制字符串，从左到右遍历这个字符串，假设当前考察的是字符t，则在trie树中我们应该走到1^t的分支上（如果存在的话），这样异或值才能最大（贪心思想）。

• 这一题数字的个数最多10万个，每个数字看成一个31位的字符串，因此trie树中最多310万个节点。大约占用的空间为$3.1\times 10^6\times 2\times 4=2.48\times 10^7$Byte，相当于24.8MB，没有超过64MB。

代码

• C++

#include <iostream>using namespace std;const int N = 100010, M = 3100010;int n;
int a[N];
int son[M][2], idx;void insert(int x) {int p = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1;if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}
}int query(int x) {int p = 0, res = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1;if (son[p][u ^ 1]) {res += 1 << i;p = son[p][u ^ 1];} else p = son[p][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;
}

AcWing 1414. 牛异或

问题描述

• 问题链接：AcWing 1414. 牛异或

  

分析

• 这里需要求解一段连续区间异或和最大值。可以使用前缀和求解区间和，这样区间和问题就转变为了两个数据的异或值，此时问题转化为了AcWing 143. 最大异或对。

• 注意前缀和数组初始数据有0，开始要加入。

代码

• C++

#include <iostream>using namespace std;const int N = 100010, M = N * 21;int n;
int s[N];  // 异或前缀和
int son[M][2], id[M], idx;  // id存储每个节点对应的原字符串的编号void insert(int x, int k) {int p = 0;for (int i = 20; i >= 0; i--) {int u = x >> i & 1;if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}id[p] = k;
}int query(int x) {int p = 0;for (int i = 20; i >= 0; i--) {int u = x >> i & 1;if (son[p][!u]) p = son[p][!u];else p = son[p][u];}return id[p];
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &s[i]);s[i] ^= s[i - 1];}int res = -1, a, b;insert(s[0], 0);for (int i = 1; i <= n; i++) {int k = query(s[i]);int t = s[i] ^ s[k];if (t > res) res = t, a = k + 1, b = i;insert(s[i], i);}printf("%d %d %d\n", res, a, b);return 0;
}

AcWing 3485. 最大异或和

问题描述

• 问题链接：AcWing 3485. 最大异或和

  

分析

• 本题和AcWing 1414. 牛异或类似，但是多了一个限制：区间长度不能超过M。

• 因此需要支持删除某个字符串，但是trie不能支持直接将某个节点删除掉，这里可以使用一个cnt数组记录trie中每个节点出现的次数。当出现的次数为0时，代表这个节点不存在，不能使用。

代码

• C++

#include <iostream>using namespace std;const int N = 100010 * 31, M = 100010;int n, m;  // 数组长度，限制长度
int son[N][2], cnt[N], idx;  // cnt记录有多少个单词经过当前节点
int s[M];  // 前缀和// v=1表示增加一个数据，v=-1表示删除一个数据
void insert(int x, int v) {int p = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1;if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];cnt[p] += v;}
}int query(int x) {int p = 0, res = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1;if (cnt[son[p][!u]]) p = son[p][!u], res = res * 2 + 1;else p = son[p][u], res = res * 2;}return res;
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {int x;scanf("%d", &x);s[i] = s[i - 1] ^ x;}int res = 0;insert(s[0], 1);for (int i = 1; i <= n; i++) {// 考虑s[i], 此时窗口内有s[i-m]~s[i-1]// s[i-m]^s[i]表示原数据[i-m+1~i]这m个数据异或和if (i > m) insert(s[i - m - 1], -1);res = max(res, query(s[i]));insert(s[i], 1);}printf("%d\n", res);return 0;
}

3. 力扣上的trie题目

Leetcode 0208 实现Trie

问题描述

• 问题链接：Leetcode 0208 实现Trie

  

分析

• 实现即可，就是模板。

代码

• C++

/*** 执行用时：56 ms, 在所有 C++ 提交中击败了99.24%的用户* 内存消耗：43.9 MB, 在所有 C++ 提交中击败了21.75%的用户*/
class Trie {
public:struct Node {bool is_end;Node *son[26];Node() {is_end = false;for (int i = 0; i < 26; i++)son[i] = NULL;}} *root;/** Initialize your data structure here. */Trie() {root = new Node();}/** Inserts a word into the trie. */void insert(string word) {auto p = root;for (auto c : word) {int u = c - 'a';if (!p->son[u]) p->son[u] = new Node();p = p->son[u];}p->is_end = true;}/** Returns if the word is in the trie. */bool search(string word) {auto p = root;for (auto c : word) {int u = c - 'a';if (!p->son[u]) return false;p = p->son[u];}return p->is_end;}/** Returns if there is any word in the trie that starts with the given prefix. */bool startsWith(string word) {auto p = root;for (auto c : word) {int u = c - 'a';if (!p->son[u]) return false;p = p->son[u];}return true;}
};

• Java

public class Trie {private class Node{public boolean isWord;public Node[] next;public Node(boolean isWord){this.isWord = isWord;next = new Node[26];}public Node(){this(false);}}private Node root;public Trie(){root = new Node();}// 向Trie中添加一个新的单词wordpublic void insert(String word){Node cur = root;for(int i = 0 ; i < word.length() ; i ++){char c = word.charAt(i);if(cur.next[c-'a'] == null)cur.next[c-'a'] = new Node();cur = cur.next[c-'a'];}cur.isWord = true;}// 查询单词word是否在Trie中public boolean search(String word){Node cur = root;for(int i = 0 ; i < word.length() ; i ++){char c = word.charAt(i);if(cur.next[c-'a'] == null)return false;cur = cur.next[c-'a'];}return cur.isWord;}// 查询是否在Trie中有单词以prefix为前缀public boolean startsWith(String isPrefix){Node cur = root;for(int i = 0 ; i < isPrefix.length() ; i ++){char c = isPrefix.charAt(i);if(cur.next[c-'a'] == null)return false;cur = cur.next[c-'a'];}return true;}
}

Leetcode 0211 添加与搜索单词

问题描述

• 问题链接：Leetcode 0211 添加与搜索单词

  

分析

• 插入不变，查询的时候遇到字母正常处理，遇到通配符直接暴搜。

代码

• C++

/*** 执行用时：156 ms, 在所有 C++ 提交中击败了48.30%的用户* 内存消耗：103.1 MB, 在所有 C++ 提交中击败了13.41%的用户*/
class WordDictionary {
public:struct Node {bool is_end;Node *son[26];Node() {is_end = false;for (int i = 0; i < 26; i++)son[i] = NULL;}} *root;/** Initialize your data structure here. */WordDictionary() {root = new Node();}void addWord(string word) {auto p = root;for (auto c : word) {int u = c - 'a';if (!p->son[u]) p->son[u] = new Node();p = p->son[u];}p->is_end = true;}bool search(string word) {return dfs(root, word, 0);}// 返回以p为根的trie树中是否存在字符串word[i...)bool dfs(Node *p, string word, int i) {if (i == word.size()) return p->is_end;if (word[i] != '.') {int u = word[i] - 'a';if (!p->son[u]) return false;return dfs(p->son[u], word, i + 1);} else {for (int j = 0; j < 26; j++)if (p->son[j] && dfs(p->son[j], word, i + 1))return true;return false;}}
};

• Java

public class WordDictionary {private class Node {public boolean isWord;public TreeMap<Character, Node> next;public Node(boolean isWord) {this.isWord = isWord;next = new TreeMap<>();}public Node() {this(false);}}private Node root;/*** Initialize your data structure here.*/public WordDictionary() {root = new Node();}/*** Adds a word into the data structure.*/public void addWord(String word) {Node cur = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);if (cur.next.get(c) == null)cur.next.put(c, new Node());cur = cur.next.get(c);}cur.isWord = true;}/*** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.*/public boolean search(String word) {return match(root, word, 0);}// 在以node为根节点的字典树中查找是否存在单词word，index表示匹配到第几个字符private boolean match(Node node, String word, int index) {if (index == word.length())return node.isWord;char c = word.charAt(index);if (c != '.') {if (node.next.get(c) == null)return false;return match(node.next.get(c), word, index + 1);} else {  // c == '.'for (char nextChar : node.next.keySet())if (match(node.next.get(nextChar), word, index + 1))return true;return false;}}
}

Leetcode 0676 实现一个魔法字典

问题描述

• 问题链接：Leetcode 0676 实现一个魔法字典

  

分析

• 首先将所有单词都插入到trie树中，然后可以暴搜是否存在只有一个字母不同的单词，注意剪枝。

代码

• C++

const int N = 10010;int son[N][26], idx;
bool is_end[N];class MagicDictionary {
public:void insert(string &s) {int p = 0;for (auto c : s) {int u = c - 'a';if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}is_end[p] = true;}/** Initialize your data structure here. */MagicDictionary() {memset(son, 0, sizeof son);idx = 0;memset(is_end, 0, sizeof is_end);}void buildDict(vector<string> dictionary) {for (auto &s : dictionary) insert(s);}// p: 在trie中的节点编号；u: 当前字符串的下标；c: 当前有多少字符不相同bool dfs(string &s, int p, int u, int c) {if (is_end[p] && u == s.size() && c == 1) return true;if (c > 1 || u == s.size()) return false;for (int i = 0; i < 26; i++) {if (!son[p][i]) continue;if (dfs(s, son[p][i], u + 1, c + (s[u] - 'a' != i)))return true;}return false;}bool search(string searchWord) {return dfs(searchWord, 0, 0, 0);}
};

• Java

class MagicDictionary {public static final int N = 10010;int[][] son = new int[N][26];int idx;boolean[] isEnd = new boolean[N];public MagicDictionary() {for (int i = 0; i < N; i++) Arrays.fill(son[i], 0);idx = 0;Arrays.fill(isEnd, false);}private void insert(String s) {int p = 0;for (char c : s.toCharArray()) {int u = c - 'a';if (son[p][u] == 0) son[p][u] = ++idx;p = son[p][u];}isEnd[p] = true;}public void buildDict(String[] dictionary) {for (String s : dictionary) insert(s);}private boolean dfs(char[] s, int p, int u, int c) {if (isEnd[p] && c == 1 && u == s.length) return true;if (c > 1 || u == s.length) return false;for (int i = 0; i < 26; i++) {if (son[p][i] == 0) continue;if (dfs(s, son[p][i], u + 1, c + (s[u] - 'a' != i ? 1 : 0)))return true;}return false;}public boolean search(String searchWord) {return dfs(searchWord.toCharArray(), 0, 0, 0);}
}

Leetcode 0677 键值映射

问题描述

• 问题链接：Leetcode 0677 键值映射

  

分析

• 每个节点可以存储两个信息，一个是当前节点的权值，另外一个是该节点为根的前缀树的权值和。

代码

• C++

const int N = 2510;int son[N][26], idx;
int V[N], S[N];  // V存储当前节点的权值，S存储以该节点为根的前缀树的权值和/*** 执行用时：4 ms, 在所有 C++ 提交中击败了79.83%的用户* 内存消耗：7.7 MB, 在所有 C++ 提交中击败了93.28%的用户*/
class MapSum {
public:// value: 现在插入的值；last: 旧值，如果不存在则为0void add(string &s, int value, int last) {int p = 0;for (auto c : s) {int u = c - 'a';if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];S[p] += value - last;}V[p] = value;}int query(string &s) {int p = 0;for (auto c : s) {int u = c - 'a';if (!son[p][u]) return 0;p = son[p][u];}return p;}/** Initialize your data structure here. */MapSum() {memset(son, 0, sizeof son);idx = 0;memset(V, 0, sizeof V);memset(S, 0, sizeof S);}void insert(string key, int val) {add(key, val, V[query(key)]);}int sum(string prefix) {return S[query(prefix)];}
};

• Java

class MapSum {public static final int N = 2510;int[][] son = new int[N][26];int[] V = new int[N], S = new int[N];  // V存储当前节点的权值，S存储以该节点为根的前缀树的权值和int idx;void add(String s, int value, int last) {int p = 0;for (char c : s.toCharArray()) {int u = c - 'a';if (son[p][u] == 0) son[p][u] = ++idx;p = son[p][u];S[p] += value - last;}V[p] = value;}int query(String s) {int p = 0;for (char c : s.toCharArray()) {int u = c - 'a';if (son[p][u] == 0) return 0;p = son[p][u];}return p;}/** Initialize your data structure here. */public MapSum() {for (int i = 0; i < N; i++) Arrays.fill(son[i], 0);idx = 0;Arrays.fill(V, 0);Arrays.fill(S, 0);}public void insert(String key, int val) {add(key, val, V[query(key)]);}public int sum(String prefix) {return S[query(prefix)];}
}