欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KMP算法(一):正常逻辑求解(next数组)

程序员文章站 2024-02-16 09:27:10
...

一、KMP是什么

KMP算法是为了解决字符串匹配效率而提出的,提出者为D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位大牛,故称为“KMP”算法。

二、暴力求解算法

1、题目:假设一个父字符串是father,子字符串是son,在father中查找son,如果存在则返回son在father中的起始索引,不存在则返回-1。

2、最简单的解法就是使用循环,挨个字符比较,如果匹配就继续,如果不匹配则father和son同时回退前进的长度,重新计算。java代码如下:

/**
 * 暴力算法
 */
private static int violentMatch(String father, String son) {
    int fatherLength = father.length();
    int sonLength = son.length();
    //i记录在father中的位置
    int i = 0;
    //i记录在son中的位置
    int j = 0;
    while (i < fatherLength && j < sonLength) {
        if (father.charAt(i) == son.charAt(j)) {
            //如果父子当前的字符匹配成功,则同时前进以为,匹配下一个
            i++;
            j++;
        } else {
            //匹配不成功,则回退前进的长度
            //因为j每次都是从son的第一位开始,也就是0,所以i-j就是回到这一轮开始的位置,再+1则表示下一个字符(当前轮开始的字符匹配不成功)
            i = i - j + 1;
            j = 0;
        }
    }
    //如果跳出循环之后,j等于子串的长度(循环进行的条件之一是j < sonLength,匹配成功后j++ 就等于sonLength了)
    if (j == sonLength) {
        //此时i所在位置是son在father中的最后一个字符的后一位,所以起始位置要减去j,就是son在father中的第一位
        return i - j;
    }
    //没有匹配成功就返回-1
    return -1;
}

3、暴力求解的问题在哪呢?

在于i跟j同步回溯,会造成很多不必要的对比次数。比如father=“abcdef", son="abx",

 

KMP算法(一):正常逻辑求解(next数组)

第一次开始比较的时候,到father的 c 位置就发现不匹配,结束回退再次循环,但是其实人工来看完全不需要从 b 和 c 再开始了,因为第一次比较已经知道了father 的 b 和 c 与son的 a 是不一样的,更何况son的 x 在father的前三位压根就没有,完全可以从 d 开始。

三、KMP算法之正常逻辑求解(next数组)

(一)、基本算法流程

假设father匹配到 i 位置,son匹配到 j 位置。

-如果j = -1, 或者当前匹配字符成功(father.charAt(i) == son.charAt(j)), 都令i++, j++, 继续匹配下一个字符。

-如果j != -1, 且当前字符匹配失败,则令 i 不变,j=next[j], 意思是当前字符匹配失败,son相对于father向右移动了j - next[j] 位。就比如father="abcabcd", son="abcd", next[]=[-1, 0, 0, 0 ],匹配到father.charAt(3)时,father的字符是a,son的字符是d,i = 3, j = 3,这个时候如果暴力解法,则i = 1, j = 0,而KMP算法则是将 i 不变, j = next[j] = 0,意味着将son右移 j - next[j] = 3。

KMP算法(一):正常逻辑求解(next数组)

KMP算法(一):正常逻辑求解(next数组)

KMP算法(一):正常逻辑求解(next数组)

用代码表示如下:

/**
 * KMP算法
 */
private static int match(String father, String son) {
    //通过子串计算next数组
    int[] next = getNext(son);
    int i = 0, j = 0;
    //一直循环到i等于father长度,或者j等于son长度
    while (i <= father.length() - 1 && j <= son.length() - 1) {
        //-1表示son需要从头匹配,||后面的语句表示字符相等,后移一位
        if (j == -1 || father.charAt(i) == son.charAt(j)) {
            i++;
            j++;
        } else {
            //字符不匹配,i不变,j回退到next[j]进行比较,或者说son右移j - next[j]位
            j = next[j];
        }
        if (j > son.length() - 1) {
            //匹配成功
            return i - son.length();
        }
    }
    return -1;
}

(二)、next数组计算原理

1、寻找前缀后缀最长公共元素长度(这里看到一篇博客说的比较详细,直接引用了,链接:https://blog.csdn.net/v_july_v/article/details/7041827

KMP算法(一):正常逻辑求解(next数组)

2、然后自己再解释一下,为什么“next 数组考虑的是除当前字符外的最长相同前缀后缀”,见下图

KMP算法(一):正常逻辑求解(next数组)

(三)、next计算代码

private static int[] getNext(String son) {
    //因为是自己跟自己比较,所以起始状态j 比 i小1。只是-1不存在,所以下方next[0]设置成了-1
    //配合判断条件j == -1,造成的结果就是i和j一起进一位。如果之前的步骤两个字符相同,那就是都进一位继续比较。
    // 如果不同,j置为-1然后自增变成0,i进一位,就开始了多一位字符的运算。
    int i = 0, j = -1;
    int[] next = new int[son.length()];
    next[0] = -1;
    while (i < son.length() - 1) {
        //以son = "ababd"为例
        //起始的时候j=-1,令i = 1, j = 0,所以next[1] = 0,而且不管是什么字符串,都会是0,
        // 因为next 数组考虑的是除当前字符外的最长相同前缀后缀。所以i = 1的时候,next数组考虑的只有son[0]这一个字符
        //而当i=1了,j=0,son[1]和son[0]不相等,则j就要回退,回退到next[j],此处原理与match时候的j = next[j]的原理很相似。
        if (j == -1 || son.charAt(i) == son.charAt(j)) {
            i++;
            j++;
            next[i] = j;
        } else {
            //son[i]和son[j]不相等,则j就要回退,回退到next[j],此处原理与match时候的j = next[j]的原理很相似。
            // 回退到j = 0时就相当于此时的字符与son[0]开始比较,不相等则j=next[0]=-1,紧接着就各自加1,开始多一位字符长度的比较
            j = next[j];
        }
    }
    //感兴趣的可以再用son="abcdabcdcab"等进行debug观察计算和回溯过程
    return next;
}

 

四、自述

这周开始在看《大话数据结构》,这算是书中目前为止遇到的第一个真正意义上的算法吧,就把我难住了,大概看了一天半吧才有了大概的轮廓,但是感觉细节还不是很清晰,就想着通过写博客的方式来讲述,加深理解。如果大家觉得哪里讲的有问题或者不够透测,可以留言讨论。

边写博客边加深理解,也算是耗费了一些时间,一周就这样过去了(阶段性空闲,程序员都懂的,可别说我工作不饱和好吧……^_^)。本来想再把知乎上看到的另一种解法--确定有限状态机 也写在这里的,但是时间来不及了,毕竟还是要工作的。就准备等周末来写好了。然后下周再研究KMP算法的改进算法--nextval数组方式,以及Sunday算法。

相关标签: 算法