一种非常快速的字符串匹配算法

摘要

结合Karp-Rabin和Boyer-Moore字符串匹配算法的优点,提出了一种非常快速的字符串匹配算法.该算法在匹配过程中与传统的直接比较模式及正文子串不同,与KR算法一样,比较的是模式与子串对应的散列值;该算法同时吸取了BM算法的特点,能在扫描正文的过程中跳过尽可能多的字符.理论分析表明,模式串较短时,该算法在最坏情况下的时间复杂度也可以达到O(n).实验表明,该算法所需时间约为KR算法的1/10.