KMP算法详解

• 同学们，如果我们要判断下图ababababc中是否有ababc和所在的位置，正常是不是需要按下标一个个比，然后不同的时候i再从上次比较的下一个i1开始，步骤如下：
  

  

• 细心的同学会发现其实还是有优化空间的，分析一下，我们在下面图1这个时候下一步可不可以让i不回退到i1的下一个位置而是继续往下走呢，其实是可以的，只是我们需要满足条件：下面一组字符串不再拿"ababc"去从i位置比较，而是拿"abc"继续从i位置比较，因为前面的"ab"是相同的，没必要再比较了。那么问题来了，我们应该怎么样知道下面ababc中（也就是下标j）要从哪个地方开始取值再和上面的i开始比较呢。

• 上面的分析所以就诞生了KMP算法，让原本的时间复杂度o(m*n)变成了o(m+n)

  
  图1

• 要找出j下次该出现的位置，我们可以按如下规则 从ababc中找出对应的规律放入数组next中
  第一步：先创建数组next，长度和要匹配的字符一样（5），然后把下标0的位置置为0，然后我们再创建2个变量i和j，i从1开始，j从0开始。后面就遵循下面的顺序挨个跑...
1.next[i] = j;
2.i++;
3.相同：j++; 不同：j = next[j - 1];
  

  

由此我们可以得到数组next为[0,0,1,2,0]，然后我们会发现与ababc对应，next数组里值是0的忽略，看next数组里下标2的值是1，说明当前位置往前面数1个，也就是a在之前ab里有相同的，然后最后一个相同的位置是（值-1）也就是0。我们再看next数组里下标3的值是2，从当前位置往前数2个，也就是ab在之前aba里也有相同的，最后一个值b相同的位置在1位置。是不是很神奇。

• 然后我们把这个next数组套在上面的步骤上，当执行到上面图1的时候，i不变，j = next[j - 1]，j移到下标2位置，然后再拿i(a)和j(a)比较...以此类推，kmp算法的步骤如下：
  

  

• 好了，思路讲完了我们就发车了

    /**
     * KMP算法 str字符 dest要比较的字符
     */
    public int kmp(String str, String dest) {
        //获取next数组
        int[] next = getKmpNext(dest);
        for (int i = 0, j = 0; i < str.length(); i++) {
            //这里用while 如果j替换了位置后发现j的值和i的值还是不对 就会继续往后取值
            while (j > 0 && str.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            //值是相等的 上面i和这里j都++
            if (str.charAt(i) == dest.charAt(j)) {
                j++;
            }
            //找到比较的字符了 返回字符位置
            if (j == dest.length()) {
                return i - j + 1;
            }
        }
        return 0;
    }

    /**
     * 获取字符的next数组
     */
    public int[] getKmpNext(String dest) {
        int[] next = new int[dest.length()];
        //按文章里：把下标0的位置置为0，然后我们再创建2个变量i和j，i从1开始，j从0开始
        next[0] = 0;
        //2.i++;
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //3.相同：j++; 不同：j = next[j - 1];
            //不同 这里用while是为了确保j的取值是正确的 可以看如下情况，现在执行到这里的时候
            //如果不用while j会取为2，其实这个位置d，在前面是不存在的 应该是0，所以用while
            //next[0,0,1,2,0,1,2,3,4,]
            //     a b a b c a b a b d
            //                       i
            //     a b a b c a b a b d
            //             j
            while (j > 0 && dest.charAt(j) != dest.charAt(i)) {
                j = next[j - 1];
            }
            //相同
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            //1.next[i] = j;
            next[i] = j;
        }
        return next;
    }