KMP算法:从入门到推导

By Long Luo

之前虽然知道KMP算法,但是一直无法深入理解其原理,最近看了2篇文章:从头到尾彻底理解KMP(2014年8月22日版)KMP算法教程,然后再实际写代码,终于对KMP算法有了一定了解了,下面写一写我个人的学习过程。

这篇文章主要从我个人学习过程来叙述:

为了解决什么问题?

KMP算法是一种字符串匹配算法,可以在O(n+m)的时间复杂度内实现两个字符串的匹配。

所谓字符串匹配,是这样一种问题:字符串P是否为字符串S的子串?如果是,它出现在S的哪些位置?

其中S称为主串;P称为模式串

最常见的就是经常要用的搜索功能,比如要在一大段文字中找到某个句子或者找到出现的全部位置。在这种场景下,要找的句子就是给定的模式P,而大段文字就是目标字符串S。

从暴力法开始

我们先从最直观的地方开始:

  1. 两个字符串A, B的比较?
  2. 如果P是S的字串,第一个出现的位置在哪里?

所谓字符串比较,就是问两个字符串是否相等

最朴素的思想,就是从前往后逐字符比较,一旦遇到不相同的字符,就返回False;如果两个字符串都结束了,仍然没有出现不对应的字符,则返回True。实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int Search_BruteForce(String targetStr, String patternStr) {
int targetLen = targetStr.length();
int patLen = patternStr.length();

for (int i = 0; i < targetLen; i++) {
if (targetStr.charAt(i) == patternStr.charAt(i)) {
for (int j = 1; j < patLen; j++) {
if (targetStr.charAt(i + j) != patternStr.charAt(j)) {
break;
}

if (j == patLen - 1) {
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
public static int ViolentMatch(String targetStr, String patternStr) {
int targetLen = targetStr.length();
int patLen = patternStr.length();

int i = 0;
int j = 0;
while (i < targetLen && j < patLen) {
if (targetStr.charAt(i) == patternStr.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}

if (j == patLen) {
return i - j;
} else {
return -1;
}
}

刚才我们成功实现了暴力算法,那么其时间复杂度如何?

记n为串S的长度,m为串P的长度。

考虑“字符串比较”这个小任务的复杂度。最坏情况发生在:两个字符串唯一的差别在最后一个字符。这种情况下,字符串比较必须走完整个字符串,才能给出结果,因此复杂度是O(len)的。

由此,不难想到暴力算法所面对的最坏情况:

主串形如“AAAAAAAAAAAAA…B”,而模式串形如“AAAAA…B”。每次字符串比较都需要付出O(m)次字符比较的代价,总共需要比较n次,因此总时间复杂度是O(nm)。

那么如何改进呢?

信息熵冗余

我们很难降低字符串比较的复杂度(因为比较两个字符串,真的只能逐个比较字符)。因此,我们考虑降低比较的趟数。如果比较的趟数能降到足够低,那么总的复杂度也将会下降很多。

要优化一个算法,首先要回答的问题是“我手上有什么信息?” 我们手上的信息是否足够、是否有效,决定了我们能把算法优化到何种程度。请记住:尽可能利用残余的信息,是KMP算法的思想所在。

很明显在暴力算法中,模式字符串每次都需要比较,非常复杂,那么这里面有没有优化的时间呢?

这里我直接引用参考文档里的说明:

假设现在文本串S匹配到i位置,模式串P匹配到j位置:

  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;

  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令i不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了**j - next[j]**位。换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next值,即移动的实际位数为:j - next[j],且此值大于等于1。

你也会意识到next数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。例如如果next[j] = k,代表j之前的字符串中有最大长度为k的相同前缀后缀。

此也意味着在某个字符失配时,该字符对应的next值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next[j]的位置)。如果next[j]等于0或-1,则跳到模式串的开头字符,若next[j]=k且k > 0,代表下次匹配跳到j之前的某个字符,而不是跳到开头,且具体跳过了k个字符。

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int KMP(String target, String pattern) {
int i = 0;
int j = 0;
int txtLen = target.length();
int patLen = pattern.length();

int[] next = buildNextArray(pattern);

while (i < txtLen && j < patLen) {
if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}

if (j == patLen) {
return i - j;
} else {
return -1;
}
}

如何求Next数组?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] buildNextArray(String pattern) {
int len = pattern.length();
int[] next = new int[len];
next[0] = -1;
int i = -1;
int j = 0;
while (j < len - 1) {
if (i == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (pattern.charAt(i) != pattern.charAt(j)) {
next[j] = i;
} else {
//因为不能出现p[j] = p[next[j]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
next[j] = next[i];
}
} else {
i = next[i];
}
}

return next;
}

小结

KMP算法是一个很重要的算法,但是我们不光要知其然还要知其所以然,所以需要认真吃透其方法,详细了解其具体实现,才能真正掌握这一算法。不光知道,还需要达到可以直接手写代码的水平。