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


粗暴匹配的 BF 与 RK 算法

<!-- more -->

## 1. 特性
从本节开始我们将学习字符串匹配算法。字符串匹配算法有很多，大体可以分成两类:
1. 单模式串匹配算法: 一个串跟一个串进行匹配，包括BF，RK，KMP，BM 算法
2. 多字符串匹配算法: 一个串中同时查找多个串，包括 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)，但却是一个比较常用的字符串匹配算法，而原因有两个:
1. 大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。
2. 算法简单，实现起来不容易出错


### 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 算法
```Python

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. 应用
今天讲的一维字符串匹配可以应用到二维空间中。即如下图所示，在一个二维主串中搜索另一个二维模式串。
![brute_test](/images/algo/string/brute.jpg)

下面是代码实现:
```Python
pass
```

**参考:**
- [王争老师专栏-数据结构与算法之美](https://time.geekbang.org/column/126)
- [《数据结构与算法：python语言实现》](https://book.douban.com/subject/30323938/)