数据结构·字典树

字典树trie

顾名思义，在一个字符串的集合里查询某个字符串是否存在树形结构。
树存储方式上用的是结构体数组，类似满二叉树的形式。

模板

定义结构体和trie

• 结构体必须的内容：当前结点的字符，孩子数组
• 可选：end用于查询，repeat用于统计。

typedef struct node {char c;int children[30] = {0};int end = 0, repeat = 0;
};
vector<node>trie;
node root;
trie.push_back(root);

建树三部曲

• 不好理解的可能就是这个fa，用于表示当前的父节点是谁。
• 查询结点是否存在于父节点的孩子中：if (!trie[fa].children[idx])

• 没有存在则添加结点：创建新下标int new_idx = trie.size()，父节点的孩子添加该下标。

			int new_idx = trie.size();trie[fa].children[idx] = new_idx;node x;x.c = s[i];if (i == s.size() - 1) {x.end = 1;}trie.push_back(x);

• 父节点变为子节点：fa = trie[fa].children[idx]

void build(string s) {int fa = 0;for (int i = 0; i < s.size(); i++) {int idx = s[i] - 'a';if (!trie[fa].children[idx]) {int new_idx = trie.size();trie[fa].children[idx] = new_idx;node x;x.c = s[i];if (i == s.size() - 1) {x.end = 1;}trie.push_back(x);fa = new_idx;}else {if (i == s.size() - 1) {trie[fa].end = 1;}fa = trie[fa].children[idx];}}
}

字符串的查询

• 从父亲结点一直遍历到叶子结点，最后i==s.size()-1时特判end是否为end==true?即可
• 与建树过程几乎完全一致

void query(string s) {int fa = 0;for (int i = 0; i < s.size(); i++) {int idx = s[i] - 'a';if (!trie[fa].children[idx]) {cout << "WRONG" << endl;return;}else {fa = trie[fa].children[idx];if (i == s.size() - 1) {if (trie[fa].repeat) {cout << "REPEAT" << endl;}else {if (trie[fa].end) {trie[fa].repeat = 1;cout << "OK" << endl;}else cout << "WRONG" << endl;}}}}
}

打印字典树

void print_trie() {for (int i = 0; i < trie.size(); i++) {cout << trie[i].c << "|";for (int j = 0; j < 30; j++) {if (trie[i].children[j])cout << trie[i].children[j] << " ";}cout << "|" << trie[i].end << "|" << trie[i].repeat<<endl;}
}

应用

• P2580 于是他错误的点名开始了:标准的查询字符串操作。

0-1字典树

• 将数字用二进制形式保存在trie中，一般是高位到低位。配合贪心思想，可以节约查询操作。

• P4551 最长异或路径：这里需要用的异或的自反性质:自己跟自己异或不影响计算。当i<j,$[1,i]\oplus [1,j]=[i,j]$,$[i,j]$表示i到j的异或路径。现在这个问题就变成了先获得[1,i]，然后再遍历每个j，计算$[1,i]\oplus [1,j]$的最大值。时间复杂度为平方。将这些[1,i]结果保存为字典树，然后利用贪心从高位到低位选择最大的异或结果即可！

• 注意bitset<int>val这个库，接受字符串和整型作为构造函数。一定要注意的是遍历时：从低位到高位遍历，val[0]表示从右往左第一位(也就是低位)。for (int i = bitval.size() - 1; i >= 0; i--)

#include<bits/stdc++.h>
#define MAX_VALUE 1000009
#define mod 1000007
using ll = long long;
using namespace std;
typedef struct node {int x, w;node(int a, int b) :x(a), w(b) {};
};
typedef struct trie_node {int val, children[2] = { 0 };
};
vector<list<node>>graph(100009, list<node>());
int n, u, v, w, xors[100009], ans = INT_MIN;
vector<trie_node>trie;
void dfs(int st, int val) {xors[st] = val;for (auto item : graph[st]) {dfs(item.x, val ^ item.w);}
}
void build(int val) {int fa = 0;bitset<32>bitval(val);//bitset[0]是指第一位for (int i = bitval.size() - 1; i >= 0; i--) {//cout << "val:"<<val<<" i:"<<i<<" bitval[i]:" << bitval[i] << endl;if (!trie[fa].children[bitval[i]]) {int new_idx = trie.size();trie[fa].children[bitval[i]] = new_idx;trie_node x;x.val = bitval[i];trie.push_back(x);fa = new_idx;}else {fa = trie[fa].children[bitval[i]];}}
}
int query(int val) {int fa = 0;bitset<32>bitval(val);//二进制bitset<32>res;//bitset[0]是指第一位for (int i = bitval.size() - 1; i >= 0; i--) {if (trie[fa].children[!bitval[i]]) {//取反fa = trie[fa].children[!bitval[i]];res[i] = 1;}else {fa = trie[fa].children[bitval[i]];res[i] = 0;}}return (int)res.to_ulong();
}
void printout() {for (int i = 0; i < trie.size(); i++) {cout << trie[i].val << "|";for (int j = 0; j < 2; j++) {if (trie[i].children[j])cout << trie[i].children[j] << " ";}cout << "|" << endl;}
}
void solve() {cin >> n;for (int i = 1; i < n; i++) {cin >> u >> v >> w;graph[u].push_back(node(v, w));}dfs(1, 0);//for (int i = 1; i <= n; i++) {//	cout << xors[i] << " ";//}//cout << endl;trie_node root;trie.push_back(root);for (int i = 1; i <= n; i++) {build(xors[i]);}//printout();for (int i = 1; i <= n; i++) {ans = max(ans, query(xors[i]));}cout << ans;}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();return 0;
}

• P6824 「EZEC-4」可乐：这里x是有最大值的，暴力方法是对于每一个x都进行异或看看是否满足条件，时间复杂度为平方。利用a[i]构造0-1trie，可以在位级别，加速判断。对于第i位，如果k[i]为1，只需要找到与x[i]相同数字的结点，就一定可以知道x与该结点下的a[i]满足条件。如果k[i]=0，需要找到与x[i]相同数字的结点，否则一定不能与该父节点下的a[i]满足条件，提前结束。这里也是用由高位到低位的贪心思想。

#include<bits/stdc++.h>
#define MAX_VALUE 1000009
#define mod 1000007
using ll = long long;
using namespace std;
int n, k, a[1000009],res=INT_MIN;
typedef struct node {int val, children[2] = {0}, repeat = 1;
};
vector<node>trie;
void build(int val) {bitset<32>bitval(val);int fa = 0;for (int i = bitval.size() - 1; i >= 0; i--) {if (!trie[fa].children[bitval[i]]) {int new_idx = trie.size();trie[fa].children[bitval[i]] = new_idx;node x;x.val = bitval[i];trie.push_back(x);fa = new_idx;}else {int idx = trie[fa].children[bitval[i]];fa = idx;trie[idx].repeat++;}}
}
void printout() {for (int i = 0; i < trie.size(); i++) {cout << trie[i].val << "|";for (int j = 0; j < 2; j++) {if(trie[i].children[j])cout << trie[i].children[j] << " ";}cout << "|" << trie[i].repeat << endl;}
}
int query(int val,int k) {int ans = 0;bitset<32>bitval(val);bitset<32>bitk(k);int fa = 0;for (int i = bitval.size() - 1; i >= 0; i--) {if (bitk[i]) {//bitk[i]==1if (trie[fa].children[bitval[i]]) {//xor can be 0int idx = trie[fa].children[bitval[i]];//cout << bitval[i] << " "<<trie[idx].repeat << endl;ans += trie[idx].repeat;}if (trie[fa].children[!bitval[i]]) {fa = trie[fa].children[!bitval[i]];}else {break;}}else {//bitk[i]==0if (trie[fa].children[bitval[i]]) {fa = trie[fa].children[bitval[i]];if (i == 0) {ans += 1;//最后一个结点//cout << "end:" << 1 << endl;}}else break;}}return ans;
}
void solve() {node root;trie.push_back(root);cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];build(a[i]);}//printout();for (int i = 0; i <= (1<<20); i++) {res = max(res, query(i, k));}cout << res;//cout<<query(0, k);
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);solve();return 0;
}