资讯详情

Trie 是什么

实际上它就是一颗像字典的树，支持插入单词和查询单词个数等操作。

它的边权是某个字符。

比如上图，插入单词 aca 时，我们就可以在 \(5\) 号节点下新建一个节点，边权为 a。而查询是否单词 abs 时，答案为是，因为存在路径 \(1 \to 2 \to 3 \to 4\) 的边权为 abs。

Trie 的实现

插入 & 删除

插入：对于已有的位置，我们直接就可以在原有基础上加；否则就新建一个节点。

删除同理。

// cnt[u]：1 -> u 这条路径以前有几次走过（记录路径对应单词个数）
// trie[u][x]：节点 u 的孩子中，对应边权为 x 的节点编号
void insert(string s){int u = 0;for(int i = 0; i < s.size(); i++){if(!trie[u][s[i] - 'a' + 1]){ // 没有下一个对应节点，新建一个c++;trie[u][s[i] - 'a' + 1] = c;}u = trie[u][s[i] - 'a' + 1]; // 到下一个对应节点cnt[u]++; // 将当前节点的权值 + 1}
}
void del(string s){int u = 0;for(int i = 0; i < s.size(); i++){u = trie[u][s[i] - 'a' + 1]; // 到下一个对应节点cnt[u]--; // 将当前节点的权值 - 1}
}

查询个数

这个过程很像插入，但是如果没有下一个对应节点就说明这个单词不存在，直接返回 \(0\)；否则答案为最后一个节点的权值。

void insert(string s){int u = 0;for(int i = 0; i < s.size(); i++){if(!trie[u][s[i] - 'a' + 1]) return 0; // 没有下一个对应节点，也就没有对应单词u = trie[u][s[i] - 'a' + 1]; // 到下一个对应节点}return cnt[u];
}

Trie 的应用

在一些需要求解相同前 / 后缀个数、查找一个字符串是否出现过 / 出现次数时可以用到，但是很少会单独用它。

AC 自动机要用，但我不会。

变式：01 Trie

这个东西就相对常用了。顾名思义，01Trie 就是只维护 \(0\) 和 \(1\) 的 Trie。

看到 \(0\) 和 \(1\)，很自然地会想到二进制。我们可以以 01Trie 维护最小 / 大异或值一类问题。

实现大体是一样的，直接贴代码吧。

void insert(ll s){ll u = 0;for(int i = 29; i >= 0; i--){bool x = (s >> i) & 1;if(!zotrie[u][x]){c++;zotrie[u][x] = c;}u = zotrie[u][x];cnt[u]++;}
}
void del(ll s){ll u = 0;for(int i = 29; i >= 0; i--){bool x = (s >> i) & 1;u = zotrie[u][x];cnt[u]--;}
}
ll querymax(ll s){ll ans = 0, u = 0;for(int i = 29; i >= 0; i--){bool x = (s >> i) & 1;ans <<= 1;if(cnt[zotrie[u][!x]]){ // 取反是因为异或最大当然要优先不同位位数最高ans++;u = zotrie[u][!x];}else u = zotrie[u][x];}return ans;
}
ll querymin(ll s){ll ans = 0, u = 0;for(int i = 29; i >= 0; i--){bool x = (s >> i) & 1;ans <<= 1;if(cnt[zotrie[u][x]]){ // 不取反同理u = zotrie[u][x];}else{ans++;u = zotrie[u][!x];}}return ans;
}