深度分析kmp算法，从原理到实现（看了必会，简单直观）

kmp算法，常用于匹配一个字符串是否是另一个字符串的子串，不同于暴力搜索kmp算法的时间复杂度为O(m+n),网上好多对于该算法的讲解代码，但发现有木有，几乎所有的代码全是一模一样，根本没几个是自己写的，给的都是书上标准优化后的代码，直接抄下来，理解困难，原理讲解不清，含糊其词，因此本人自写一遍关于kmp算法的博客，并讲解该kmp算法的原理，以及为什么需要next数组，并证明每次最优移动次数就是next[j]的值，最后依据讲解的原理和思路给出自己的Kmp算法的具体实现，请尊重个人劳动成果，转载请注明出处。

首先请明白next数组是什么，术语讲就是字符串的前缀和后缀的最长公共长度，比如ABCEFGHRHHABC则最长公共长度就是ABC,使用术语可能会妨碍大家理解，这里我使用图形象描述。如图所示字符串ABCEFGHRHHABC的最长公共前缀是多少呢？很简答，你只需要讲该字符串数组右移，舍得末尾（ABC）能跟开头（ABC）重合的最大长度就是前缀和子缀的最大公共长度（描述起来很麻烦，画图好理解，下定义要描述起来还是麻烦啊）

明白了这个之后，现在我们来证明在匹配失败后最优匹配位置为next[j]的值，怎么证明呢？很简单的证明方法，反正法！！,假设我们移动距离不是next[j]的值，使得移动后也匹配结果，具体看下图分析，我们用X变量代表以匹配的字符变量可以代表任意字符，Y变量代表未匹配的字符，也可以表示任意字符，看下图证明：

深度分析kmp算法，从原理到实现（看了必会，简单直观）

接下来就是next数组的求法呢？这个可以用动态规划做,假设k=next[t-1],我们怎么求next[t]呢，

分两种情况，若p[t]==p[k],是不是直接到加到后面，就行了，符合next的定义，因此next[t]=k+1;

那如果p[t] !=p[k]呢？怎么求，首先如果p[t]!=p[k]说明不能直接加，那怎样才能加入？,才能符合next[t]的定义呢？

根本就是要找到，j前面有几个数，可以加入，很间单啊，看我下面的图分析，包你搞懂。

深度分析kmp算法，从原理到实现（看了必会，简单直观）

//具体算法如下

public static int[] getMyNext(String ps) {
    char[] p = ps.toCharArray();
    int[] next = new int[p.length];
    next[0] = 0; //初始化第0位为0
    int k;


    for (int t = 1; t < p.length; t++) {  
        k = next[t - 1]; //获取前一位的next
        //  System.out.println(p[k]);
        if (p[t] == p[k]) {
            next[t] = k + 1;
        } else { //不相等则需要递归,这里使用while循环使用
            while (true) {
                int temp = next[k];
                if (p[t] == p[temp]) {
                    next[t] = temp + 1;
                    break;
                }
                if (temp <= 0) {
                    next[t] = 0;
                    break;
                }

            }


        }
    }
//数组整体右移一位，为什么要右移？因为在kmp算法中我们在加入第j个字符的时候用的是第j-1的next数组，所以求玩后整体右移一位，
    moveToRight(next, 1);
   next[0]=-1;//并且我们将0位置为-1，主要是为了标识，匹配到0的情况
    return next;
}

public static void moveToRight(int[] array, int index) {

    System.arraycopy(array, 0, array, index, array.length - 1);
    System.out.println(array);
}

//既然有了next数组kmp算法也不再话下了

/**
 * 我写的kmp算法
 *
 * @param ts
 * @param ps
 * @return
 */
public static int MyKMP(String ts, String ps) {

    char[] t = ts.toCharArray();

    char[] p = ps.toCharArray();

    int i = 0; // 主串的位置

    int j = 0; // 模式串的位置

    int[] next = getMyNext(ps);


    while (i < t.length && j < p.length) {

        if (t[i] == p[j]) { //

            i++;
            j++;


        } else {

            // i不需要回溯了

            // i = i - j + 1;

            j = next[j]; // j回到指定位置
            if (j == 0) { //j==0 了 只能i右移重新从0开始匹配了
                i++;
            }

        }

    }

    if (j == p.length) {

        return i - j;

    } else {

        return -1;

    }
}

深度分析kmp算法，从原理到实现（看了必会，简单直观）

相关推荐