一、什么是 Trie树？
Trie树，也叫字典树，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
Trie树的本质就是利用字符串之间的公共前缀，将重复的前缀合并在一起。如下图。
Trie树的根节点不存数据，每个节点表示一个字符串的字符，从根节点到红色节点一条路径代表一个字符串。
二、如何实现一棵 Trie树。
1、存储 Trie树
我们假设存储的字符都是a~z，我们可以用一个数组大小26来存储字符，每一层每个字符都有26个子节点，数组的下标为存入下标的字符ASCII码值-a的ASCII码值，这样我们可以通过下标就可以知道该节点存储的是哪个字符。代码表示如下：
class TrieNode{
char data;
TrieNode children[26];
}
2、将字符串集合构造成 Trie 树
构造 Trie树，相当于把每个字符串插入到Trie树中。代码实现如下：
public class Trie {
private TrieNode root;
public Trie() {
// 树顶存储无意义字符
this.root = new TrieNode('/');
}
/**
* 插入字符串
*
* @param text 字符串
*/
public void insert(char[] text) {
TrieNode p = root;
int n = text.length;
for (int i = 0; i < n; i++) {
// 字符应该存储的数组下标
int idx = text[i] - 'a';
// 该字符在Trie树中不存在，将该字符插入到Trie树中
if (p.children[idx] == null) {
TrieNode newNode = new TrieNode(text[i]);
p.children[idx] = newNode;
}
// 继续存储下一个字符
p = p.children[idx];
}
// 存储完成后，修改结尾字符标识
p.isEndingChar = true;
}
}
class TrieNode {
public char data;
public TrieNode[] children;
public boolean isEndingChar;
public TrieNode(char data) {
this.data = data;
this.children = new TrieNode[26];
// 是否是字符串结尾字符
this.isEndingChar = false;
}
}
构建Trie树的过程，需要扫描所有的字符串，时间复杂度是O(n)，n表示所有字符串的长度和。
3、Tire树匹配字符串
在 Trie 树中，查找某个字符串，用代码实现如下：
/**
* 在 Trie 树中查找一个字符串
* @param pattern 模式串
* @return 是否存在
*/
public boolean find(char[] pattern) {
TrieNode p = root;
for (int i = 0; i < pattern.length; i++) {
int index = pattern[i] - 'a';
// 不存在 pattern
if (p.children[index] == null) {
return false;
}
// 存在继续往下找
p = p.children[index];
}
// ture 代表完全匹配，false 代表不能完全匹配，只是前缀
return p.isEndingChar;
}
从代码中可以看出Tire树的查找字符串，的时间复杂度为O(n)，n代表要查找的字符串的长度。如果不考虑构建tire树的操作，查询字符串，还是比较高效的。
三、Tire 树的优缺点和应场景
1、Tire树是非常耗内存的，拿空间换时间；如果字符串前缀重合不多，会导致空间消耗变大。
2、字符串包含的字符集不能太大。如果字符集太大，那存储空间可能会浪费很多。即便可以优化，但也要付出牺牲查询、插入的代价。
3、如果要用Trie树解决问题，要从零开始实现一个Trie树，还要保证没有bug，这个工程上是将简单问题复杂化，除非必须，一般不建议这样做。
4、Trie树中用到了指针，因为指针串起来的数据块是不连续的，所以对缓存并不友好，性能上会打个折扣。
综合以上几点，针对在一组字符串中查找字符串的问题，用散列表或者红黑树比较好。因为这两种数据结构，编程语言中现成类库都有，不需要自己实现。
Trie 树不适合精确匹配查找，它比较适合查找前缀匹配的字符串；比如搜索关键词的提示功能，我们用代码实现如下：
/**
* 查找匹配前缀所有字符串
*
* @param pattern 前缀
* @return 字符串集合
*/
public List<String> findPrefix(char[] pattern) {
TrieNode p = root;
// 找出前缀的结尾字符所在节点
for (int i = 0; i < pattern.length; i++) {
int idx = pattern[i] - 'a';
// 不存在，说明没有这个前缀的字符串
if (p.children[idx] == null) {
return null;
}
p = p.children[idx];
}
// 遍历节点p，把前缀是pattern都找出来
List<String> res = new ArrayList<String>();
iterateTrie(p, String.valueOf(pattern), res);
return res;
}
// 遍历
private void iterateTrie(TrieNode node, String str, List<String> res) {
TrieNode[] children = node.children;
// 遍历子节点
for (TrieNode child : children) {
// 如果当前子节点为空，直接跳到下一个子节点
if (child == null) continue;
// 拼接字符串
String temp = str + child.data;
// 如果当前子节点是结尾字符，把temp添加到res中
if (child.isEndingChar) {
res.add(temp);
}
// 继续往下递归
iterateTrie(child, temp, res);
}
}
四、扩展—经典多模式串匹配算法：AC自动机
网上有很多发表内容的网站，对于用户输入一些淫秽、反动、谩骂等敏感内容，会对进行过滤。
我们现在来学习一下，如何实现一个高性能的敏感词过滤系统呢？这里就需要用到多模式串匹配算法。
1、多模式串与单模式串匹配算法的区别
单模式匹配算法，是在一个模式串和主串之间进行匹配，也就是说，在一个主串中查找一个模式串。用单模式串算法来实现多模式串的匹配，要让每个模式串跟主串进行匹配，这会导致主串会被扫描多次；当主串特别长、模式串也很多时，这种处理就比较低效。
多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是上说，在一个主串中查找多个模式串。实现多模式串的匹配，它只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，大大提高了匹配效率。
2、AC自动机
AC自动机算法，全称是Aho-Corasick算法；AC自动机借鉴了单模式串的优化改进方法，对多模式串Trie树进行改进，进一步提高Trie树的效率；AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上而已。 用代码表示如下：
public class AcNode{
public char data;
public AcNode[] children;
// 失败指针
public AcNode fail;
// 当isEndingChar = true，记录模式串长度
public int length;
// 是否是结尾字符
public boolean isEndingChar;
public AcNode(char data){
this.data = data;
// 字符集只包含a~z 这26个字符
this.children = new AcNode[26];
this.length = -1;
this.isEndingChar = false;
}
}
AC自动机的构建包括两个操作：
1、将多个模式串构建成Trie树
代码实现如下：
public class AcTire{
private AcNode root;
public Tire(){
// 树顶存储无意义
this.root = new AcNode('/');
}
// 字符串插入
public void insert(char[] text){
AcNode p = root;
int n = text.length;
for(int i = 0; i < n; i++){
// 当前字符的下标
int idx = text[i] - 'a';
// 在Trie树中不存在，新增节点添加到树中
if(p.children[idx] == null){
AcNode newNode = new AcNode(text[i]);
p.children[idx] = newNode;
}
// 继续下一个字符匹配
p = p.children[idx]
}
// 插入完成，记录结尾字符下标和字符串长度
p.isEndingChar = true;
p.length = n;
}
}
2、在Trie树上构建失败指针（相当于KMP中的失效函数next数组）
这个失败指针的作用是什么？比如一个主串为：abce; 模式串为：abcd，bcd，bc，c；我们把主串字符匹配，发现匹配到第一个模式串abcd的最后一个字符匹配失败了，此时我们知道abcd模式串已经匹配不上了；为了提高效率，我们把已经能匹配上的字符串，跟其它其它模式串能不能匹配上；这时我知道abc是已经匹配上的字符串，我们把abc的后缀（bc、c）去跟其它模式串匹配，可以匹配到模式串bc和c；这时我们可以取最长可匹配后缀子串 bc 就可以了（因为c已经包含在bc中了，如果bc没有匹配上，那么就取c），那么字符串abc中的节点c的失败指针指向模式串 bc。如下图
通过上面的分析，主串匹配模式串，关键就是找到模式串每个节点的失败指针；
现在我们来构建Trie树的失败指针，这个过程跟KMP算法中next数组的构建过程很相似，我们假设节点p的失败指针指向节点 q，我们看节点p的子节点pc对应的字符，是否也可以在节点q的子节点找到。如果找到了节点 q 的子节点 qc，对应字符跟节点 pc 对应的字符相同 ，则将节点pc的失败指针指向节点qc；如果没有找到，我们再找q的失败指针子节点的字符跟节点 pc 对应的字符相同；就这样继续下去，如果都没有找到，我们就把pc节点的失败节点指向根节点；根节点的失败指针对应为 null； 如下图
整个实现代码如下：
// 构建失败指针
public void getFail() {
// 使用队列来遍历每个节点
Queue<AcNode> queue = new LinkedList<>();
root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcNode p = queue.remove();
for (AcNode child : p.children) {
// 当前子节点为空，直接跳到下一个子节点；
if (child == null) continue;
// 父节点是根节点
if (p == root) {
child.fail = root;
} else {
// 比较child字符
int idx = child.data - 'a';
AcNode pFail = p.fail;
while (pFail != null) {
// 如果相等
if (pFail.children[idx] != null) {
child.fail = pFail.children[idx];
break;
}
pFail = pFail.fail;
}
// 如果没找到
if (pFail == null) {
child.fail = root;
}
}
// 将子节点加入到队列中
queue.add(child);
}
}
}
// 匹配字符串
public void match(char[] text){
}
