一直走，一直走……

KMP算法

Posted on | In

KMP算法是字符串算法中经典的算法之一，本文仅作记录理解之用，其中有参考《严书》和他人博客，建议先看《严书》。

1. KMP算法的由来

KMP算法是解决字符串匹配问题。

问题：字符串匹配，一个主串，一个模式串，模式串是否在主串中，如果在，求出第一个字符的下标。

正常解法： 一个字符一个字符比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//s是主串，p是模式串，返回模式串在主串中的起始下标，如果不存在，返回-1
int get_substring(char *s, int slen, char *p, int plen)
{
	int i = 0;
	int j = 0;
	int index = -1;
	for (; i <= slen - plen; i ++) {
		int mov = 0;
		while (mov < plen && s[i + mov] == p[j + mov])
			++ mov;
		if (mov == plen)
			index = i;
	}
	return index;
}

严书的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//返回模式串P在主串S中第pos个字符之后的位置，若不存在，返回-1
//C中是没有string类型的，这里为了简便
int index_substring(char *s, char *p, int pos)
{
	int i = pos;
	int j = 0;
	int slen = strlen(s);
	int plen = strlen(p);
	while (i < slen && j < plen) {
		if (s[i] == p[j]) {
			++ i;
			++ j;
		} else {
			i = i - j + 1;
			j = 0;
		}
	}
	if (j == plen)
		return i - j;
	else
		return -1;
}

这种方法太低效，时间复杂度接近O(n * m)，所以，是否可以利用已经部分匹配的信息，减少回溯的次数，让模式串尽可能快速移动到合适的位置。

那么，问题来了， 当主串的指针i和模式串的指针j不匹配时，模式串的指针j应该移动到哪个位置？

于是，KMP算法就有了。

2. KMP算法

先介绍Next数组的含义。

2.1 next数组的含义

next[j] = k，当主串的指针i和模式串的指针j不匹配时，模式串的指针j应该移动到指针k，主串指针i不需要回溯。

先举个例子，明白next[j] = k等式的含义。

next[j] = k，k的含义指模式串的前k个字符和其最后的k个字符相同(下标从0开始)。

KMP图

2.2 理解next数组的正确

主串用T[i]表示，模式串用P[j]表示，下标从0开始。

从严谨角度来看，请参考《严书》的数学归纳法证明。

本文以理解为主。

1
2
3
4
5
当 T[i] != P[j]时，
  有 T[i-j ~ i-1] == P[0 ~ j-1]
  已知 P[0 ~ k-1] == P[j-k ~ j-1]
  再把j修改为k，则有 T[i-k ~ i-1] == P[0 ~ k-1]， 所以主串的指针i和模式串的指针k比较，
  结果是：主串的指针i不需要回溯，模式串的指针j回溯到指针k，而不是回溯到第一个。

2.3 如何求出next数组

求出过程，是数学归纳法，也是递推过程。

当j=0时，即模式串中第一个不匹配时，有next[0] = 0； 我们先不管初始条件，否则容易乱。

假设当next[j] = k，next数组含义知有，P[0 ~ k-1] == P[j-k ~ j-1]。

那么next[j+1]是？:sweat_smile:

​ 分为两种情况：

  1. 当p[k] == p[j]时，有P[0 ~ k-1~k] == P[j-k ~ j-1~j]，则有next[j+1] = k+1 = next[j] + 1;
  2. 当p[k] != p[j]时，这又是一个字符串匹配问题，整个模式串既是是主串又是模式串，应当将模式串中P[j]和P[next[k]]比较，由已知得，有next[k] = m，当p[j] == p[m]，则有P[j-m+1 ~ j] = p[0 ~ m]，即next[j+1] = m + 1 = next[k] + 1；当p[j] != p[m]时，依次类推，最后next[j+1] = 0（j >= 0）；

最后，我们来看初始条件。有next[1] = 0，显然当模式串中第一个字符和主串的字符不匹配时，是应该从下标0开始比较。在求解next数组过程中，有公式next[j+1] = next[j] + 1，所以，next[0] = -1，也就是说，初始条件是，j = 0，k = -1。

根据求next数组的递推关系，求next数组的递归代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
//递归代码， arr是next数组
void next(int arr[], int index, char *p)
{
	if (index == 0)
		arr[index] = -1;
	else {
		int tmp = arr[index - 1];
		if (p[index -1] == p[tmp])
			arr[index] = tmp + 1;
		else 
			next(arr, index - 1, p);
	}
}

求next数组的非递归代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
//非递归代码
void get_next(int arr[], int len, char *p)
{
	int j = 0;
	int k = -1;
	next[0] = -1;
	while (j < len) {
		if (k == -1 || p[j] == p[k])
			arr[++ j] = ++ k;
		else 
			k = next[k];
	}
}

2.4 改进的next数组

2.3中求next数组存在另外的问题，比如主串s ‘aaabaaaab’和模式串p ‘aaaab’，next数组值如下，

j 0 1 2 3 4
模式 a a a a b
next[j] -1 0 1 2 3
nextval[j] 0 0 0 0 4

当i = 3，j = 3时，主串和模式串不匹配，根据求出的next数组，仍然会依次比较i = 3，j = 0、1、2，实际上因为p[0] == p[1] == p[2]，是不需要再进行比较的，所以改进的next数组nextval。

求nextval数组的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void nextval(int arr[], int len, char *p)
{
	int j = 0;
	int k = -1;
	arr[0] = -1;
	while (j < len) {
		if (k == -1 || p[j] == p[k]) {
			if (p[j + 1] == p[k + 1])
				nextval[++ j] = nextval[++ k];
			else
				nextval[++ j] = ++ k;
		} else {
			k = nextval[k];
		}
	}
}

【未完待续】

3. 参考

[1] http://www.cnblogs.com/tangzhengyue/p/4315393.html

[2] 严书《数据结构》