KMP算法|KMP算法 传统思路 适合初学者 便于理解
本文只是一个学习后的总结,可能会有错误,欢迎各位指出。任意转载。
题目:给定一个字符串 str1 和一个字符串 str2,在字符串 str1 中找出字符串 str2 出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
str1 = aaaaabcabc
str2 = abcabcaa
前段时间偶然接触到左神的算法讲解视频,大概三天的时间,反反复复把 KMP 算法看了三遍。终于有了一些自己的理解与体会。用传统的 KMP 算法去做字符串匹配,其实是用 next 数组对暴力算法的一个优化。另外一种理解是将 KMP 算法理解为动态规划,这里不详细叙述。
这里我分为三部分来讲。
- 暴力解法
- KMP 算法
- 如何求 next 数组
- str1[ i ] 和 str2[ j ]相等: i 和 j 都往后移动一位。
- str1[ i ] 和 str2[ j ]不等,j 归 0, i 从下一个初始位置开始比较。
如果 i 到达了最后一个初始位置,也就是 str1.length - 1 ,此时还没有匹配成功,那么说明永远都没办法匹配到 str2 。 这个时候返回 -1 。
代码:
public int strStr(String str1, String str2) {
int length1 = str1.length();
int length2 = str2.length();
if(length2 == 0) return 0;
if(length1 < length2) return -1;
int i = 0;
while(i < length1){
int j = 0;
while(i < length1 && j < length2
&& str1.charAt(i) == str2.charAt(j)){
i++;
j++;
}
if(j == length2){
return i-j;
}
i = i - j + 1;
}
return -1;
}
还是建议动手写一下。
KMP算法 这里暂时先不讨论 next 是如何来的。你需要知道它存放的是 str2 的一些信息。他的值等于 str2 前面的所有字符形成的字串的前缀等于后缀的最大值。这里非常绕,举个例子来说明:
index 等于 6 的时候, 字串是
a b c a b c
。前后缀取 1 的时候,前缀为 a, 后缀为 c,此时不等。 next 不能取 1 。
前后缀取 2 的时候,前缀为 ab, 后缀为 bc, next 不能取 2 。
前后缀取 3 的时候,前缀为 abc, 后缀为 abc, 此时相等, next 可以取 。
前后缀取 4 的时候,前缀为 abca, 后缀为 cabc, next 不可以取 4 。
前后缀取 5 的时候,前缀为 abcab, 后缀为 bcabc, next 不可以取 5 。
前后缀不可以取 6 。因为前后缀不可以为字符串本身。
index:0 1 2 3 4 5 6 7 8 9
str1 = a a a a a b c a b c
str2 = a b c a b c a a
next:-1 0 0 0 1 2 3 1
接下来是 KMP 算法的流程。按照暴力的解法,我们还是有两根指针 i 和 j。
- 两个元素相等时: i 和 j 往后移动一位。
- 两个元素不等时: j = next [ j ],如果此时 next[ j ] 等于 -1,说明 j 指针已经移动到了最前面。
next[j] != -1
,这种情况下,j 指针直接跳到 str2[next[j]]
去。为什么这样做可以?举例子。index
0 1 2 3 4 5 6 7
str1 =
a b c f a b c x
str2 =
a b c f a b c y
next=
-1 0 0 0 0 1 2 3
在 index 为 6的时候,i = j = 7,这个时候两个元素不相等,我们会把 j 跳到
str2[next[j]]
,也就是 j = 3
。这个时候 str1 前面的子串 和 str2 前面的子串是相等的,他们拥有共同的 next 数组。j 跳到 3,这个 3 代表: y/x 前面这个子串他的前三位和后三位相等。那么,我们的 y 的子串前三位 和 x 子串的后三位这个时候是不是就不需要比较了,因为这个 3 默认了他们相等。那么前三位(index为 0 1 2)就不需要比较了,直接比较第四(index 为 3 )位。这里就是 next 数组的核心。在左神的视频里面讲得更直观。str1 =
a b c f a b c x
str2 =
* * * * a b c f a b c y
比较 x 与 f 是否相等。
next[j] == -1
,这种情况下,j 已经来到最前面了,没办法继续前移,那么只能 i 向后移。代码:
public static int getIndexOf(char str1[], char str2[]) {
if(str1.length == 0 || str1.length < str2.length) {
return -1;
}
if(str2.length == 0) {
return 0;
}
int i = 0;
int j = 0;
int next[] = getNextArray(str2);
//对应三种情况
while( i < str1.length && j < str2.length) {
if(str1[i] == str2[j]) {
i++;
//两个元素相等
j++;
}else if(next[j] == -1) {
i++;
//next[j] == -1
}else {
j = next[j];
//next[j] != -1
}
}
return (j == str2.length) ? i-j : -1;
}
next数组 str2 =
a b c f a b c y
next=
-1 0 * * * * * *
第一位默认为 -1。 因为第一位元素没有子串。
第二位默认为 0。因为第二位元素的子串只有一个元素,那他的前后缀最大相等数目只能为0。
接下来是第三位,第三位的子串是
a b
,这里是难点。如何求出它的 next 值。j = 3
用 j - 1 的 next 的值,
cn = next[j-1]
的 str2 对应的元素, 和 str2[j-1]
比较。这里的cn = 0, 那比较的就是第 0 号元素和第 1 号元素的值。比较出来一定有两种情况,相等,不相等。而在不相等的时候又要分两种情况。index
0 1 2 3 4 5 6 7
str2 =
a b c f a b c y
next=
-1 0 0 0 0 1 * *
【KMP算法|KMP算法 传统思路 适合初学者 便于理解】为了更直观看见,我换个例子。j = 6.
cn = next[j-1] = 1, str2[cn] = b
str2[j-1] = b
这个时候是相等的,因此
next[6] = ++cn = 2
。为什么?这个 cn 代表的是什么?cn 代表的是
j-1
位的 next 值,这个值代表j-1
位的前后缀最大值。这个最大值是 1,说明他第一位和最后一位相等。那么比较他的第二位(str2[cn]
)和最后一位的下一位(str2[j-1]
)是否相等。相等的话,next[6] = ++cn = 2
。不相等怎么办?分为两种情况。cn > 0,cn = next[cn]
cn<= 0,next[j] = 0
str[j-1]
相等的 cn
,如果一直找不到呢?怎么办,那next[j] = 0
。代码:
public static int[] getNextArray(char []str) {
if(str.length == 1) {
return new int [] {-1};
}
int next[] = new int [str.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while( i < str.length) {
if(str[i-1] == str[cn]) {
next[i++] = ++cn;
}else if(cn > 0) {
cn = next[cn];
}else {
next[i++] = 0;
}
}
return next;
}
小结一下
- 暴力解法,多去写,多写两遍就熟练。
- KMP 具体实现,有三种情况。元素相等、元素不等且 next 不等于-1、元素不等且 next 等于 -1。
- next 的求解方法,也是三种情况。cn 和 j-1 对应的元素相等、 对应的元素不等且cn>0、 对应的元素不等且cn<=0。
推荐阅读
- 第326天
- 画解算法(1.|画解算法:1. 两数之和)
- Guava|Guava RateLimiter与限流算法
- 从我的第一张健身卡谈传统健身房
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的(传统文化与身心健康)教育体系心得体会
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- 虚拟DOM-Diff算法详解