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

An improved KR algorithm for multi-patterns string matching

作　　者：董志鑫[1] 李馨梅 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]对外经济贸易大学保险学院,北京100029

出　　处：《智能计算机与应用》2018年第1期116-122,共7页Intelligent Computer and Applications

摘　　要：Karp-Rabin算法是利用hash函数的特性进行字符串匹配的算法。KR算法对模式串和循环中每一次要匹配的子串按一定的hash函数求值,如果hash值相同,才进一步比较这2个串是否真正相等。Karp-Rabin算法适用于多个字符串匹配。该算法所需要的空间存储很小,相比AC算法在空间占用上具有很大的优势。本文首先将模式串进行合适的分类,求出模式串半段对应的哈希值,然后对目标段按照模式串的基准长度进行分段,每次比较目标段是否含有模式串的半段,若含有,则继续比较;否则,继续进行下一个目标段的匹配。最后通过实验验证,证明了算法的有效性。Karp-Rabin algorithm is a string matching algorithm using the characteristics of hash functions. The KR algorithmevaluates each substring of the pattern string and the loop in accordance with a certain hash function. If the hash value is the same,then the two strings are compared to determine they are equal or unequal. Karp -Rabin algorithm is suitable for multiple stringmatching better. The space storage required by the algorithm is very small, and it has great advantages in space occupation comparedwith AC algorithm. This paper first classifies the pattern string properly. The hash value corresponding to the half segment of thepattern string is computed. Then, the target segment is segmented according to the reference length of the pattern string. Each timedetermines whether the target segment contains half of the string of patterns. If it contains, continue to compare; otherwise, continuethe matching of the next target segment. Finally, the validity of the algorithm is proved by experiments.

关 键 词：多模式 模式匹配 KR算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]