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

A Very Fast String Search Algorithm

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

     

    Abstract: A very fast algorithm to perform pattern matching in strings was described. The proposed match algorithm combines the advantages of Karp-Rabin's algorithm and Boyer-Moore's algorithm. Instead of checking at each position of the text if the pattern occurs, it is only to check the resemblance between the contents of the string and the pattern by using a hashing function and can skips as many characters as possible. In the cases of short patterns its time complexity can theoretically reach O(n) even in the worst cases. In actual experiments, the time it takes to search a string is about 1/10 of the time KR algorithm takes.

     

/

返回文章
返回