多模式匹配在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说，给出一个长字符串和很多短模式字符串，如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有
Trie
树，
AC
算法，
WM
算法等等。我们将首先介绍这些常见算法。
1.
hash
可以单字、双字、全字、首尾字
hash
。
优点：简单、通常有效
缺点：受最坏情况制约，空间消耗大，需要回朔。
2.
Trie
树
改进：进行穿线，参考
KMP
的算法，进行相同前缀匹配，建立跳转路径，避免回朔。
跳转路径建立的算法思想：
如果要建立节点
A -> A’
的
跳转路径需要满足：
1)
A = A’
节点有相同的
value
值，代表同一个字
2)
A
的深度
>A’
的深度
3)
对于
A
节点的父节点
F
，和
A’
节点的父节点（如果有父节点的话），有
F->F’
优点：无回朔，查询效率一般较高
缺点：数据结构复杂难以维护，浪费空间多，建树时间长。
3.
AC
算法
本质上来说和
Trie
树一样。