当前位置：首页 > news >正文

【基础算法练习】Trie 树

news 来源：原创 2024/5/20 22:02:15

文章目录

模板题：[ACwing 835. Trie字符串统计](https://www.acwing.com/problem/content/description/837/)
- 题目描述
- 代码与解题思路
模板题：[ACwing 143. 最大异或对](https://www.acwing.com/problem/content/145/)
- 题目描述
- 代码与解题思路
Trie 算法需要注意的点
- Trie 树的构建和算法思想的理解：
- Trie 树的算法模板

模板题：ACwing 835. Trie字符串统计

题目描述

代码与解题思路

#include <iostream>using namespace std;const int N = 100010;int son[N][26], cnt[N], idx;char str[N];void insert(char str[])
{   int p = 0; // 从第一个节点开始遍历for (int i = 0; str[i] != 0; i++) {int u = str[i] - 'a';// p 表示第几个节点, u 表示的是哪个字母// 如果 son 为 0 就新建节点, 如果 son 不为 0 就证明存在这个节点if (son[p][u] == 0) son[p][u] = ++idx;// 令 p 指向子节点（下一个节点）p = son[p][u];}// 以 p 这个节点为结尾的字符串数量 + 1cnt[p]++;
}int query(char str[])
{int p = 0;for (int i = 0; str[i] != 0; i++) {int u = str[i] - 'a';// 这个字符串不存在if (son[p][u] == 0) return 0;// 令 p 指向子节点p = son[p][u];}// 返回这个字符串存在的个数return cnt[p];
}int main()
{int n;cin >> n;while (n--) {char ch;cin >> ch >> str;if (ch == 'I') insert(str);else cout << query(str) << endl;}return 0;
}

模板题：ACwing 143. 最大异或对

题目描述

代码与解题思路

#include <isotream>
#include <algorithm>uisng namespace std;const int N = 100010, M = 3000000;int n;
int son[M][2], idx;
int a[N]void insert(int x) {int p  = 0; for (int i = 30; i >= 0; i--) {// 现在 s 是 son[p][x >> i & 1] 的引用, 写 s 就等于写 son[p][x >> i & 1]int& s = son[p][x >> i & 1]; // 新建节点if (s == 0) s = ++idx;// 令 p 指向子节点p = s;}
}int query(int x) {int res = 0, p = 0;for (int i = 30; i >= 0; i--) {int s = x >> i & 1;if (son[p][!s] != 0) { // 相异就累加res += 1 << i;p = son[p][!s];}else p = son[p][s]; // 相同就跳过}return res;
}int main()
{cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];insert(a[i]); // 构建 Trie 树}int res = 0;for (int i = 0; i < n; i++) res = max(res, query(a[i]));cout << res << endl;return 0;
}

Trie 算法需要注意的点

Trie 树的构建和算法思想的理解：

Trie 树的算法模板

注释详解版本

const int N = 100010;int son[N][26], cnt[N], idx; // 节点数组、计数数组、数组容量下标char str[N]; // 字符串数组// 插入字符串
void insert(char str[]) {   int p = 0; // 从第一个节点开始遍历for (int i = 0; str[i] != 0; i++) {int u = str[i] - 'a';// p 表示第几个节点, u 表示的是哪个字母// 如果 son 为 0 就新建节点, 如果 son 不为 0 就证明存在这个节点if (son[p][u] == 0) son[p][u] = ++idx;// 令 p 指向子节点（下一个节点）p = son[p][u];}// 以 p 这个节点为结尾的字符串数量 + 1cnt[p]++;
}int query(char str[]) {int p = 0;for (int i = 0; str[i] != 0; i++) {int u = str[i] - 'a';// 这个字符串不存在if (son[p][u] == 0) return 0;// 令 p 指向子节点p = son[p][u];}// 返回这个字符串存在的个数return cnt[p];
}

无注释纯享版

int son[N][26], cnt[N], idx;
char str[N]; void insert(char str[]) {   int p = 0; for (int i = 0; str[i] != 0; i++) {int u = str[i] - 'a';if (son[p][u] == 0) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;
}int query(char str[]) {int p = 0;for (int i = 0; str[i] != 0; i++) {int u = str[i] - 'a';if (son[p][u] == 0) return 0;p = son[p][u];}return cnt[p];
}