23 字符串匹配之 BF & RK 算法

宋涛收录于 Python

2018-10-30 约 1081 字预计阅读 3 分钟

粗暴匹配的 BF 与 RK 算法

1. 特性

从本节开始我们将学习字符串匹配算法。字符串匹配算法有很多，大体可以分成两类:

单模式串匹配算法: 一个串跟一个串进行匹配，包括BF，RK，KMP，BM 算法
多字符串匹配算法: 一个串中同时查找多个串，包括 Trie 树和 AC 自动机

本节我们先来学习“最简单粗暴的” BF 和 RK 算法。为了便于描述，对于在字符串A中查找 B，我们将 A 称为主串，B 称为模式串，n=len(A), m=len(B)。

1.1 BF 算法

BF(Brute Force) 暴力匹配算法，采用的就是我们最容易理解的穷举法。从主串的第一位开始检查主串中所有长度为 m 的子串看是否与模式串相等。主串中有(n-m+1)个长度为 m 的子串，因此总共需要比较(n-m+1)*m次

BF 算法的时间复杂度很高，为 O(m*n)，但却是一个比较常用的字符串匹配算法，而原因有两个:

大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。
算法简单，实现起来不容易出错

1.2 RK 算法

RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。RK 算法可以理解为引入了哈希算法的 BF。

RK 算法希望通过计算字符串的哈希值，并通过比较哈希值，而不是比较字符串，来缩小BF算法中主串的子串与模式串的比较时间。要想达到优化的目的，我们必需使得(字符串哈希+哈希值比较的时间) < (m 次字符比较的时间)。因为哈希值是整数，单次整数的比较时间可以忽略不计。但是字符串哈希值的计算也需要遍历每个字符，因此想要优化，必需精心设计此处的哈希函数。

为了减少字串哈希值的计算量，在计算第 i 个字串的哈希值时，需要能用到已经计算的第 i-1 个字串的哈希值，并且平衡好计算过程中空间占用和哈希冲突的概率。因为 RK 算法并不常用，所以这里我不再过多讲述，有兴趣的同学可以自己查看专栏的介绍。

RK 算法的时间复杂度取决于哈希函数，理想情况下，RK 算法的时间复杂度是 O(n)，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，时间复杂度就退化为 O(n*m)。

2. 实现

2.1 BF 算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15



def find_brute(T, P):
    """
    :param T: 主串
    :param P: 模式串
    :return:
    """
    n, m = len(T), len(P)
    for i in range(n - m + 1):
        j = 0
        while j < m and T[i + j] == P[j]:
            j += 1
        if j == m:
            return i
    return -1

3. 应用

今天讲的一维字符串匹配可以应用到二维空间中。即如下图所示，在一个二维主串中搜索另一个二维模式串。

下面是代码实现:

1

pass

参考:

目录