BF 和 KMP 算法

我们在平常开发过程当中，针对字符串的处理那可以说是十分常见的了，所以我们今天就看两种字符串当中的算法，不过我们在看具体算法的实现之前，我们先来了解一下字符串的概念

字符串

在计算机刚被发明的时候，主要作用是做一些科学和工程的计算工作，刚开始的计算机都是处理数值工作，直到后来引入了『字符串』的概念，这样一来计算机开始可以处理非数值的概念了（原理是用数值来模拟非数值，通过 ASCII 码表），我们先来看下『串』这样的数据结构

• 串（string）是由零个或多个字符组成的『有限序列』，又名叫字符串
• 一般记为 s = "a1a2a3 ... an"（n >= 0）
• 串可以是空串，即没有字符，直接由 "" 表示，或者可以用希腊字母 Φ（fai）来表示
• 子串与主串的概念，例如 "abc" 是 "abcdef" 子串，反之则倒过来

字符串的存储结构

• 字符串的存储结构与线性表相同，也分顺序存储结构和链式存储结构
• 字符串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的
• 按照预定义的大小，为每个定义的字符串变量分配一个固定长度的存储区，一般用定长数组来定义
• 与线性表相似，既然是固定长度的存储区，就存在一个空间分配不灵活的问题，那么会考虑用链式存储结构
• 不同的是字符串我们一般都是连在一起表述的，所以习惯上我们通常还是会直接定义一个足够长度的存储区来存储的

字符串的比较

字符串比较大小跟传统的数字比较有点差别，很容易我们可以知道数字 2 比 1 要大，可要是字符串之间的比较呢？没错，也是比较大小，但是比较的是字符串里每个字符的 ASCII 码大小，因为 "a" 的 ASCII 码是 97，"A" 的 ASCII 码是 65，所以 'abc' > 'Abc' 是成立的，但是这样的比较并没有太大的意义，我们比较关注的还是两个字符串之间是否相等，这也是本章当中将要介绍的内容，即 BF 和 KMP 算法

BF 算法

BF 算法，即暴力（Brute Force）算法，是普通的模式匹配算法，BF 算法的思想就是将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配

• 若相等，则继续比较 S 的第二个字符和 T 的第二个字符
• 若不相等，则比较 S 的第二个字符和 T 的第一个字符，依次比较下去，直到得出最后的匹配结果

BF 算法属于朴素的模式匹配算法，它的核心思想是

• 有两个字符串 S 和 T，长度为 N 和 M
• 首先 S[1] 和 T[1] 比较，若相等，则再比较 S[2] 和 T[2]，一直到 T[M] 为止，若 S[1] 和 T[1] 不等，则 T 向右移动一个字符的位置，再依次进行比较
• 该算法最坏情况下要进行 M * (N - M + 1) 次比较，所以时间复杂度为 O(M * N)

C 语言版本实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 返回子串 T 在主串 S 中第 pos 个字符之后的位置，若不存在，则返回 0
// T 非空，1 <= pos <= strlen(S)
// 这里我们这里为了表述方便，字符串使用了第一个元素表示长度的方式
int index(String S, String T, int pos) {
  int i = pos; // i 用于主串 S 中当前位置下标
  int j = 1;   // j 用于子串 T 中当前位置下标

  // i 或 j 其中一个到达尾部即终止搜索
  while (i <= S[0] && j <= T[0]) {

    // 若相等则继续下一个元素匹配
    if (S[i] == T[i]) {
      i++;
      j++;
    // 若失配则 j 回溯到第一个元素从新匹配
    } else {
      // i 回溯到上次匹配首位的下一个元素，这是效率低下的关键
      i = i - j + 2;
      j = 1;
    }
  }

  if (j > T[0]) {
    return i - T[0];
  } else {
    return 0;
  }
}

JavaScript 版本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function indexOf(str, key) {
  let i = 0, j = 0

  // 为了简洁，没有判断当 str 剩余的字符少于 key 应该终止循环，因为这样会用到 length
  // 原理和上方是一样的，即 str[j] 和 key[i] 对比，如果一样那么 i 和 j 都加 1，否则 j 恢复到匹配时的下一个，i 恢复到 0
  while (key[i] !== undefined && str[j] !== undefined) {
    if (key[i] === str[j]) {
      i++
      j++
    } else {
      j = j - i + 1
      i = 0
    }
  }
  if (i === 0) return -1;
  return j - i
}

s = 'ABCDABCDABDE'
t = 'ABCDABD'
indexOf(s, t)

KMP 算法

下面我们再来看一种比较复杂的算法，也就是 KMP 算法

KMP，也称为 Knuth-Morris-Pratt 字符串查找算法，简称为 KMP 算法，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法

相较于 BF 算法，KMP 算法的主旨是尽量的减少指针的回溯从而使得性能得到提高（主要是文本串的指针，下面可以发现），我们先来看一下 KMP 算法 的操作流程

• 假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置
• 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j] ），都令 i++ 和 j++，然后继续匹配下一个字符
• 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j] ），则令 i 不变，j = next[j]（此举意味着失配时，模式串 P 相对于文本串 S 向右移动了 j - next[j] 位）
• 换言之，将模式串 P 失配位置的 next 数组的值对应的模式串 P 的索引位置移动到失配处

是不是看上去一头雾水，没关系，下面我们来结合图片一步一步往下看，其实 KMP 算法的两个难点在于『前缀表』与『next 数组』的获取，如果搞懂了这两个概念以后，在理解起来就是非常的简单了，我们以下图文本串 S 与模式串 P 为例

我们首先可以得出模式串 P 的所有『子串』，如下图

然后在求得每一个模式串中『相等的前缀与后缀的最大长度』，所以这里我们就需要稍微提及一下前缀与后缀的概念，所谓『前缀』指除了最后一个字符以外，一个字符串的全部头部组合，而『后缀』是指除了第一个字符以外，一个字符串的全部尾部组合，可以参考下面这个例子加深印象

• abcdef 的前缀 ==> a、ab、abc、abcd、abcde（注意，abcdef 不是前缀）
• abcdef 的后缀 ==> f、ef、def、cdef、bcdef（注意，abcdef 不是后缀）
• 公共最大长 ==> 0（因为其前缀与后缀没有相同的）

• ababa 的前缀 ==> a、ab、aba、abab
• ababa 的后缀 ==> a、ba、aba、baba
• 公共最大长 ==> 3（因为他们的公共前缀后缀中最长的为 aba，长度 3）

我们以上图当中标注为橙色的第五行的 abaab 为例，前缀和后缀分别如下图所示

然后我们可以得出『两者相同部分』的『最大长度』，也就是图中标注绿色的部分，由图可知为 2，然后在依据此原理，依次推算出所有子串的『相等的前缀与后缀的最大长度』，结果如下图所示

但是这里要多说一句，就是有没有什么方法可以让我们快速的获取到所有子串的『相等的前缀与后缀的最大长度』呢？方法是有的，这里我们以第四和第五行子串为例，如下图

我们假设已经求得了第四行子串的『最长公共前后缀』，它的长度为 1，如下图所示

那么我们可以思考，如何使得它的『最长公共前后缀』变长呢？没错，只需要在它后面添加一个字母就够了，也就是字母 b，如下图

也就是说，下一行添加的字母与当前行的『最长公共前后缀』的长度后面的那个字母一样，则『最长公共前后缀』的长度加 1，也就如下图所示

但是如果下一行添加的字母与当前行的『最长公共前后缀』的长度后面的那个字母不一样，则可以根据我们最开始的笨方法重新计算即可

现在再让我们回到最开始的地方，因为我们已经得到了『所有子串的相等的前缀与后缀的最大长度』，我们可以将这组序列称之为 maxL，如下图所示

然后我们便可以根据『最大长度表』来去获得我们最为重要的 next 数组了，关于 next 数组的获取，就是在我们的『最大长度表』的基础之上『整体向右移动一位』，然后初始值赋为 -1（最后一位的 0 则被忽略掉）

有了 next 数组以后，我们就可以正式的开始我们的比对过程了，如下图

如图中所示，依次从左往右开始一一比对，直到遇到不相匹配的，也就是下图这样的情况

这时可以发现，模式串的 b 与文本串的 c 失配了，所以我们就需要找出失配处模式串的 next 数组里面对应的值，这里为 0，所以就需要将索引为 0 的位置移动到失配处再次开始匹配（其他元素也是移动同样的距离）

然后继续执行我们的比对过程，但是此时可以发现，依然是不匹配的，所以我们还是需要按照之前的逻辑来进行执行

此时模式串的 a 与文本串的 c 失配了，所以我们就需要找出失配处模式串的 next 数组里面对应的值，这里为 -1，所以就需要将索引为 -1 的位置移动到失配处，再次继续向右执行

直到再次出现下图这样的情况

此时也是同理，从图中我们可以发现，当前不匹配的位置位于 next 数组当中的 2 位置处（也就是红框所在位置），所以这里依然按照我们之前的逻辑，移动到索引为 2 的置处再次开始匹配，如下图

最终直到匹配完成或者没有匹配到结果，如下

这样一来，就完成了我们的整个 KMP 算法的流程，下面我们在来看看如何用代码来进行实现，总的来说分为两个步骤，首先是先获取我们的 next 数组，然后才是去进行匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdio.h>

typedef char *String;

void getNext(String T, int *next) {
  int j = 0;
  int i = 1;
  next[1] = 0;

  while (i < T[0]) {
    if (0 == j || T[i] == T[j]) {
      i++;
      j++;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
}

// 返回子串 T 在主串 S 第 pos 个字符之后的位置
// 若不存在，则返回 0
int KMP(String S, String T, int pos) {
  int i = pos;
  int j = 1;
  int next[255];

  getNext(T, next);

  while (i <= S[0] && j <= T[0]) {
    if (0 == j || S[i] == T[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }

  if (j > T[0]) {
    return i - T[0];
  } else {
    return 0;
  }
}

但是这里还存在可以优化的空间，比如我们需要匹配的主串 S 为 aaaabcde，而子串 T 是 aaaaax，那么匹配的情况就成了下图所示

如果按照我们之前的逻辑，这里将会依次匹配 next 数组的 4, 3, 2, 1, 0，但是我们可以很明显的发现，因为 T 串的前几个字母都是一致的，完全没有必要进行比较，直接将将指针赋值过去即可，所以我们可以稍微的优化一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void getNext(String T, int *next) {
  int j = 0;
  int i = 1;
  next[1] = 0;

  while (i < T[0]) {
    if (0 == j || T[i] == T[j]) {
      i++;
      j++;

      // 我们在这里进行一下判断，避免多余的操作
      if (T[i] != T[j]) {
        next[i] = j;
      } else {
        next[i] = next[j];
      }
    } else {
      j = next[j];
    }
  }
}

最后再来看一下 JavaScript 版本的实现，原理都是一样的，首先获取 next 数组，然后在根据 next 数组来进行回退操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

function getNext(p) {
  let k = -1
  let j = 0
  let next = [-1]
  let pLen = p.length

  while (j < pLen - 1) {
    // p[k] 表示前缀，p[j] 表示后缀
    if (k == -1 || p[j] == p[k]) {
      ++j
      ++k
      // 在这里直接进行赋值操作也是可以的，但是保持一致，还是同 C 语言版本，在这里进行一下优化
      if (p[j] != p[k]) {
        next[j] = k
      } else {
        // 因为不能出现 p[j] = p[next[j]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
        next[j] = next[k]
      }
    } else {
      k = next[k]
    }
  }
  return next
}

function KMP(s, p) {
  let i = 0
  let j = 0

  let sLen = s.length
  let pLen = p.length

  let next = getNext(p)

  while (i < sLen && j < pLen) {
    // 如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++
    if (j === -1 || s[i] === p[j]) {
      i++
      j++
    } else {
      // 如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]
      // 这里就是与 BF 算法不同的地方，这里仅仅只用回退 j，而不用回退 i
      j = next[j]
    }
  }

  return j === pLen ? i - j : -1
}

s = 'ABCDABCDABDE'
t = 'ABCDABD'
KMP(s, t)  // 4