稀有猿诉

十年磨一剑，历炼出锋芒，说话千百句，不如码二行。

Understanding KMP Algorithm

字符串模式匹配问题是非常重要且基础的问题，它是解决在目标字符串str中搜索模式字符串pattern出现的次数，或者索引位置。这个问题最为高效的方法就是著名的KMP算法，但这个算法不太好理解，毕竟是解决了从O(n2)的复杂度提升到线程O(n)的，今天就来学习并理解一下KMP算法。

字符串模式匹配问题有很多变幻，比如从头匹配就是前缀匹配，从后就是后缀匹配，找出所有匹配的索引，找第一个，看是否有匹配等等。以及其他能转化为模式匹配的问题，比如回文相关问题，但本质都模式匹配问题。这里就以寻找模式pattern在str中的第一个索引位置为例题。

暴力大法

世上无难题，只要能用暴力不超时。很容易写出一个暴力方法：

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

int index(String str, String pattern) {
  int n = str.length();
  int m = str.length();
  for (int i = 0; i <= n - m; i++) {
      int j = 0;
      while (j < m && str.charAt(i + j) == pattern.charAt(j)) {
          j++;
      }
      if (j == m) {
          return i;
      }
  }
  return -1;
}

很明显暴力大法的时间复杂度是O(nm)，需要从str中的每一个字符开始尝试去匹配pattern。str的指针在尝试这一次匹配后，只能向前步进一个，这是暴力大法最大的问题。假如能有方法让它步进的快一些，那么就能显著 的提升效率，这就是KMP算法的牛逼之处。

KMP算法

KMP算法的牛逼之处就是利用预处理和已做过的上一次匹配来快速步进str的i指针，使总的匹配次数降到O(n + m)。

无论是否能理解，好在代码不长，就当模板题背下来吧。

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

public int index(String str, String pattern) {
    char[] sc = str.toCharArray();
    char[] pc = pattern.toCharArray();
    int n = sc.length;
    int m = pc.length;
    int[] next = calcNext(pc);

    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && sc[i] != pc[j]) {
            j = next[j - 1];
        }
        if (sc[i] == pc[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }

    return -1;
}

private int[] calcNext(char[] pattern) {
    int m = pattern.length;
    int[] next = new int[m];
    int k = 0;
    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = next[k - 1];
        }
        if (pattern[k] == pattern[i]) {
            k++;
        }
        next[i] = k;
    }
    return next;
}

next数组的现实意义是在pattern中当前字符之前的最长前后缀长度。前后缀就是即是前缀，又是后缀，比如’abcddabc’，这里’abc’就是这个字符串的前后缀。next数组长度与pattern长度一致，next[i]的意义是，在pattern中截止到pattern[i]的子串的最长前后缀长度。要牢记next数组的意义，这会是KMP的重点应用范围，比如题214回文问题。

整个KMP算法，匹配过程并不难理解，主串的指针i从不回溯，一直在前进，而模式串的j指针则不断的跳转到其next数组指示的位置。核心仍是next数组的计算方式，有些难于理解，当作模板背下来也行。当涉及最长前后缀的题目时，就可以拿出next数组来使用。

典型题目

题目 题解 说明
28. 找出字符串中第一个匹配项的下标 题解 KMP板子题
214. 最短回文串 题解 next数组妙用
题解

参考资料

Comments