介绍
Trie 树，又名字典树，顾名思义就是为多个字符串的存贮与查找而生的，和现实中的字典差不多，其实就是一种字符查找自动机。通过对被查找串预处理，梳理为树形结构，在每次查找 \(S\) 时复杂度可以达到 \(O(|S|)\)（而朴素查找复杂度为 \(O(|S| + \sum_i |t_i|)\)），且占的空间比单独存贮字符串通常要小。
实现方法
朴素情况下，我们查找字符串时会与每个字符串进行比较，从第一个字符开始，然后比较第二个，依次往后。如果我们把每个字符串抽象成一条链，查找时我们就是从链头依次往后走，看能不能走到头。（其实一条链就是一个简易的 Trie 树）
而如果是有多个被匹配串，朴素的做法是逐个匹配，也就是在每个链上都跑一遍。
注意到这样我们每次匹配时同个匹配串走的路径是相同的。
于是我们可以把相同前缀的被匹配串的前缀节点合并，这就形成了一棵树。
每次插入时我们顺着已有的路往下走，若没有路了再新建节点。
注意我们需要在链的末尾进行标记，表示有被匹配串以该节点结尾。
这样查找时我们按照查找串的路线往下走，如果能走到底而且尾部节点有标记就表明存在相同的被查找串。
这样就解决了问题。
上代码！ （这里使用了递归的写法，简单快捷）
const int MAXN = 500005;
int s[MAXN][27], n, m, cnt, col[MAXN]; // s: 儿子节点 cnt: 栈顶指针 col: 节点标记
int insert (int cur, const char *str, int len, int ind) { // cur: 当前节点编号 str: 插入的被查找串 len: 被查找串长度 ind: 当前下标
if (!cur) cur = ++cnt;
if (ind < len) {
s[cur][str[ind]-'a'] = insert(s[cur][str[ind]-'a'], str, len, ind + 1);
}
else col[cur] = 1;
return cur;
}
bool find (int cur, const char *str, int len, int ind) {
if (!cur) return false;
if (len == ind) return col[cur];
return find (s[cur][str[ind]-'a'], str, len, ind + 1);
}
例题
超级无敌大板子 Luogu P2580 于是他错误的点名开始了
直接套板子即可。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int s[MAXN][27], n, m, cnt, col[MAXN]; // s: 儿子节点 cnt: 栈顶指针 col: 节点标记
int insert (int cur, const char *str, int len, int ind) { // cur: 当前节点编号 str: 插入的被查找串 len: 被查找串长度 ind: 当前下标
if (!cur) cur = ++cnt;
if (ind < len) {
s[cur][str[ind]-'a'] = insert(s[cur][str[ind]-'a'], str, len, ind + 1);
}
else col[cur] = 1;
return cur;
}
bool find (int cur, const char *str, int len, int ind) {
if (!cur) return false;
if (len == ind) return col[cur];
return find (s[cur][str[ind]-'a'], str, len, ind + 1);
}
int root1, root2;
char tmp[55];
int main () {
root1 = ++cnt;
root2 = ++cnt;
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> tmp;
insert(root1, tmp, strlen(tmp), 0);
}
cin >> m;
for (int i = 1;i <= m;i++) {
cin >> tmp;
if (!find (root1, tmp, strlen(tmp), 0)) cout << "WRONG" << endl;
else if (!find(root2, tmp, strlen(tmp), 0)) cout << "OK" << endl, insert(root2, tmp, strlen(tmp), 0);
else cout << "REPEAT" << endl;
}
return 0;
}