算法基础-字典树

1.字典树的概念

2.字典树的作⽤

3.字典树的实现

准备⼯作：

#include <iostream> #include <cstring> using namespace std; const int N = 1e6 + 10; int tree[N][26], p[N], e[N]; int idx;

插⼊字符串：

void insert(string& s) { int cur = 0; // 从根结点开始 p[cur]++; // 这个格⼦经过⼀次 for(auto ch : s) { int path = ch - 'a'; // 如果没有路 if(tree[cur][path] == 0) tree[cur][path] = ++idx; cur = tree[cur][path]; p[cur]++; } e[cur]++; }

查询字符串出现的次数：

int find(string& s) { int cur = 0; for(auto ch : s) { int path = ch - 'a'; if(tree[cur][path] == 0) return 0; cur = tree[cur][path]; } return e[cur]; }

查询有多少个单词以字符串s为前缀：

int find_pre(string& s) { int cur = 0; for(auto ch : s) { int path = get_num(ch); if(tree[cur][path] == 0) return 0; cur = tree[cur][path]; } return p[cur]; }

4.1【模板】字典树

题目描述

给定 n 个模式串 s1​,s2​,…,sn​ 和 q 次询问，每次询问给定一个文本串 ti​，请回答 s1​∼sn​ 中有多少个字符串 sj​ 满足 ti​ 是 sj​ 的前缀。

一个字符串 t 是 s 的前缀当且仅当从 s 的末尾删去若干个（可以为 0 个）连续的字符后与 t 相同。

输入的字符串大小敏感。例如，字符串Fusu和字符串fusu不同。

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数，表示数据组数 T。

对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 n 和询问的个数 q。
接下来 n 行，每行一个字符串，表示一个模式串。
接下来 q 行，每行一个字符串，表示一次询问。

输出格式

按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。

输入输出样例

输入 #1复制

3 3 3 fusufusu fusu anguei fusu anguei kkksc 5 2 fusu Fusu AFakeFusu afakefusu fusuisnotfake Fusu fusu 1 1 998244353 9

输出 #1复制

2 1 0 1 2 1

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤T,n,q≤105，且输入字符串的总长度不超过 3×106。输入的字符串只含大小写字母和数字，且不含空串。

说明

std 的 IO 使用的是关闭同步后的 cin/cout，本题不卡常。

【解法】

【参考代码】

#include <iostream> #include <string> #include <cstring> using namespace std; const int N = 3e6 + 10; // 字典树节点最大数量（根据数据范围设定） int tr[N][62]; // 字典树：tr[节点][字符编号] = 子节点编号 int p[N]; // p[节点]：以该节点为前缀的模式串数量 int idx; // 字典树节点计数器（初始为0，根节点是0） // 将字符映射为0-61的编号（区分大小写字母+数字） int get_num(char ch) { if (ch >= 'a' && ch <= 'z') { return ch - 'a'; // 小写字母：0-25 } else if (ch >= 'A' && ch <= 'Z') { return ch - 'A' + 26; // 大写字母：26-51 } else { return ch - '0' + 52; // 数字：52-61 } } // 插入模式串到字典树中 void insert(string& s) { int cur = 0; // 从根节点开始 p[cur]++; // 根节点是所有字符串的前缀，计数+1 for (char ch : s) { int path = get_num(ch); // 获取当前字符的编号 if (tr[cur][path] == 0) { // 若该字符的子节点不存在，新建节点 tr[cur][path] = ++idx; } cur = tr[cur][path]; // 移动到子节点 p[cur]++; // 该节点的前缀计数+1 } } // 查询文本串s作为前缀的模式串数量 int find_pre(string& s) { int cur = 0; // 从根节点开始 for (char ch : s) { int path = get_num(ch); if (tr[cur][path] == 0) { // 路径中断，无匹配的前缀 return 0; } cur = tr[cur][path]; // 移动到子节点 } return p[cur]; // 返回最终节点的前缀计数 } int main() { ios::sync_with_stdio(false); // 加速cin/cout cin.tie(nullptr); int T; cin >> T; while (T--) { // 处理多组测试数据 // 清空字典树（只清空用到的节点，避免memset超时） for (int i = 0; i <= idx; i++) { memset(tr[i], 0, sizeof(tr[i])); // 清空当前节点的所有子节点 p[i] = 0; // 清空计数 } idx = 0; // 重置节点计数器 int n, q; cin >> n >> q; // 插入n个模式串 while (n--) { string s; cin >> s; insert(s); } // 处理q次查询 while (q--) { string s; cin >> s; cout << find_pre(s) << '\n'; } } return 0; }

4.2于是他错误的点名开始了

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛 CON900）。

题目描述

这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

输入格式

第一行一个整数 n，表示班上人数。

接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。

第 n+2 行一个整数 m，表示教练报的名字个数。

接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 50）。

输出格式

对于每个教练报的名字，输出一行。

如果该名字正确且是第一次出现，输出OK，如果该名字错误，输出WRONG，如果该名字正确但不是第一次出现，输出REPEAT。

输入输出样例

输入 #1复制

5 a b c ad acd 3 a a e

输出 #1复制

OK REPEAT WRONG

说明/提示

• 对于 40% 的数据，n≤1000，m≤2000。
• 对于 70% 的数据，n≤104，m≤2×104。
• 对于 100% 的数据，n≤104，m≤105。

upd 2022.7.30：新增加一组 Hack 数据。

【解法】

【参考代码】

#include <iostream> #include <string> using namespace std; // 字典树最大节点数（根据实际数据量调整，5e5足够应对大部分场景） const int N = 5e5 + 10; // n：学生名字数量；m：点名查询次数 int n, m; // tr[i][j]：第i个节点的第j个小写字母（0-25）指向的子节点编号 // e[i]：节点状态（0=非名字结尾；>0=名字结尾且未查询；-1=名字结尾且已查询） int tr[N][26], e[N], idx; // 插入名字到字典树 void insert(string& s) { int cur = 0; // 从根节点（编号0）开始 for (auto ch : s) { // 遍历名字的每个字符 int path = ch - 'a'; // 小写字母映射为0-25的路径 if (tr[cur][path] == 0) { // 路径未创建则新建节点 tr[cur][path] = ++idx; } cur = tr[cur][path]; // 移动到子节点 } e[cur]++; // 标记该节点为名字结尾（初始为未查询状态） } // 查询名字状态：0=不存在；>0=首次查询；-1=重复查询 int find(string& s) { int cur = 0; // 从根节点开始 for (auto ch : s) { // 遍历查询名字的每个字符 int path = ch - 'a'; if (tr[cur][path] == 0) { // 路径不存在，名字不在名单中 return 0; } cur = tr[cur][path]; // 移动到子节点 } // 路径存在，判断节点状态 if (e[cur] > 0) { int t = e[cur]; e[cur] = -1; // 标记为已查询 return t; } return e[cur]; // 返回-1（重复查询） } int main() { // 优化输入输出速度（大数据量必备） ios::sync_with_stdio(false); cin.tie(nullptr); // 输入学生名字数量并插入所有名字 cin >> n; while (n--) { string s; cin >> s; insert(s); } // 输入查询次数并处理所有点名查询 cin >> m; while (m--) { string s; cin >> s; int ret = find(s); if (ret == 0) { cout << "WRONG" << endl; } else if (ret > 0) { cout << "OK" << endl; } else { cout << "REPEAT" << endl; } } return 0; }

4.3最⼤异或对

题目描述

给定 N 个整数 A1​.A2​,⋯,AN​ 中选出两个进行异或计算，得到的结果最大是多少？

输入格式

第一行一个整数 N，第二行 N 个整数 A1​.A2​,⋯,AN​。

输出格式

一个整数表示答案。

输入输出样例

输入 #1复制

3 1 2 3

输出 #1复制

3

说明/提示

对于所有测试数据，1≤N≤105，保证 0≤Ai​<231。

【解法】

【参考代码】

#include <iostream> using namespace std; const int N = 1e5 + 10; int n; int a[N]; // 字典树：每个数32位，1e5个数最多需要1e5*32个节点 int tr[N * 32][2], idx; // 插入数字x的二进制到字典树（从高位到低位） void insert(int x) { int cur = 0; for (int i = 31; i >= 0; i--) { // 取出x的第i位二进制值（0/1） int path = ((x >> i) & 1); // 路径不存在则新建节点 if (tr[cur][path] == 0) tr[cur][path] = ++idx; // 移动到子节点 cur = tr[cur][path]; } } // 找和x异或最大的数，返回异或结果 int find(int x) { int cur = 0; int ret = 0; for (int i = 31; i >= 0; i--) { int path = ((x >> i) & 1); // 优先走相反的位（贪心） if (tr[cur][path ^ 1]) { ret |= (1 << i); // 异或结果的第i位设为1 cur = tr[cur][path ^ 1]; } else { // 无相反位，走相同位 cur = tr[cur][path]; } } return ret; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; insert(a[i]); } int ret = 0; for (int i = 1; i <= n; i++) { ret = max(ret, find(a[i])); } cout << ret << endl; return 0; }