Trie树 - 知识点梳理

介绍

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;
}