接下来，介绍一些基本概念，做些对比，
基本概念
trie树
Trie树，又称字典树、前缀树、单词查找树，是一种树形结构，哈希树的变种。其典型应用是用于统计，排序和保存大量的字符串（但不仅限字符串），所以经常被搜索引擎系统用于文本词频统计。
优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
具有以下特征：
根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
每个单词的公共前缀作为一个字符节点保存。
DFA算法
DFA，Deterministic Finite Automation, 即确定有限状态自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表求和的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。
数据结构：Trie树。
原理：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。
AC自动机和DFA自动机对比
AC自动机和DFA确定性有限自动机都是用于字符串匹配的算法，但它们在设计和应用上有一些显著的区别。以下是两者之间的主要区别：
基本概念
Aho-Corasick自动机（AC自动机）：
AC自动机是一种多模式匹配算法，能够在一次扫描中同时匹配多个模式。
它结合了Trie树和KMP（Knuth-Morris-Pratt）算法的思想，通过构建一个带有失败指针的Trie树来实现高效匹配。
确定性有限自动机（DFA）：
DFA是一种状态机，用于接受或拒绝输入字符串。
在每个状态下，根据当前输入字符转移到下一个状态，直到处理完所有输入字符。
DFA通常用于单模式匹配，但也可以通过扩展来支持多模式匹配。
数据结构
AC自动机：
使用Trie树作为基础数据结构，每个节点代表一个字符。
增加了失败指针，用于在匹配失败时跳转到其他可能的部分匹配位置。
DFA：
使用状态转换表，每个状态对应一组输入字符及其对应的下一个状态。
状态转换表可以表示为二维数组或哈希表。
构建过程
AC自动机：
首先构建Trie树，将所有模式插入其中。
然后添加失败指针，通过广度优先搜索（BFS）遍历Trie树，设置每个节点的失败指针。
DFA：
构建过程相对简单，只需定义所有可能的状态及其转换规则。
对于复杂模式，可以通过正则表达式或其他方法生成DFA。
匹配过程
AC自动机：
在文本中进行一次线性扫描，从根节点开始，根据当前字符进行状态转移。
如果遇到无法继续匹配的情况，则根据失败指针跳转到其他可能的位置继续匹配。
DFA：
从初始状态开始，根据当前输入字符进行状态转移，直到处理完所有输入字符或进入终止状态。
时间复杂度
AC自动机：
匹配时间复杂度：( O(n) )，其中 ( n ) 是待检查文本的长度。
DFA：
匹配时间复杂度：( O(n) )。
应用场景
AC自动机：
特别适合多模式匹配，如敏感词检测、病毒签名检测等需要同时查找多个模式的问题。
DFA：
通常用于单模式匹配，如正则表达式引擎、编译器中的词法分析器等。通过扩展，也可以用于多模式匹配，但构建和维护较为复杂。
总结
虽然AC自动机和DFA都能用于字符串匹配，但它们各自有不同的优势和应用场景。对于多模式敏感词检测问题，AC自动机会更高效，因为它能在一次扫描中完成所有敏感词的查找。而DFA更适合单一模式或较少数量模式的快速识别。
![[从0开始轨迹预测][NMS]：NMS的应用（目标检测、轨迹预测）](https://img-blog.csdnimg.cn/img_convert/508885221ba5c45bd103fb46cc35b83c.png)
