一种改进的应用于多模式串匹配的KR算法

摘要

Karp-Rabin算法是利用hash函数的特性进行字符串匹配的算法。KR算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值,如果hash值相同,才进一步比较这2个串是否真正相等。Karp-Rabin算法适用于多个字符串匹配。该算法所需要的空间存储很小,相比AC算法在空间占用上具有很大的优势。本文首先将模式串进行合适的分类,求出模式串半段对应的哈希值,然后对目标段按照模式串的基准长度进行分段,每次比较目标段是否含有模式串的半段,若含有,则继续比较;否则,继续进行下一个目标段的匹配。最后通过实验验证,证明了算法的有效性。