By

Contents
  1. 1. 朴素的模式匹配算法
  2. 2. KMP算法
  3. 3. next数组求解
  4. 4. 代码实现

我们经常会有这种需求，比如在字符串goodgoogle中去查找google这个子串，这种子串的定位操作通常称作串的模式匹配。

朴素的模式匹配算法

对于以上问题，最容易想到的方式当然是暴力破解了，我们可能写出如下代码：

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
#include <stdio.h>
#include <string.h>
/*朴素的模式匹配算法*/
int getIndex (const char *pStr,const char *cStr) {
  int pLen = strlen(pStr);
  int cLen = strlen(cStr);
  int pos = -1,i = 0,j = 0;
  while (i < pLen && j < cLen) {
    if (pStr[i] == cStr[j]) {
      i ++;
      j ++;
    } else {
      i = i - j + 1;        // 回到上一次开始匹配的下一个位置
      j = 0;
    }
  }
  if (j = cLen) {
    pos = i - cLen;
  }
  return pos;
}
int main () {
  char *p = "goodgoodgoodgoogle";
  char *c = "google";
  int pos;
  pos = getIndex(p, c);
  printf("pos: %d\n", pos);           // 12
  return 0;
}

以上算法，简单地说，就是对依次用主串的每一个字符作为开头，与子串字符进行匹配。主串做大循环，子串做小循环，直到匹配成功为止。

它的时间复杂度为O(n + m)，其中n为主串长度，m为子串长度。

KMP算法

朴素的模式匹配算法是低效的，于是三位前辈——D.E.Knuth、J.H.Morris、V.R.Pratt就研究出了KMP算法，有人称看毛片算法。

KMP算法是一个模式匹配算法，可以大大避免重复遍历的情况。

它具有以下特点：

  1. 主串的i值不回溯。
  2. 子串的j值会在不匹配时发生回溯，回溯的位置为next[j]。
  3. next数组表示：在子串与主串在某处失配时，子串j应该回溯的位置，即next[j]。
  4. 而next[j]的值取决与子串位置j之前的字符串中，前后缀的相似度。

下面一张图辅助理解：

next数组求解

KMP算法的核心就是next数组，有了一个子串的next数组，KMP算法也就很容易实现了！

那么给定一个子串，如何求出其next数组呢？

要解决这个问题，我们需要谨记next数组的相关概念:

它的长度和子串长度相同，它的每个值说明了在子串和主串失配时，应该从子串的哪个位置开始下次匹配。而next[j]的值，就是子串在j位置之前的字符串的前后缀相似度。

它的求解过程可以图解如下：

代码实现

有了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
53
54
55
56
#include <stdio.h>
#include <string.h>
/*返回子串next数组*/
int * getNext (const char *c) {
  int cLen = strlen(c);
  int next[cLen];
  int *p = next;    // 用于返回，因为next不能用作返回返回值
  int i = 0;            // 前缀的下标
  int j = 1;            // 后缀的下标
  next[0] = -1;
  while (j < cLen) {
    if (c[i] == c[j-1]) {        // 如果前后缀相等，前后缀相似度加1
      next[j] = next[j-1] + 1;
      i ++;
      j ++;
    } else {
      i --;                 // 如果前后缀不相等，i值回溯
      if (i < 0) {          // 如果i回溯到0位置依旧不等，j指向下一个位置
        next[j] = 0;
        i ++;
        j ++;
      }
    }
  }
  return p;
}
/*KMP模式匹配算法*/
int getIndex (const char *p, const char *c) {
  int pLen = strlen(p);
  int cLen = strlen(c);
  int pos = -1, i = 0, j = 0;
  int *next = getNext(c);                // 对c串进行分析，得到其next数组
  while (i < pLen && j < cLen) {
    if (j == -1 || p[i] == c[j]) {       // 如果j=-1，代表第0个位置不匹配，则i和j都需要向后加1
      i ++;
      j ++;
    } else {
      j = next[j];
    }
  }
  if (j == cLen) {
    pos = i - cLen;
  }
  return pos;
}
int main () {
  char *p = "aaaaabcdefaaaaax";
  char *c = "aaaaax";
  int pos;
  pos = getIndex(p, c);
  printf("pos: %d\n", pos);    // 10
  return 0;
}

以上就是完整的KMP算法的实现，不过KMP算法还有可以优化的地方，后续补充。

Contents
  1. 1. 朴素的模式匹配算法
  2. 2. KMP算法
  3. 3. next数组求解
  4. 4. 代码实现