多模式匹配算法

AC自动机中，转移的最小单位是一个字符。也就是说，匹配后只能移动一个字符，复杂度是线性的O(n)

。然而线性并非最快，Boyer-Moore算法在匹配后可以跳过多个字符，比线性还快。据说在实践中，利用Boyer-Moore优化的AC自动机总是更快。

来熟悉一下Boyer-Moore算法的基本思路。假设模式串的长度为m

，母文本为t。算法不是去母文本中找模式串，而是在模式串中从右到左找文本的第 m个字符tm。如果没找到，那么就可以在母文本中跳过m个字符，继续搜索t2m。如果找到了，比如说是模式串的第2个字符，那就可以跳过m−2个字符，继续搜索t2m−2，以此类推。ti恰好与模式串尾部匹配的时候，再比较剩下的ti−1⋯tt−m，直到这m个字符都匹配上。该算法可利用下图演示（二进制串匹配，白色代表0，绿色代表1

）：

上例在匹配下标5

后直接快进了3

个字符。

Wu Manber利用了Boyer-Moore的思路，将该算法拓展到多模式匹配。

预处理

第一步要算出所有模式串上的最小长度m

，然后先考虑每个模式串的前m个字符。如此所有模式串长度都一样了。注意如果最短模式串非常短，比如长度为1，

文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。

原文链接：aaaedu.blog.csdn.net/article/details/105133521