美文网首页程序员
字符串匹配算法--BF算法与RK算法

字符串匹配算法--BF算法与RK算法

作者: 二毛_220d | 来源:发表于2019-10-20 15:37 被阅读0次

    BF算法

    BF算法中的BF是brute force的缩写,中文叫做暴力匹配算法,也加朴素匹配算法。算法特点:“暴力” 、简单、好懂、性能不佳。
    引入两个概念:主串与模式串。
    比方说:我们在字符串A中查找字符串B,那么字符串A就是主串,字符串B就是模式串。
    我们把主串的长度记作n,模式串的长度记作m。因为我们是在主串中查找模式串,所以n>m。
    BF算法的思想:我们在主串中,检查起始位置分别是0、1、2、3、...n-m且长度为m的n-m+1个子串,看有没有跟模式串匹配的。
    图例:


    BF算法图例

    这种算法的最坏时间复杂度为O(n*m)。

    尽管理论上,BF算法的时间复杂度很高,是O(n*m)。 但在实际开发中它是一个比较常用的字符串匹配算法。为什么这么说呢?原因有两点。

    • 第一:实际的软件开发中,大部分情况下,模式串与主串的长度都不会太长。
    • 第二:BF算法的思想简单,代码实现也非常简单。简单意味着不容易出错,如果有bug也容易暴露和修复。

    RK算法

    RK算法的全称叫Rabin-Karp算法,是由它的两位发明者Rabin与Karp的名字来命名。
    RK算法的思想是这样的:我们通过哈希算法对主串中的n-m+1个子串分别求哈希值,然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等,那就说明对应的子串与模式串匹配了(这里不考虑哈希冲突)。有哈希冲突怎么办,解决方法也很简单(当我们发现子串的哈希值与模式串相等时,再对比一下子串与模式串就可以了)。哈希值是数值,数值之间的比较是比较快速的。


    RK算法图例

    相关文章

      网友评论

        本文标题:字符串匹配算法--BF算法与RK算法

        本文链接:https://www.haomeiwen.com/subject/doxamctx.html