[数据结构与算法]数据结构：Tire树--高效的字符串匹配结构

??Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

给定如下单词：abc、abd、cbd、ccce、bcda、ccc
Tire树的结构大致如下：

那它是如何构造的呢？
?? 首先从根节点开始我们要存放单词abc，判断根节点是否有存放着字母 a 的子节点，如果没有就增加一个节点将a存进去；接着在 a 节点判断 a 节点是否有存放字母 b 的子节点，同样的没有就新增一个节点用来存放 b ，c也同理。
??接下来存放abd，存放完一个单词后指针要回到根节点重新移动。字母 a 显然已经有了，指针直接移到该节点；接着看 b ，也有了继续移动；存放字母 d 的时候发现b节点没有子节点存放d那就新增一个存放字母d，这样第二个单词也存放完成了。
??那我们查找的时候怎么知道单词的结束位置呢？很简单在存放的时候，当存放结束时将最后一个节点做标记即可，同个这样标记我们还可以非常快速的得到一个单词总共出现了几次。

接下来看一个题目巩固一下：https://www.acwing.com/problem/content/837/
??题目目的很明确就是要将单词插入然后询问某些单词出现了几次：
??代码实现方面一般可以用 指针链表的形式实现，我偷个懒用数组模拟指针实现了：

#include<iostream>
using namespace std;

const int N = 100007;
int Tire[N][26];
int cnt[N], index;//cnt数组用来标记单词的结尾，存放出现的次数，index用来模拟指针
char s[N];

void insert(char str[]) {//插入操作
	int p = 0;
	for (int i = 0; str[i]; i++) {
		int id = str[i] - 'a';
		if (!Tire[p][id]) {//如果没有这个节点就增加
			Tire[p][id] = ++index;
		}
		p = Tire[p][id];
	}
	cnt[p]++;
}

int Query(char str[]) {//查询操作
	int p = 0;
	for (int i = 0; str[i]; i++) {
		int id = str[i] - 'a';
		if (!Tire[p][id]) return 0;
		p = Tire[p][id];
	}
	return cnt[p];//返回出现的次数
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		char op[2];
		cin >> op >> s;
		if (op[0] == 'I') insert(s);
		else cout << Query(s) << '\n';
	}
	return 0;
}

可以尝试用指针实现以下。
下面又是一道变形题：https://www.acwing.com/problem/content/description/145/
直接贴代码：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int Tire[N * 31][2], cnt[N * 31];
int id = 0;

void insert(int x) {//插入一个数
	int p = 0;
	for (int i = 30; i >= 0; i--) {
		int t = (x >> i) & 1;//获得第i + 1位的二进制位

		if (!Tire[p][t]) Tire[p][t] = ++id;//没有就开一个新节点
		p = Tire[p][t];
	}
	cnt[p]++;//结尾标记
}
int Query(int x) {
	int p = 0;
	int res = 0;
	for (int i = 30; i >= 0; i--) {
		//从高位开始找
		int t = (x >> i) & 1;
		//如果这个数字的第i + 1 位相反的二进制位存在（!t）就取出来 否则按照x走
		if (Tire[p][!t]) t = !t;

		res = (res << 1) + t;
		p = Tire[p][t];
		
	}
	return res^x;
}
int main() {
	int n, x;
	int maxAns = 0;
	cin >> n;
	while (n--) {
		cin >> x;
		insert(x);
		maxAns = max(maxAns, Query(x));
	}
	cout << maxAns;
	return 0;
}