作者:罗大光; 郝玉洁; 刘乃琦匹配散列函数字符串匹配快速匹配
摘要:结合Karp-Rabin和Boyer-Moore字符串匹配算法的优点,提出了一种非常快速的字符串匹配算法.该算法在匹配过程中与传统的直接比较模式及正文子串不同,与KR算法一样,比较的是模式与子串对应的散列值;该算法同时吸取了BM算法的特点,能在扫描正文的过程中跳过尽可能多的字符.理论分析表明,模式串较短时,该算法在最坏情况下的时间复杂度也可以达到O(n).实验表明,该算法所需时间约为KR算法的1/10.
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社