前言
最近学校对数据结构的串部分KMP算法进行了讲解,出于好奇,感觉这个代码简洁干练,但思想有很我发现KMP算法确实很巧妙,所以在此想做一个总结,分享给大家.子字符串查找问题,历史上有很多种方法,都是在此问题上,提高整体的效率,提炼出一个简洁,时间复杂度较低的算法.这篇博客介绍的KMP算法求解子字符串问题就是由Knuth,Morris,Pratt三位大佬创建出来的.
问题描述
子字符串查找,给定一个长度位N的文本字符串和一个长度为M的模式字符串,在文本中找到和该模式字符串相符的子字符串.求文本文件满足要求的字符串的首元素下标.
文本:a b c a b c a b c f,模式串:c a b c a,你可能一看就知道答案时2,但是当文本字符串足够长,长度达到一万,甚至十万,此时如果还是采用”肉眼观察法”,就很难观察的出来,往往黑客盗取密码就是在几万行代码中输入Password关键词找到相应的位置,来达到目的.
说到这里,可能有人会觉得可以采用暴力的方法求解(Brute Force),如下图:
我们发现暴力算法,每一次与模式串比较,最终文本串都需要回溯一遍,那有没有一种方法可以让文本串中的指针i不进行回溯呢,KMP算法就是如此.
; KMP算法思想
以上面的问题为例子,使用KMP算法求解.与暴力求解算法不同的地方是, KMP算法中的指针i不需要回溯,指针j也不一定会回退到起始位置,指针j回退的位置是由模式串决定的,通过指针j回溯,总能满足指针i回溯到某个位置,让指针i不回溯.
在讲解KMP算法之前,我们首先需要了解一个概念,字符串的前后缀
字符串 abcabc
前缀的集合: {a,ab,abc,abca,abcab}
后缀的集合: {c,bc,abc,cabc,bcabc}
此时的字符串abcabc 最长相等前后缀 就是abc,此时的长度就是3,通过上述的具体例子,我相信这个概念大家都能看得懂.大家可以自己找两个例子试一试. 这个概念在后续的问题求解中很重要!
前面讲到,KMP算法的核心就是指针i不动,找到指针j移动的位置,按照暴力求解的方式,指针j理论上会回退到零的位置,但是KMP算法并不是这样,如果你明白对指针j回溯的位置,这个算法你就能理解的差不多了.我们是通过一个next数组来记录模式串每一个位置,如果不匹配的情况下,指针j就回溯到该数组对应值的位置.
详解next数组
这是上课课本上的公式,反正我开始也是没看懂.next[i]的值表示下标为i的字符 前的字符串最长相等前后缀的长度。起始数组next的值只是与模式串本事有关,也就是给出一个模式串,就能给出这个模式串每个下标位置对应的next数组中的值.令起始位值next[0] == -1,所以next[1] == 0,因为没有最长相等前后缀,数组后面值都是通过求该位置 前的字符串最长相等前后缀.如果没有最长相等前后缀,那么此时值位0.
举个栗子 模式串: a b c a b c a a a.
模式串abcabcaaai012345678next[i]-100012341
下面给出一个例子,可以自己试一试
模式串:a b c a b c a b c.
模式串abcabcabci012345678next[i]-100012341
; 用图解释next数组的回溯
那我们现在可以得到next数组,那具体怎么理解它呢?下面给出文本串abcababcabc和模式串abcabc,其中红色部分为不匹配的部分,白色部分为相等部分.
前面讲到的最长相等前后缀在这里就起到了作用,不难发现白色部分同样也存在相等前后缀的情况,根据KMP的思想,我们就可以将模式串向后移动了.
模式串怎么移动呢
因为模式串和文本串不匹配时,前面白色部分字符串是完全一样的,所以 将文本串最长相等前后缀的后缀与模式串的最长相等前后缀的前缀对齐,如下图:
根据前面分析最长相等前后缀的思想,不难发现,这里的最长相等前后缀是”ab”,长度为2.也就意味着,文本串指针i不需要重新回溯到起始位置,模式串指针j也仅仅需要回到下标为2的位置,然后比较s[i]和t[j]即可
所以这里可以看出next数组的对应的值有两个意思,一个就是最长相等前后缀的长度,二是模式串指针j回溯位置的下标.
复杂度分析
根据上面的分析,我们的文本串指针i没有进行回溯,所以这里遍历文本串的时间复杂度为O(n),求next数组时的时间复杂度为O(m),所以在最坏的情况时间复杂度为O(N + M),相对于O(N * M)在时间复杂度上确实上升了不上,但是与此同时,空间复杂度相对于暴力求解,也不在时O(1),因为在求next数组的时候开辟了空间,所以也可以将KMP算法时空间换取时间.
代码实现
public static int KMP(String str,String sub){
int lenStr = str.length();int lenSub = sub.length();
int[] next = new int[lenSub];
//得到next数组
getNext(sub,next);
int i = 0;//遍历主串
int j = 0;//遍历字串
while(i < lenStr && j < lenSub){
if(j == -1 || str.charAt(i) == sub.charAt(j)){
i++;
j++;
}else{
j = next[j];
}
}
if(j >= lenSub){
return i - j;
}
return -1;
}
//得到next数组
public static void getNext(String sub,int[] next){
next[0] = -1;next[1] = 0;
int i = 2;
int k = 0;//前一项的k,记录前面的匹配情况
//遍历模式串
for(; i < sub.length(); i++){
//p[i - 1] == p[k]
if(k == -1 || sub.charAt(i - 1) == sub.charAt(k)){
next[i] = k + 1;
k++;
i++;
}else{
//k回退,去找t.charAt(i -1) == t.charAt[k];
k = next[k];
}
}
}
Original: https://blog.csdn.net/m0_64332179/article/details/127709070
Author: 诚挚的乔治
Title: KMP算法(详解加图解)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/705159/
转载文章受原作者版权保护。转载请注明原作者出处！