算法介绍
KMP 算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的,KMP 算法的时间复杂度 O(m+n)。
相同前后缀
KMP 算法之所以能够快速匹配,主要是因为在迭代过程中并不是逐个查找,而是根据模式串的最长相同前后缀表进行跳跃查找。这里的相同前后缀指的是字符串中前缀和后缀相同的子串,不包括整个字符串。
示例 1:“aba”,“a”既是“aba”的前缀,也是“aba”的后缀,所以“a”就是“aba”的相同前后缀。
示例 2:“ababa”,“a”是“ababa”的相同前后缀,“aba”也是“ababa”的相同前后缀。
下面演示“abacabad”的最长相同前后缀表是如何得到的。
i
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
子串
|
a
|
ab
|
aba
|
abac
|
abaca
|
abacab
|
abacaba
|
abacabad
|
最长相同前后缀
|
-
|
-
|
a
|
-
|
a
|
ab
|
aba
|
-
|
table
|
0
|
0
|
1
|
0
|
1
|
2
|
3
|
0
|
查找演示
看看 KMP 算法如何使用最长相同前后缀表进行查找。
字符串,“abacabaabacabad”
模式串,“abacabad”
匹配图解
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
字符串 |
a✅ |
b✅ |
a✅ |
c✅ |
a✅ |
b✅ |
a✅ |
a❎ |
b |
a |
c |
a |
b |
a |
d |
模式串 |
a✅ |
b✅ |
a✅ |
c✅ |
a✅ |
b✅ |
a✅ |
d❎ |
|
|
|
|
|
|
|
j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
|
|
|
最长前后缀表 |
0 |
0 |
1 |
0 |
1 |
2 |
3 |
0 |
|
|
|
|
|
|
|
字符串和模式串前 7 个字符都能匹配上,当 i=7,j=7 时,匹配失败。如果是暴力查找,那么就需要让 i=1,j=0,然后重新开始匹配,如下:
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
字符串 |
a |
b❓ |
a |
c |
a |
b |
a |
a |
b |
a |
c |
a |
b |
a |
d |
模式串 |
|
a❓ |
b |
a |
c |
a |
b |
a |
d |
|
|
|
|
|
|
j |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
|
|
如果是 KMP 算法会是怎样呢?
直接将模式串已成功匹配的前缀“aba”和字符串已成功匹配的“aba”对齐,让 i=7,j=3,然后继续匹配。如下:
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
字符串 |
a |
b |
a |
c |
a✅ |
b✅ |
a✅ |
a❓ |
b |
a |
c |
a |
b |
a |
d |
模式串 |
|
|
|
|
a✅ |
b✅ |
a✅ |
c❓ |
a |
b |
a |
d |
|
|
|
j |
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
最长前后缀表 |
|
|
|
|
0 |
0 |
1 |
0 |
1 |
2 |
3 |
0 |
|
|
|
因为只有模式串成功匹配的子串“abacaba”中的某个前缀和字符串中已经匹配成功的子串“abacaba”中的某个后缀相同,后续的比较才有意义,而且只有取最长的相同前后缀才不会遗漏可能的匹配,而“aba”就是“abacaba”的最长相同前后缀。
i=7,j=3 匹配失败,所以继续将模式串已成功匹配的前缀“a”和字符串已成功匹配的“a”对齐,让 i=7,j=1,然后继续匹配。如下:
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
字符串 |
a |
b |
a |
c |
a |
b |
a✅ |
a❓ |
b |
a |
c |
a |
b |
a |
d |
模式串 |
|
|
|
|
|
|
a✅ |
b❓ |
a |
c |
a |
b |
a |
d |
|
j |
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
最长前后缀表 |
|
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
2 |
3 |
0 |
|
i=7,j=1 匹配失败,因为已成功匹配的子串没有相同前后缀,所以将模式串整体后移和字符串未匹配成功的字符对齐,让 i=7,j=0,然后继续匹配下去。如下:
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
字符串 |
a |
b |
a |
c |
a |
b |
a |
a✅ |
b✅ |
a✅ |
c✅ |
a✅ |
b✅ |
a✅ |
d✅ |
模式串 |
|
|
|
|
|
|
|
a✅ |
b✅ |
a✅ |
c✅ |
a✅ |
b✅ |
a✅ |
d✅ |
j |
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
最长前后缀表 |
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
2 |
3 |
0 |
最终匹配完成,从第一第二阶段来看,KMP 算法比暴力查找算法少了很多无用的循环,所以效率比较比暴力查找自然快多了。注:KMP 算法时间复杂度是 O(m+n),暴力查找是 O(m*n)。
算法实现
public int strStr(String text, String pattern) {
if ("".equals(pattern)) {
return 0;
}
int[] table = new int[pattern.length()];
int i = 0, j = 1;
while (j < table.length) {
if (pattern.charAt(i) == pattern.charAt(j)) {
table[j++] = i + 1;
i++;
} else {
if (i == 0) {
j++;
} else {
i = table[i - 1];
}
}
}
i = 0;
j = 0;
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
if (j == 0) {
i++;
} else {
j = table[j - 1];
}
}
if (j == pattern.length()) {
return i - j;
}
}
return -1;
}
视频讲解
- 在 YouTube 上查看请点击https://youtu.be/kUaiHxkX7lY
- 在 B 站上查看请点击https://www.bilibili.com/video/BV1bi4y1x7As
- 在西瓜视频上查看请点击https://www.ixigua.com/i6840806957645824516