本期讲讲 KMP 算法,也就是江湖俗称的<del>看毛片</del>算法。
这个算法其实在面试中出现的概率还是蛮大的,不管是校招还是社招,甚至在考研中也遇到过,而且 KMP 算法也比较难理解,所以很有必要研究一下。
先说一下这个算法出现的背景,也就是解决什么问题。每个算法和框架都有它出现的原因和要解决的问题,很多时候你不会一个技术,并不是你笨,而是你没有找到它的使用场景或者是没搞明白它要解决的问题而已。所以,了解它要解决的问题,是学习的重中之重。
首先看一个例子:
字符串 str="abcabcabcde",字符串 match="abcabcde"
如果 str 包含子串 match,返回 match 在 str 中的起始位置。
这个问题其实可以使用暴力来破解,如下图:
从 str[i]开始( i 初始等于 0 ),每次只要遇到了 match 和 str 不匹配的情况,str 回退到 str[i+1],再继续 str[i+1]和 match[0]依次对比,长此以往,直到 match 完全匹配出来或者 str 遍历完毕为止,这样做的时间复杂度是 O(M*N),M 是 str 的长度,N 是 match 的长度。
那么有没有种方法可以不这么笨拙的解决字符串匹配的问题呢?
KMP 算法就是解决 match 和 str 在匹配过程中不停的做回退的问题的。简单一句话,KMP 算法是做字符串高效匹配的算法
说 KMP 的解法之前,先看看一个聪明的人类是如何解决这个问题的:
这样做的原因是没必要一次性退回从 match[0]和 str[1]开始比较,因为可以看出来绿色框内的 match[0,1,2]和 str[3,4,5]是重合的,重合的这部分完全可以复用,没有必要再从 match[0]和 str[1]开始重复比较;
具体的过程可以模拟抽象成下图:
所以问题转化成了:
每次 str[j]和 match[j]不相同时,在 match[0...j-1]这段字符串中,以 match[j-1]结尾的后缀子串(不能包含 match[0])和以 match[0]开头的前缀子串(不能包含 match[j-1])的最大匹配长度是多少?只要求出这个最大匹配长度,就能在 str[j]和 match[j]不相同时,知道把 match 滑动到什么位置了!
KMP 算法的重点就是维护一个数组,保存 match 中每个字符在不匹配时,match 应该滑动到什么位置,这个数组起名叫 next。
那么如何构造 next 数组呢?
首先对于 match[0]来说,它前面没有字符,所以 next[0]规定为-1 ;对于 match[1]来说,因为 next 数组规定计算的时候子串后缀不能包含第一个字符,所以 next[1]=0 ;
说完特殊情况,再说说常规情况,比如现在假设 match[i]是 A 字符,match[i-1]是 B 字符,可以通过 next[i-1]得到 B 字符前的字符串最长前缀与后缀的匹配区域,现在假设 L 为最长前缀子串,K 为最长后缀子串,C 为最长前缀子串之后的一位字符,现在只需要比较 C 和 B 即可
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(str, match) {
if(str === null || match === null || match.length > str.length)
return -1;
if(str === "")
return 0;
let index1 = 0;
let index2 = 0;
let nextArr = getNext(match);
console.log(nextArr);
while(index1 < str.length && index2 < match.length) {
if(str[index1] === match[index2]) {
index1++;
index2++;
} else if(nextArr[index2] === -1) {
index1++;
} else {
index2 = nextArr[index2];
}
}
return index2 === match.length ? index1 - index2 : -1;
};
var getNext = function(match) {
let next = [-1, 0];
let cn = 0;
let index = 2;
while(index < match.length) {
if(match[index-1] === match[cn]) {
cn++;
next[index] = cn;
index++;
}
else if(cn > 0) {
cn = next[cn];
}
else {
next[index] = 0;
index++;
}
}
return next;
}
class Solution {
public int strStr(String str, String match) {
if(str == null || match == null || str.length() < match.length()) {
return -1;
}
if(str.length() < 1) {
return 0;
}
char[] strs = str.toCharArray();
char[] matches = match.toCharArray();
int index1 = 0;
int index2 = 0;
int[] next = getNextArr(matches);
while (index1 < strs.length && index2 < matches.length) {
System.out.println(index2);
if(strs[index1] == matches[index2]) {
index1++;
index2++;
} else if(next[index2] == -1) {
index1++;
} else {
index2 = next[index2];
}
}
return index2 == matches.length ? index1 - index2 : -1;
}
public int[] getNextArr(char[] match) {
if(match.length == 1) {
return new int[] {-1};
}
int[] next = new int[match.length];
next[0] = -1;
next[1] = 0;
int index = 2;
int cn = 0;
while(index < match.length) {
if(match[index-1] == match[cn]) {
cn++;
next[index] = cn;
index++;
} else if(cn > 0) {
cn = next[cn];
} else {
next[index] = 0;
index++;
}
}
return next;
}
}
1
zzzzzzggggggg OP 个人觉得还是讲的很清楚的
|
2
zzzzzzggggggg OP up
|
3
ericgui 2020-03-15 08:17:19 +08:00
@zzzzzzggggggg 有 java 版本的实现么?
|
5
WhatIf 2020-03-15 09:18:57 +08:00 via Android
想起当年读书时候自学数据结构,书上介绍这个算法,花了一周以上时间才明白说的是什么,后来又是忘得差不多了。再后来,看到这个算法时候,却觉得是自然而然的
|
6
zzzzzzggggggg OP @WhatIf 对,有的时候就是那一瞬间就悟了
|
7
zzzzzzggggggg OP @ericgui 有的,今天我补充一个 Java 版本的
|
8
zzzzzzggggggg OP @ericgui 老铁可以看下,我补充了 Java 的解法,好久没写 Java 了语法不太熟悉,还请担待
|
9
ericgui 2020-03-15 12:02:09 +08:00
@zzzzzzggggggg
if(str.length() < 1) { return 0; } 改成 if (str.length == 0 || p.length() == 0) return 0; 那不然会有一个 corner case 报错 corner case 是 => str = ""; match = ""; |
10
zzzzzzggggggg OP @ericgui 好嘞,确实忽略了 match 也是空字符串的 case
|
11
ericgui 2020-03-15 13:37:55 +08:00
@zzzzzzggggggg 我也是用这算法上 leetcode 试了试,才发现有 corner case
|
12
zzzzzzggggggg OP @ericgui 是国内版的还是国外版的 LeetCode,我在国内版的试了下是可以通过的😅
|
13
ericgui 2020-03-16 00:29:03 +08:00
@zzzzzzggggggg 英文版,28 题
|
14
zzzzzzggggggg OP @ericgui 好嘞
|