KMP算法（一）：正常逻辑求解（next数组）

一、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"，

 

第一次开始比较的时候，到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算法
 */
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）

2、然后自己再解释一下，为什么“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算法。