IT牛人博客聚合

多模式匹配在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说，给出一个长字符串和很多短模式字符串，如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树，AC算法，WM算法等等。我们将首先介绍这些常见算法。

1.hash

可以单字、双字、全字、首尾字hash。

优点：简单、通常有效

缺点：受最坏情况制约，空间消耗大，需要回朔。

2.Trie树

改进：进行穿线，参考KMP的算法，进行相同前缀匹配，建立跳转路径，避免回朔。

跳转路径建立的算法思想：

如果要建立节点 A -> A’ 的 跳转路径需要满足：

查看全文: http://www.udpwork.com/item/6036.html