彻底理解和掌握 KMP 算法

本文带你彻底理解和掌握 KMP(Knuth-Morris-Pratt) 算法

LeetCode：https://leetcode-cn.com/problems/implement-strstr (opens new window)

# BF(Brute Force) 算法 / 暴力算法

文本串 Text: ababababca
模式串 Pattern: abababca

KMP-1

如上图所示，从 T串的起始位和 P串循环匹配，直到匹配成功返回对应的下标或者匹配到最后结束返回-1

function strStr(t, p) {
  for (let i = 0; i <= t.length-p.length; i++) {
    let flag = true;
    for (let j = 0; j < p.length; j++) {
      if (t[i + j] != p[j]) {
          flag = false;
          break;
      }
    }
    if (flag) {
      return i;
    }
  }
  return -1;
}

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

int strStr(char* t, char* p) 
{
  int i = 0, j = 0;
  bool flag = true;

  for (i = 0; i <= strlen(t)-strlen(p); i++) 
  {
    for (j = 0; j < strlen(p); j++) 
    {
      if (t[i + j] != p[j]) 
      {
          flag = false;
          break;
      }
    }

    if (flag) 
      return i;
  }

  return -1;
}

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

// Make sure to add code blocks to your code group

# KMP(Knuth Morris Pratt) 算法

# 原理刨析

高性能的算法都是慢慢优化出来的，从上面的暴力算法来看，第 1 轮如下：

KMP-2

第 2、3 轮如下：

KMP-3

上图中 括号 、红色 的内容看不懂先不管，后面理解了回头看就懂了

第 2 轮 T[1] != P[0] 直接失败，进入第三轮

第 3 轮 T[2-5] == P[0-3]，进入 T[i=6] 跟 P[j=4] 的判断

KMT 算法就是能够直接从第 1 轮匹配失败时的 i=6，进入到第 3 轮的 T[i=6] 跟 P[j=4] 的判断，直接跳过中间能够确定失败的比较，重点就是怎么去确定中间这些比较一定是失败的

继续上面，假如T串比较长，上面第三轮还未成功，按暴力BF算法继续下去就是 i=3 然后 j=0，根据上图， P 串右移一位，即 j=0 对齐到 i=3 自行脑补一下 😄 ，这时图中 深灰色串 上下需要比较的就只有三个

然后一直匹配失败，BF循环下去，直到深灰色部分错开，即第 7 轮时 (注意此时 i 相对于第一轮匹配失败时的位置从图片上来说也是不动的，只不过此时 i=6 表示的是BF第7轮)

重 点 来 了

提示

前缀就是除了最后一位，从第一位到任意一位的字符串，比如上面的 ababab 的前缀就包括 ababa abab aba ab a
后缀就是除了第一位，从任意一位到最后一位的字符串，比如上面的 ababab 的后缀就包括 babab abab bab ab b

注意：本身不是后缀也不是前缀

这时你会发现，在深灰色部分错开之前的这几轮中，前面深灰色部分的比较:

就是第 1 轮匹配失败时前面相同字串(ababab) 的 前缀跟后缀 在比较，并且是从最长前后缀往最短的去比较（脑补一下，一直在错开，所以是从最长到最短）
也是 T串跟 P串 开始一部分的比较，所以只要前后缀不相等，那么这一轮就 确定是失败的

这时有两种情况：

没有相同的前后缀，也就是深灰色部分最终错开，这时 j=0、i=6（也就是进入BF的第七轮的比较），继续后面的比较
有相同的前后缀(注意这个也是最长相同前后缀)，这时也就是上面图片BF第三轮的情况，由于前后缀相同，也就是 T串跟 P串开始的部分相同，无需再比较 j 指向相同前后缀的后一位，下标从0开始，也就是等于最长相同前后缀的长度 ，所以 j=4、i=6 (注意这里相当于BF第三轮的 T[i=6] 跟 P[j=4] 的比较)，继续后面的比较

继续后面的比较：

成功，输出对应的下标，也就是 i 减去 P 串长度 + 1 或者 i - j
失败，重复上面的步骤，也就是求出失败位置前面相同部分的 最长相同前后缀的长度，然后 j 移动到该位置，i 保持失败时的位置不变，继续后面的比较，然后重复下去

到这里，你应该清楚 KMP 为什么相比于BF暴力解法更快：

因为 KMP 利用已匹配部分中最长相同的「前缀」和「后缀」来跳过那些能够被否定的匹配。
因为 KMP 的原串指针 i 不会进行回溯，要么递增，要么保持原位。（j=0，也就是P串从开始位置比较时，i、j 是递增直到匹配失败停下来，接下来 i 保持位置不变，j 跳到相同最长前后缀长度的位置继续后面的比较）

重 点 又 来 了

通过上面，我们知道 P串从开始位置(j = 0 )到匹配失败时的位置 前面部分跟 T串是相同的，也就是说 对于匹配串 P 的任意一个失败位而言，由该位置发起的下一个匹配点位置(j 跳转的位置)其实与原串无关(前面部分相同了也就不需要原串了)。

举个🌰，对于 P串 abcabd 的字符 d(该位置匹配失败) 而言，前面相同部分 abcab 的 最长相同前后缀 ab 的长度为 2，也就是说由字符 d 发起的下一个匹配点位置(j 跳转的位置)必然是字符 c 的位置（2 的位置）

所以我们可以直接先求出 P串在每个位置失败时前面部分对应的 最长相同前后缀的长度，组成一个 next 数组，我们将这一过程称为找 next 点。

KMP-4

👉

到这里你应该明白，为什么 KMP 算法中需要先设置一个 next 数组，保存着 匹配串P 在每个位置前面部分对应的 最长相同前后缀的长度 了吧！！！

先看看在确定 next 数组 情况下的核心代码：

function strStr(t, p) {
  let i = 0, j = 0;

  // p 为空时 直接返回 0，与 js 中的 str.indexOf('') 返回 0 相同
  if(p.length === 0) {
    return 0
  }

  // j == p.length 时，说明匹配上了，退出循环
  // i == t.length 时，说明前一轮已经匹配到 T串 最后一位了，这一轮需要退出循环，否则越界了
  while(i < t.length && j < p.length) {
    // 1. 
    // 注意：next 数组的第一位我们设置为 -1，即 next[0] = -1;
    // j == -1 说明 上一轮循环中 j = next[j] = next[0]，j = 0，表示的其实就是上一轮循环中，在 P串 的起始位就匹配失败了
    // 这一轮循环 i 指向下一位，即 i++，而 j 需要指向起始位，即 j = 0，j == -1 时 j++ 刚好就是 0 指向起始位
    // 2. 
    // t[i] == p[j] 说明该位匹配上，继续下一位的匹配，所以 i++; j++;
    if (j == -1 || t[i] == p[j]) 
    {
      i++;
      j++;
    } else {
      // 没匹配上，j 指向 该位前面已匹配的字串 最长相同前后缀 的后面，即 等于最长相同前后缀的长度 next[j]
      j = next[j];
    }
  }

  // 匹配到，返回对应的下标
  if (j === p.length)
      return i - j;

  return -1; 
}

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

int strStr(char *t, char *p) 
{
  int i = 0, j = 0;
  // strlen 返回值是 unsigned int 需要转化为 int，否则下面 j < m 的判断 当 j = -1 时会跳出循环出错
  int n = (int)strlen(t), m = (int)strlen(p);

  if(m == 0) 
  {
    return 0;
  }

  while(i < n && j < m) 
  {
    if (j == -1 || t[i] == p[j]) 
    {
      i++;
      j++;
    } 
    else 
    {
      j = next[j];
    }
  }

  if (j == m)
      return i - j;

  return -1;
}

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

// Make sure to add code blocks to your code group

# next 数组的构建

通过上面原理剖析，我们知道：

对于匹配串 P 的任意一个失败位而言，由该位置发起的下一个匹配点位置 (j 跳转的位置) 其实与原串无关。
跳转的位置 就是 P串 在 失败位 前面字串的 最长相同前后缀的长度。

KMP-4

将 P串 每个位置前面字串的 最长相同前后缀的长度 找出来组成一个 next 数组，我们将这一过程称为 next 数组的构建。

# next 数组构建过程

求 next 数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串。

KMP-5

next[0] = -1 : 方便后面编码自增等于 0，指向起始位

next[1] = 0 : 这个位置前面只有一个字符，没有前后缀，所以为 0

next[2] : 这个位置前后缀就只有一个字符，直接比较是否相等，

KMP-6

next[3] : 这个位置最长的前后缀长度为 2 ，根据上一轮知道长度为 2 是不相同的，也就是只需比较最后一位长度为 1 的前后缀是否相同。

KMP-7

next[4] 、next[5] 、next[6] ：由于前面 j 位都是匹配上的，如果较最后一位也相等，此时 j + 1 就是最长前后缀了，如果不相等(下轮的情况)

KMP-8

KMP-9

不相等之后，我们需要继续查看前面是否还有其他更短的相同前后缀，这个时候从哪里开始看，这个过程是不是就是 KMP 匹配到失败时，看前面字串的最长相同前后缀的长度，然后去跳转 j

并且 此时前面每个位置的最长相同前后缀的长度我们已经求出来了，就是已经算出的 next数组的前部分，所以这个过程跟 KMP 查找字串相通的，也就可以得出如下结论：

next 数组构建过程

求 next 数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串。

匹配成功，那么当前的 next 值就是匹配成功的字符串的长度。即 next[++i] = ++j;

匹配失败，根据前面求出的 next 值去跳转，即 j = next[j];

下面给出具体代码：

function getNext(p, next) {
  let i = 1, j = 0;

  next[0] = -1;
  next[1] = 0;

  while (i < p.length - 1) {
    if (j == -1 || p[i] == p[j]) {
      i++;
      j++;
      next[i] = j;
    }	else {
      j = next[j];
    }	
  }
}

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

void getNext(char* p, int* next)
{
  int i = 1, j = 0;

  next[0] = -1;
  next[1] = 0;

  while (i < (int)strlen(p) - 1)
  {
    if (j == -1 || p[i] == p[j])
    {
      i++;
      j++;
      next[i] = j;
    }	
    else
    {
      j = next[j];
    }	
  }
}

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

// Make sure to add code blocks to your code group

# 代码实现

整体代码合并后如下：

function strStr(t, p) {
  const pl = p.length;
  
  // p 为空时 直接返回 0，与 js 中的 str.indexOf('') 返回 0 相同
  if(pl === 0) {
    return 0
  }

  //const next = new Array(pl).fill(0);
  const next = [];

  // 构建 next 数组
  next[0] = -1;
  if(pl > 1) {
    next[1] = 0;
  }

  let i = 1, j = 0;

  while (i < p.length - 1) {
    if (j == -1 || p[i] == p[j]) {
      i++;
      j++;
      next[i] = j;
    }	else {
      j = next[j];
    }	
  }

  // KMP
  i = 0;
  j = 0;
  // j == p.length 时，说明匹配上了，退出循环
  // i == t.length 时，说明前一轮已经匹配到 T串 最后一位了，这一轮需要退出循环，否则越界了
  while(i < t.length && j < p.length) {
    // 1. 
    // 注意：next 数组的第一位我们设置为 -1，即 next[0] = -1;
    // j == -1 说明 上一轮循环中 j = next[j] = next[0]，j = 0，表示的其实就是上一轮循环中，在 P串 的起始位就匹配失败了
    // 这一轮循环 i 指向下一位，即 i++，而 j 需要指向起始位，即 j = 0，j == -1 时 j++ 刚好就是 0 指向起始位
    // 2. 
    // t[i] == p[j] 说明该位匹配上，继续下一位的匹配，所以 i++; j++;
    if (j == -1 || t[i] == p[j]) 
    {
      i++;
      j++;
    } else {
      // 没匹配上，j 指向 该位前面已匹配的字串 最长相同前后缀 的后面，即 等于最长相同前后缀的长度 next[j]
      j = next[j];
    }
  }

  // 匹配到，返回对应的下标
  if (j === p.length)
      return i - j;
 
  return -1; 
}

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
53
54
55
56
57

int strStr(char *t, char *p) 
{
  int i = 1, j = 0;
  // strlen 返回值是 unsigned int 需要转化为 int，否则下面 j < m 的判断 当 j = -1 时会跳出循环出错
  int n = (int)strlen(t), m = (int)strlen(p);
  //int *next = (int*)malloc(sizeof(int) * m);

  if(m == 0) 
  {
    return 0;
  }

  // 构建 next 数组
  // int next[m] = {0};
  int next[m];

  next[0] = -1;
  if (m > 1) {
      next[1] = 0;
  }

  while (i < (int)strlen(p) - 1)
  {
    if (j == -1 || p[i] == p[j])
    {
      i++;
      j++;
      next[i] = j;
    }	
    else
    {
      j = next[j];
    }	
  }

  // kMP
  i = 0;
  j = 0;

  while(i < n && j < m) 
  {
    if (j == -1 || t[i] == p[j]) 
    {
      i++;
      j++;
    } 
    else 
    {
      j = next[j];
    }
  }

  if (j == m)
      return i - j;
  
  return -1;
}

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
53
54
55
56
57

// Make sure to add code blocks to your code group

编辑此页

#KMP

上次更新: 2023/02/02, 14:58:40

← EMV交易流程 npm切换源→