KMP算法
一 . 问题场景
有字符串A和字符串B,求B在A中首次出现的位置。力扣题目链接:28. 找出字符串中第一个匹配项的下标 - 力扣(LeetCode)
为方便说明,规定A为主串,B为子串(模式串)
二. 朴素的匹配算法
为方便说明,举A = "aabaaf"
,B="aaf"
使用如下图所示的算法(图中只显示了前两趟匹配)
代码实现如下
class Solution {
public int strStr(String haystack, String needle) {
for(int index = 0; index <= haystack.length() - needle.length(); index++){
int i = index;
int j = 0;
while(j <= needle.length() - 1){
if(haystack.charAt(i) == needle.charAt(j)){
if(j == needle.length() - 1){
return index;
}
i++;
j++;
}else{
break;
}
}
}
return -1;
}
}
三. KMP算法
1.算法由来
因为是由这三位学者发明的:Knuth,Morris和Pratt,所以取了三位学者名字的首字母。所以叫做KMP
2.算法思想
在匹配主串aabaaf
与子串aaf
的第一趟匹配中,是在b
和f
的位置发生的失配,说明前两个位置的字符是匹配上的。利用这个信息,我们可以在回溯时,不让index
变为index + 1
,i
往回退,而是只让j
往回走。
如图所示
如果在发生失配的模式串的前一部分,满足A1=A2,由于前一部分已经匹配上了,所以有B1=A1,B2=A2,所以有A1=B2,所以在下一次匹配时,应直接让i
不动,j
移动到n
的位置进行匹配。每次发生失配时,j现在的位置 -> j之后的位置
构成的映射可以用一个函数来表示,即next[j现在的位置] = j之后的位置
,只要算出这个映射,接下来再在每次失配时根据映射next
查找j
应该在的位置,就完成了模式串匹配。
3.next求法
为求解next数组,规定字符串前缀:除最后一个字符外的其他字符构成的字符串;字符串后缀:除第一个字符外其他字符构成的字符串。字符串s的next数组为next[i] = s[0 : i + 1]的最长相等前后缀
(s[i : j]
为s中[i, j)
的字符)。
3.1 手算过程
比如,对于aaabaaac
0处字符为a
,没有前后缀,next[0] = 0;
1处字符为aa
,前缀为a
,后缀为a
,最长相等前后缀为a
,next[1] = 1;
......
6处字符为aaabaaa
,前缀为aaabaa
,后缀为aabaaa
,找最长相等的前后缀过程(手算过程,机器实现不是这样,因为复杂度太高)
考虑aaabaa
和aabaaa
,两者不同
考虑aaaba
和abaaa
,两者不同
考虑aaab
和baaa
,两者不同
考虑aaa
和aaa
,两者相同,所以最长相等前后缀为aaa
,长度为3,next[6] = 3;
7处同理。
其next数组为{0, 1, 2, 0, 1, 2, 3, 0}
3.2 机算过程
显然上面手算方法的复杂度达到了O(N^2),不可取,应使用动态规划的方式进行求解。
求next[i]的值,分两种情况讨论
s[i] == s[now]和s[i] != s[now] (now = next[i - 1],即最长前缀的后一个位置)
用cpp写的伪代码如下(求解过程在注释中)
void getNext1(int* next, const string& s){
next[0] = 0;
//i指示是求谁的next数组
for(int i = 1; i < s.length(); i++){
//定义s[0: now]指的是{s[0], s[1], ..., s[now - 1]}
//now指示最长前缀的后一个位置
int now = next[i - 1];
//step1(s[now] == s[i])
//此时,在s[0 : i]中,有s[0 : now] == s[i - now : i],且为最长相等前后缀,长度为now (next[i - 1] == now) (条件1)
//如果s[now] == s[i],则有s[0 : now + 1] == s[i - now : i + 1]
//假设在s[0 : i + 1]中,s[0 : now + 1]不是最长相等前缀,s[0 : now + 1 + t]才是
//那么s[0 : now + 1 + t] == s[i - now - t : i + 1]
//那么s[0 : now + t] == s[i - now - t : i],其长度为now + t,且为s[0 : i]中相等的前后缀
//这与条件1矛盾
//所以在s[0 : i + 1]中,s[0 : now + 1]是最长相等前缀,因此可以算得s[0 : i + 1]的最长相等前后缀长度为now + 1
if(s[now] == s[i]){
next[i] = now + 1;
continue;
}
/*step2(s[now] != s[i])
此时,在s[0 : i]中,有s[0 : now] == s[i - now : i],且为最长相等前后缀,长度为now (next[i - 1] == now) (条件1)
如果s[now] != s[i],就要减小now到k,使得s[0 : k] == s[i - k : i],k < now,求k值
令next[now - 1] = t,显然t < now (条件2)
则在s[0 : now]中,s[0 : t] == s[now - t : now]
又由条件1,s[0 : now] == s[i - now : i],
所以,s[0 : t] == s[i - now : i - now + t] == s[i - t : i]
即s[0 : t] == s[i - t : i],t < now
所以t就是我们要的k,所以k = t = next[now - 1] (条件2),此时再比较s[k]是否==s[i],不等就继续到step2
直到s[k] == s[i]或者k == 0
*/
/*
如果循环到最后s[k] == s[i],就使用step1的逻辑(即使是因为k == 0出来的也一样)
如果循环到最后s[k] != s[i],说明到前后缀没有公共部分,取0即可
*/
while(now >= 1 && s[now] != s[i]){
now = next[now - 1];
}
if(s[now] == s[i]){
next[i] = now + 1;
}else{
next[i] = 0;
}
}
}
4.匹配过程
匹配的过程如下所示
public int strStr(String haystack, String needle) {
int[] next = getNext(needle);
int i = 0; //指示主串
int j = 0; //指示子串
while(i < haystack.length()){
if(haystack.charAt(i) == needle.charAt(j)){ //i与j匹配上了
if(j == needle.length() - 1){ //i与j匹配到了子串末尾,说明匹配成功
return (i - needle.length() + 1);
}
i++;
j++;
}else{ //i与j没有匹配上
//失配的位置不是needle[0]
if(j != 0){
j = next[j - 1];
}else{//失配的位置是needle[0]
i++;
}
}
}
return -1;
}
5.完整代码
完整代码如下所示
class Solution {
public int strStr(String haystack, String needle) {
int[] next = getNext(needle);
int i = 0; //指示主串
int j = 0; //指示子串
while(i < haystack.length()){
if(haystack.charAt(i) == needle.charAt(j)){
if(j == needle.length() - 1){
return (i - needle.length() + 1);
}
i++;
j++;
}else{
//失配的位置不是needle[0]
if(j != 0){
j = next[j - 1];
}else{//失配的位置是needle[0]
i++;
}
}
}
return -1;
}
//求next数组
public static int[] getNext(String s){
int[] next = new int[s.length()];
next[0] = 0;
//求1到s.length() - 1的next,i为所求的next数组的位置
for(int i = 1; i < next.length - 1; i++){
//now始终为最长相同前后缀中,相同前缀的后一个位置
int now = next[i - 1];
//处理s[i] == s[now]
if(s.charAt(i) == s.charAt(now)){
next[i] = now + 1;
continue;
}
//处理s[i] != s[now]
while(now >= 1 && s.charAt(i) != s.charAt(now)){
now = next[now - 1];
}
if(s.charAt(i) == s.charAt(now)){
next[i] = now + 1;
}else{
next[i] = 0;
}
}
return next;
}
}
标签:匹配,int,needle,next,后缀,算法,KMP,now
From: https://www.cnblogs.com/tryingWorm/p/17437153.html