侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

KMP算法---字符串匹对

林贤钦
2020-06-27 / 0 评论 / 9 点赞 / 866 阅读 / 0 字
温馨提示:
本文最后更新于 2020-06-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

KMP算法---字符串匹对

  • KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。

  • KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

图文展示kmp算法

举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD"?

接着比较字符串和搜索词的下一个字符,还是相同。直到D匹配到了空格

有几个问题?kmp是如何得出4位的,部分匹配表又是什么?是怎么算出来的?

得到了部分匹配表,那么如何利用这个部分匹配表来算出要移动4位?

规则我们知道了,接下来继续移动

到此,已经完成了,找到了。算法规则知道了,接下来就是代码怎么实现了,没有代码实现,都是扯犊子

代码实现kmp算法

第一步:获取部分匹配表next数组

根据上文的kmp算法,我们肯定得先算出字串的部分匹配表next数组

public static int[] kmpNext(String dest){
    //创建一个next数组,保存部分匹配值
    int[] next = new int[dest.length()];
    next[0]=0;//如果字符串长度为1,部分匹配值默认为0
    for (int i = 1,j=0; i <dest.length() ; i++) {
         //这是kmp算法的核心点
        //当j>0且dest.CharAt(i) != dest.CharAt(i) ,我们需要从next[j-1] 获取新的j
        while (j>0 && dest.charAt(i)!=dest.charAt(j)){
            //直到我们发现有dest.charAt(i) = dest.charAt(j)或者j=0成立才退出
            j=next[j-1];
        }
        //当dest.charAt(i) == dest.charAt(j)满足时,部分匹配值就是+1
        if (dest.charAt(i)==dest.charAt(j)){
            j++;
        }
        next[i]=j;
    }
    return next;
}

说明:以上面的ABCDABD为例子

  • A:字符串的第一个,默认位0,所以还是next[0]=0

  • B:字符串的第二个,进入for循环,j=0,第一个条件不满足,"B" != "A",if条件也不满足,所以next[1]=0

  • C: 字符串的第三个,j=0,第一个条件不满足,"C" != "A",if条件也不满足,所以next[2]=0

  • D: 字符串的第四个,j=0,第一个条件不满足,"D" != "A",if条件也不满足,所以next[3]=0

  • A: 字符串的第五个,j=0,第一个条件不满足,"A" != "A",if条件条件满足,所以j++,next[4]=j=1

  • B: 字符串的第六个,j=1,while循环的第一个添加满足,但是while循环的第二个条件dest.charAt(i)!=dest.charAt(j)不满足,所以跳过来到了if条件,if条件满足所以j++,next[5]=j=2

  • D: 字符串的第七个,j=2,while循环的第一个添加满足,而且第二个条件也满足。进入while循环,j=next[j-1]=next[1]=0; 不满足while条件,退出while循环,"D"和"A"也不相等,不满足条件,所以next[6]=0

最后得到部分匹配表[0,0,0,0,1,2,0]

第二步:根据部分匹配表查找字符串

/**
 *  kmp搜索算法
 * @param str1  源字符串
 * @param str2  子串
 * @param next  部分匹配表, 是子串对应的部分匹配表
 * @return   如果是-1就是没有匹配到,否则返回第一个匹配的位置
 */
public static int kmpSearch(String str1,String str2,int[]next){
    //遍历长串
    for (int i = 0,j=0; i < str1.length(); i++) {
        //j>0只有已经开始相等的时候才满足,而如果满足第二个条件就会回退比对
        while (j>0&&str1.charAt(i)!= str2.charAt(j)){
            j=next[j-1];
        }
        //如果发现相等,j++
        if (str1.charAt(i)==str2.charAt(j)){
            j++;
        }
        //找到了
        if (j==str2.length()){
            //返回数组下标,i为最后一个下标,j为数组长度
            return i-j+1;
        }
    }
    return  -1;
}

简要分析一下代码如何展示上图的,当我们"D"遇到了空格,此时i的下标到了空格这,而j=6,进入while循环

j=next[j-1]=next[5],从上面的部分匹配表,可得next[5]等于2,也就是j=2,所以匹配条件,j>0,而且,空格和str2.charAt(2)=C不相等,就直接匹对空格和c了,在前面ab已经匹对过,kmp算法跳过了这个,只能说牛逼。然后再到了j=next[2-1]=next[1]=0;跳出循环。

9

评论区