纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

Java KMP Java数据结构彻底理解关于KMP算法

飞人01_01   2021-09-14 我要评论
想了解Java数据结构彻底理解关于KMP算法的相关内容吗,飞人01_01在本文为您仔细讲解Java KMP的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,KMP,Java,数据结构,下面大家一起来学习吧。

大家好,前面的有一篇文章讲了子序列和全排列问题,今天我们再来看一个比较有难度的问题。那就是大名鼎鼎的KMP算法。

img

本期文章源码:GitHub源码

简介

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

说的简单的一点,就是一个用于在主串中,查找子串的算法。

暴力解法(BF)

在讲解KMP算法之前,我们得先理解暴力解法,因为KMP算法就是在暴力解法的基础之上,进行了优化,使之匹配速度加快。

人如其名,暴力解法,就是一种很暴力的解决方法。比如:主串“abbabbec”,待查找的子串为“abbec”, 请问主串中是否包含这个子串?

我们肉眼,能够很轻松的看到从第4个字符开始,一直到末尾这一段,就是需要查找的子串。那么编译器是如何进行查找呢?它就只能一个字符一个字符的尝试:

QQ截图20210913152249

上图就是暴力解法的全部过程,通过匹配一个个字符,如果当前字符匹配成功,i和j就同时走一步;如果当前字符匹配不成功,i 就应该回到当前开始的第一个字符的下一个字符:比如图中步骤4和步骤5,就是说的这个意思,当前是从第一个字符a开始匹配的,此时匹配失败了,i就应该回到a字符的下一个字符,j就从0下标开始,继续往下匹配;

当i或者j走到了字符串的末尾,我们就结束循环。然后判断j是不是遍历完了待查找的子串,如果确实是走到了子串的末尾,说明查找成功了,就返回子串在主串的起始位置(i - j, 在上图就是返回3),反之就是:主串的字符都遍历完了,子串的还没遍历完,那就是主串没有这个子串的情况,此时返回-1即可。

//BF算法
//s 为主串
//m 为待查找的子串
public int BF(String s, String m) {
    if(s == null || m == null) {
        return -1;
    }
    
    char[] str1 = s.toCharArray(); //主串
    char[] str2 = m.toCharArray(); //子串
    int i = 0; //指向主串的下标
    int j = 0; //指向子串的下标
    
    //i和j的值,都还没到末尾,循环继续
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //当前字符匹配成功
            i++;
            j++;
        } else { //当前字符匹配不成功
            i = i - j + 1; //回到开头的下一个字符
            j = 0; //子串从头开始
        }
    }
    
    //判断是否遍历完了子串,并返回相应的值
    return j == str2.length? i - j : -1; 
}

时间复杂度:

假设主串的长度为N, 子串的长度为M。最差的情况,就如上图的情况,只有在最后一个字符才查找成功。所以子串要从每一个字符作为起始位置开始匹配,每一个字符作为起始,都会匹配子串的长度M次,也就是说暴力解法的时间复杂度为O(N*M)。

KMP算法

KMP算法和BF算法,在代码上差别不大。在BF的代码基础之上,需要计算一个next数组,在while循环里面再加一个判断语句即可,其他的代码都是不变的。

虽然代码改动不是很大,但是从逻辑思维上,却是一个质的飞越。所以我们先来看一下KMP的核心:next数组。

next数组究竟是什么?我相信很多同学都会有这样一个疑问。

其实next数组,计算的待查找的子串的每个字符(不包括当前字符)前面的所有字符中,前缀字符串和后缀字符串相等的,并且最长的字符个数。比如:

image-20210913160944706

举一个完整的例子吧,比如子串是str2 = “ababab”,计算这个字符串的next数组如下:

首先就是从头开始遍历字符串:(建议拿出笔和纸,一起画一画,更容易理解)

  • j = 0; str2[j] = a

a字符前面没有任何字符,人为规定第一个字符的next值为-1。

  • j = 1; str2[j] = b

b字符前面只有一个字符a,有人就会说,那么next就是1咯? 当然不是,我们还忽略了一个重要条件:计算的当前字符前面的所有字符,进行划分前缀和后缀字符串,但是所谓的前缀和后缀字符串,并不包括了这前面的整体字符串。说的简单一点就是:假设b字符前面的所有字符是“abc”, 前缀字符串是“abc”, 后缀字符串是“abc”,这种情况是不算在内的。用数学公式解释:前缀字符串 = 后缀字符串 = b字符前面所有字符。这种情况不算数。

所以当前这个b字符,前面就只有一个字符,所以人为规定第二个字符的next值为0。

  • j = 2; str2[j] = a

a字符前面有字符串“ab”, 前缀和后缀字符串,排除“ab” = “ab”的情况,就没有能够匹配前缀和后缀的字符串,所以第三个字符的next值为0。

  • j = 3; str2[j] = b

b字符前面的字符串是“aba”,此时排除“aba” = ”aba“的情况, 那就只剩下前缀字符串“a” = 后缀字符串“a”的情况,所以第四个字符的next值为1。

  • j = 4; str2[j] = a

a字符前面的字符串是“abab”,排除“abab” = “abab”的情况后,就只剩下前缀字符串“ab” = 后缀字符串“ab”的情况,所以第五个字符的next值为2。

  • j = 5;str2[j] = b

b字符前面的字符串是“ababa”, 排除“ababa” = “ababa”的情况后,就只剩下前缀字符串“aba” = 后缀字符串“aba”,所以第六个字符的next值为3。

  • j = 6; str2[j] = ‘\0'

遍历结束

所以上面例子的next数组的值,如下图:

image-20210913164309450

那么就有同学会纳闷了,在逻辑层面上,我知道该怎么计算next数组了,但是在代码层面上,似乎并没有什么思路。不急,我们现在就说一下代码怎么实现这个逻辑。

我们以上图的最后一个字符b为例。在求解b字符所对应的next值时,b字符前面的字符,是已经计算好了next值的。所以我们需要借助b字符前面已经计算好的next值,来计算b字符的next值。

image-20210913173022974

image-20210913174250994

所以next数组的计算代码,如下:

public int[] getNextArr(String m) {
    if (m.length() < 2) { //只有一个字符
        return new int[] {-1};
    }
    if (m.length() < 3) { //只有两个字符
        return new int[] {-1, 0};
    }
    
    char[] str = m.toCharArray();
    int[] next = new int[m.length()];
    next[0] = -1;
    next[1] = 0; //人为规定的两个位置的next值
    int cn = 0; //表示往前跳的下标。也就是前缀字符串的下一个字符。初始化就是第一个字符
    int i = 2; //从第三个字符开始判断
    
    while (i < m.length()) {
        if (str[i - 1] == str[cn]) { 
            //当前字符的前一个字符,与cn所对应的字符比较
            next[i++] = ++cn; //等价于:next[i++] = next[i - 1] + 1; cn++; 
        } else if (cn > 0) {
            //说明当前字符没匹配成功,cn要往前跳,找上一组前缀、后缀字符串
            cn = next[cn];
        } else {
            //cn一直往前跳,都没能与当前字符匹配成功,则当前位置next值就是0
            next[i++] = 0;
        }
    }
    
    return next; //返回next数组
}

next数组的计算代码,我们就讲完了,再加把劲,就还剩最后的一点点了。

我们先来将大致的框架写出来:

//KMP算法
// s 为主串
// m 为待查找的子串
public int KMP(String s, String m) {
    if (s == null || m == null || s.length() < 1 || m.length() < 1) {
        return -1;
    }
    
    int[] next = getNextArr(m); //计算子串的next数组
    
    char[] str1 = s.toCharArray();
    char[] str2 = m.toCharArray();
    int i = 0; //指向主串的下标
    int j = 0; //指向子串的下标
    
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //字符相等的情况,i和j同时加1
            i++;
            j++;
        } else if (j == 0) {
            
        } else {
            
        }
    }
    
    return j == str2.length? i - j : -1; //判断子串是否遍历完了
}

现在就还剩下while循环里面,20行~24行的代码,还没填写。

20行~24行的代码,是在上面的if语句没有为真,才会走到20行后面代码。也就是说此时当前的字符已经没有匹配成功了。此时就需要对j或者i进行调整。

那么对于j来说,就分为两个情况:

j != 0时,则说明j还能往前面跳,即就是说j位置前面的字符,还有可能会有前缀、后置字符串。那么j继续往前跳即可。j = next[j]。(找j位置前面的前缀字符串)

j == 0时,则说明j前面已经没有字符了,换个角度说,对于当前i位置的字符,在子串中j已经走到了第一个字符,都还没匹配成功,则说明,当前i位置的字符肯定不会匹配成功的。那么i往后走一个字符的位置,然后再循环就进行判断。

完整的代码:

//KMP算法
// s 为主串
// m 为待查找的子串
public int KMP(String s, String m) {
    if (s == null || m == null || s.length() < 1 || m.length() < 1) {
        return -1;
    }
    
    int[] next = getNextArr(m); //计算子串的next数组
    
    char[] str1 = s.toCharArray();
    char[] str2 = m.toCharArray();
    int i = 0; //指向主串的下标
    int j = 0; //指向子串的下标
    
    while (i < str1.length && j < str2.length) {
        if (str1[i] == str2[j]) { //字符相等的情况,i和j同时加1
            i++;
            j++;
        } else if (j == 0) { //j不能再往前走了,那么i就往后走一个位置
            i++;
        } else { //j还能往前跳,寻找前面的前缀字符串
            j = next[j];
        }
    }
    
    return j == str2.length? i - j : -1; //判断子串是否遍历完了
}

只要理解了next数组是如何进行计算的,那么KMP算法的就理解了一大半了。

后面的整体的代码框架,跟BF算法是差不多的。只需分为i和j两个值的调整,即可!

具体的,大家可以再分别举几个例子,自己手动去走一遍代码,这里就能更好的理解KMP算法的思路。也可以看一下左程云老师所写的《程序员代码面试指南》一书,也有相应的讲解。

好啦,本期更新就到此结束啦,我们下期见!!!

在这里插入图片描述


相关文章

猜您喜欢

  • .Net性能调优-ArrayPool .Net性能调优-ArrayPool详情

    想了解.Net性能调优-ArrayPool详情的相关内容吗,张三~~在本文为您仔细讲解.Net性能调优-ArrayPool的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:.Net性能调优-ArrayPool,.Net性能调优,下面大家一起来学习吧。..
  • Java SpringBoot启动指定profile Java SpringBoot启动指定profile的8种方式详解

    想了解Java SpringBoot启动指定profile的8种方式详解的相关内容吗,Apple_Web在本文为您仔细讲解Java SpringBoot启动指定profile的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,SpringBoot,SpringBootprofile,下面大家一起来学习吧。..

网友评论

Copyright 2020 www.hris-software.net 【幸运软件站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式