KMP

1.发现问题

给定一个字符串s1 “aaaaaab”,以及一个模式字符串s2 “aaab”,如果要判断字符串2是否是字符串1的子串,即两个字符串是否匹配,正常情况下,我们会挨个比较,比如先判断s1[0]==s2[0],然后判断s1[1]==s2[1],然后是s1[2]==s2[2],然后是s1[3]!=s2[3],所以我们会从s1的第二个位置为起始位置,重新开始比较,即s1[1] == s2[0], s1[2]==s2[1], s1[3]==s2[2], s1[4]!=s2[3],然后会从s1的第三个位置为起始位置开始比较,……..,最终,时间复杂度是O(mn),m是s1的长度,n是s2的长度。


2.找到规律

上面这个例子我们可以发现,字符串的某些部分被重复比较了很多次,每次失败都是重头开始。我们发现其实只需要比较部分字符串即可,那些前缀后缀相等的字符就不用比较了。比如acbacx..acbaca...,比较到字符x和字符a时,不相等,按照我们前缀和后缀相等,就直接跳过前缀,直接比较后缀。即直接从串1的x字符和串2的b字符开始比较,即比较acx...acbaca...

3.如何求最长前缀后缀数组

前缀后缀数组的特点是前缀和后缀的字符相等,比如acbac的前缀后缀是ac,所以这个字符的最长前缀后缀就是ac。所以每个数组元素的值就是以当前位置index对应字符结尾的字符串的最长前缀后缀的长度。

比如acbac的最长前缀后缀数组为[0,0,0,1,2] (index=0位置默认为0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int[] computeTemporaryArray(char pattern[]){
int [] lps = new int[pattern.length];
int index =0;
for(int i=1; i < pattern.length;){
if(pattern[i] == pattern[index]){
lps[i] = index + 1;
index++;
i++;
}else{
if(index != 0){
index = lps[index-1];
}else{
lps[i] =0;
i++;
}
}
}
return lps;
}

4.KMP算法

利用前缀后缀数组,避免当不匹配时重新从模式字符串的头部开始匹配,也避免了从给定字符串的匹配位置的下一个位置开始。时间复杂度是O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean KMP(char []text, char []pattern){

int lps[] = computeTemporaryArray(pattern);
int i=0;
int j=0;
while(i < text.length && j < pattern.length){
if(text[i] == pattern[j]){
i++;
j++;
}else{
if(j!=0){
j = lps[j-1];
}else{
i++;
}
}
}
if(j == pattern.length){
return true;
}
return false;
}

代码参考:https://github.com/mission-peace/interview/blob/master/src/com/interview/string/SubstringSearch.java

5.例子



KMP
https://vickkkyz.fun/2022/05/16/计算机/LeetCoode/KMP/
作者
Vickkkyz
发布于
2022年5月16日
许可协议