字符串匹配算法－KMP理解

发表于 | 分类于

字符串匹配作为计算机的基本任务，有很多种算法可以高效的匹配字符串，其中Knuth-Morris-Pratt算法（简称KMP）是最常用的算法之一。可是很多人都觉得KMP难以理解，所以我就想试着理出一些头绪，如果能给你一些帮助，那就更好了。

字符串匹配包括模式串和目标串两部分数据，普通的匹配算法需要回溯即不匹配就后退一位，而KMP通过对模式串的分析，避免一些注定失败的匹配过程，使得时间复杂度从(M*N)降低到(M+N)。

KMP算法的高效性就在于next数组记录了当前字符不匹配的情况下模式串如何跳转，根据next数组记录的第一个元素的不同可以将KMP算法通过两种方式分析，第一种是传统的方式,next[0] = -1;第二种是最近看到的理解，next[0] = 0。接下来具体分析两种观点。

##传(晦)统(涩)的KMP算法解析##
传统的KMP算法中next数组的含义是当前位置的模式串字符与目标串字符不同时，模式串将要跳转的位置。举个例子，目标串S = ”abcabcabdabba”，模式串T = “abcabd”，然后构造next数组，算法如下:

  1. next[0] = -1，意义：任何模式串next的第一位都是-1。
  2. next[j] = k，意义：T[0]~T[k-1] = T[j-k]~T[j-1]且T[k] != T[j] (1 <= k < j)。
  3. next[j] = -1，意义：T[0]~T[k-1] = T[j-k]~T[j-1]且T[k] = T[j] (1 <= k < j)。
  4. next[j] = 0，意义：除上述情况的其他情况。

根据上述算法，可以得到T的next数组next[0] = -1，next[1] = 0是毫无疑问的；next[2] = 0，因为“ab”没有相同的子串；next[3] = 0，因为“abc”没有相同的子串；next[4] = -1，因为T[0] = T[3]且T[1] = T[4]；next[5] = 2,因为T[0]T[1] = T[3]T[4]。

在得到next数组之后如何跳转呢，这就是接下来要解决的问题。假设S和T匹配发现在S[m] != T[n]，对应到next[n]的三种情况，如下：

  • next[n] = -1，即T[0] = T[n]，由于T[n] != S[m]，所以比较S[m+1] == T[0]。
  • next[n] = 0，即T[0] != T[n]，比较S[m] == T[0]。
  • next[n] = k (1 <= k < n)，即T[0]~T[k-1] = T[n-k]~T[n-1] = S[m-k]~S[m-1]，比较S[m] == T[k]。

可以看出，传(晦)统(涩)的的KMP思路不复杂但是不太清晰，再加上很多教材上对next数组解释不清和一些莫名其妙的递归过程求next数组，使得我们很容易迷惑。

##新(聪)颖(明)的KMP算法解析##
相对于传统的事无巨细的KMP解析过程，这次的解析是从整体的角度来解析KMP算法，有一种高屋建瓴的快感。

仍然通过对目标串S，模式串T的匹配过程来分析。首先改变next数组的定义，next[n] = k，即T[0]~T[k] = T[n-k]~T[n]，跳转算法也要做相应的调整：向后移动的位数 = 当前匹配的字符数 - next[n] = (n - k)。

最重要的过程仍然是构造next数组，不同于传统的构造next数组方法的复杂，这次我们采用一种看起来比较简单的方法-通过字符串中前缀与后缀中共有的最长的字符串的长度作为next数组的元素值。

首先解释下前缀和后缀的概念：

字符串：bread

前缀：b，br，bre，brea

后缀：d，ad，ead，read

如果模式串T = “ABCDABD”，构造next数组：

  • “A”前缀和后缀都为空集，共有的为空，则next[0] = 0
  • “AB”前缀为[A]，后缀为[B]，共有的为空，则next[1] = 0
  • “ABC”前缀为[A，AB]，后缀为[C，BC]，共有的为空，则next[2] = 0
  • “ABCD”前缀为[A，AB，ABC]，后缀为[D，CD，BCD]，共有的为空，则next[3] = 0
  • “ABCDA”前缀为[A，AB，ABC，ABCD]，后缀为[A，DA，CDA，BCDA]，共有的为[A]，则next[4] = 1
  • “ABCDAB”前缀为[A，AB，ABC，ABCD，ABCDA]，后缀为[B，AB，DAB，CDAB，BCDAB]，共有的为[AB]，next[5] = 2
  • “ABCDABD”前缀为[A，AB，ABC，ABCD，ABCDA，ABCDAB]，后缀为[D，BD，ABD，DABD，CDABD，BCDABD]，共有的为空，则next[6] = 0

代码：

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
58
/*
 * Created-On: 2013-10-11
 * Author: Arthur_Wang
 * KMP point: construct jump array, store short string jump information
 * long, short = "BBC ABCDAB ABCDABCDABDE", "ABCDABD"
 */
public class KMP {
	private String longString, shortString;
	private int[] jumps;
	public KMP(String longString, String shortString) {
		this.longString = longString;
		this.shortString = shortString;
		jumps = new int[shortString.length() + 1];
		jumps[0] = jumps[1] = 0;
	}
	public void find() {
		for (int i = 0; i < shortString.length() - 1; i++)
			jumps[i + 2] = next(i);
		for (int i : jumps)
			System.out.print(i + " ");
		int i = 0, j = 0;
		System.out.println("Start");
		while (i < longString.length() && j < shortString.length()) {
			if (longString.charAt(i) == shortString.charAt(j)) {
				j++;
				i++;
			} else if (j == 0)
				i++;
			else
				j = jumps[j];
		}
		if (j == shortString.length())
			System.out.println(i);
		else
			System.out.println("failed");
	}
	public int next(int index) {
		if (jumps[index + 1] > 0) {
			if (shortString.charAt(index + 1) == shortString
					.charAt(jumps[index + 1]))
				return jumps[index + 1] + 1;
			else
				next(jumps[jumps[index + 1]]);
		}
		if (shortString.charAt(0) == shortString.charAt(index + 1))
			return 1;
		return 0;
	}
	public static void main(String... args) {
		KMP kmp = new KMP("BBC ABCDAB ABCDABCDABDE", "ABCDABD");
		kmp.find();
	}
}

##结论##
有的读者可能已经看出来上文两种方法其实没有本质的不同，最大的区别在于两者构造next数组的过程，第二种方式从整体上考虑模式串的特征，直观看起来更容易理解，如果有不同看法，欢迎交流！

参考资料

声明：欢迎转载，请注明出处。