Trie 学习笔记

Trie 也称字典树，指可以储存多个字符串的有根树。Trie 树的每一条边对应一个字符，每一个顶点代表从根到该结点经过的字符边按顺序连接的字符串。我们也可以称顶点为状态，边为转移。

性质

任意一个结点到根结点所代表的字符串都是实际字符串集合中某些串的前缀。特别地，根结点代表空集。

Trie 利用了串的公共前缀，不仅节约了空间，也方便了插入与查询。

原理

我们定义 ch 是一个二维数组，其中第一维为结点编号，第二维为转移边，ch[u][i] 表示结点 u 通过 i 字符指向（到达）的结点。定义 tot 为结点总数。

插入字符串的步骤：

1. 定义指针 u 指向根结点，从根结点开始匹配；

2. 如果当前结点存在指向下一个字符的边（ch[u][c] != 0） ，则此字符已插入，继续匹配下一个字符（u = ch[u][c]）；

3. 如果当前结点不存在指向下一个字符的边（ch[u][c] == 0），插入此字符（ch[u][c] = ++tot），继续插入下一个字符（u = ch[u][c]）；

4. 如果字符串完成匹配（插入），标记此结点为顶点。

查询字符串是否为字符串集合中某个串的前缀（与插入的思路是一样的）：

1. 定义指针 u 指向根结点，从根结点开始匹配；

2. 如果字符存在（ch[u][c] != 0） ，继续匹配下一个字符（u = ch[u][c]）；

3. 如果字符不存在（ch[u][c] == 0），返回 false；

4. 完成匹配，返回 true。

实现

int tot;
int ch[1000][100];
bool flag[100005];

void insert(char *s) {
	int len = strlen(s);
	int u = 1; // 定义根结点编号为 1
	for (int i = 0; i < len; i++) {
		int c = s[i] - 'a'; // 假设字符串只有小写字母
		if (!ch[u][c]) ch[u][c] = ++tot;
		u = ch[u][c];
	}
	flag[u] = true; // 结尾标记
}

bool query(char *s) {
	int len = strlen(s);
	int u = 1;
	for (int i = 0; i < len; i++) {
		int c = s[i] - 'a';
		if (!ch[u][c]) return false;
		u = ch[u][c];
	}
	return true;
}