KMP算法

KMP算法主要在于讨论字符串的匹配问题，在刷题LeetCode中遇到过几次，我觉得这个还是应该总结一下。
KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法.
KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

单纯讲理论可能就会假大空，由例子来引入：
有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一个子串 str2="ABCDABD"
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

解决这个问题也很简单，暴力匹配。但是这样很浪费，这个不再多提。就是如果第一个匹配成功，继续匹配下一个，如果下一个不成功，重新匹配，这样存在大量的回溯。浪费了大量的时间。

在这里，ABCDAB中比较过，不匹配，但是如果是暴力匹配算法中仍要和BCDAB比较，可以但是没必要。这里kmp算法是用来了一个比较巧妙的方法来不进行比较，str1中A后面三个字符都是已经比较过的，因为子串ABCD我们知道都不相同，所以没必要比较。那么怎么知道子串不相同呢？
kmp有一个部分匹配表
搜索词（部分匹配值） A （0） B（0） C（0） D（0） A（1） B（2） D（0）
这个有点复杂，为了防止迷惑，我把展开来写一遍
即A （0） AB（0） ABC（0） ABCD（0） ABCDA（1） ABCDAB（2） ABCDABD（0）
关于这个部分匹配表我觉得是kmp算法的精华。
应该马上解释，但是夹在这感觉会断思路，可以接着看思路，再来看这个部分匹配表原理
先引入概念，前缀和后缀是什么
比如字符串“bread”的前缀是什么？前缀是b，br，bre，brea。后缀是read，ead，ad，d
这个很好理解。那么和这个表有什么关系呢？部分匹配值就是“前缀”和“后缀”的最长的共有元素的长度。以“ABCDABD”为例。就是题中的数据

• A的前缀和后缀均为空集，共有元素的长度为0
• AB的前缀为A，后缀为B，共有元素的长度为0
• ABC的前缀为A,AB，后缀为BC,C共有长度为0
• ABCD的前缀为A,AB.ABC.后缀为BCD,CD,D,共有长度为0
• ABCDA的前缀为A,AB,ABC,ADCD,后缀为BCD,CD,DA,A,共有长度为1
• ABCDAB的前缀为A,AB,ABC,ADCD，ABCDA,后缀为BCDAB,CDAB,DAB,AB,B 共有长度为2
• ABCDABD的前缀为A,AB,ABC,ADCD,ABCDA,ABCDAB后缀为BCDABD,CDABD,DABD,ABD,BD,D.共有长度为0
  部分匹配的实质是：有时候，字符串头部和尾部会有重复，比如：“ABCDAB”之中有两个AB,那么他的部分匹配值就是2（AB的长度）。搜索词移动的时候，第一个AB向后移动4位（字符串长度-部分匹配值），就可以来到第二个AB的位置

已知空格与D不匹配时，前面六个字符“ABCDAB”是匹配的，查表可知，最后一个匹配字符B对应的“部分匹配值”为2，因此按照下面的公式算出向后移动的位数：
移动位数=已匹配的字符数 - 对应的部分匹配值
因为6-2等于4，所以将搜索词向后移动4位

因为空格与C不匹配，搜索词还有继续往后移。这是，已匹配的字符数为2（“AB”），对应的匹配值为0。所以，移动位数=2-0，结果为2，于是将搜索词向后移2位

因为空格与A不匹配，继续后移一位

逐位比较，知道发现C与D比匹配。于是，移动位数=6-2，继续将搜索词向后移动4位。

逐位比较，知道搜索词的最后一位，发现完全匹配，于是搜索完成，如果还要继续搜索（即找出全部匹配），移动位数=7-0，再将搜索词向后移动7位，这里就不再重复了

KMP算法的思想就介绍完了，精华就是“部分匹配表”，这个表的作用也很简单，就是减少重复不必要的操作，不像暴力匹配一样。不用一位位移动，不过如果是AAA,这种还是需要一步步移动的。
接下来查看代码如何实现
其实有了思路，代码就基本没什么问题了

public class KMPAlgorithm {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        //String str2 = "BBC";
        
        int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
        System.out.println("next=" + Arrays.toString(next));
        
        int index = kmpSearch(str1, str2, next);
        System.out.println("index=" + index); // 15了
        
        
    }
    
    //写出我们的kmp搜索算法
    /**
     * 
     * @param str1 源字符串
     * @param str2 子串
     * @param next 部分匹配表, 是子串对应的部分匹配表
     * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
        
        //遍历 
        for(int i = 0, j = 0; i < str1.length(); i++) {
            
            //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
            //KMP算法核心点, 可以验证...
            while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j-1]; 
            }
            
            if(str1.charAt(i) == str2.charAt(j)) {
                j++;
            }           
            if(j == str2.length()) {//找到了 // j = 3 i 
                return i - j + 1;
            }
        }
        return  -1;
    }

    //获取到一个字符串(子串) 的部分匹配值表
    public static  int[] kmpNext(String dest) {
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
        for(int i = 1, j = 0; i < dest.length(); i++) {
            //当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
            //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
            //这时kmp算法的核心点
            while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j-1];
            }
            
            //当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

关于代码中的while可以参考这篇文章
KMP的next数组求法详解:https://blog.csdn.net/to_be_better/article/details/49086075
例子说话
A B A B A B A C
0 1 2 3 4 5 6 7
next[6] = 4
即前缀为t[0]~t[4] 后缀为t[2]~t[6]
next[5] = 4
next[4] = 3
即前缀为t[0]~t[2] 后缀为t[2]~t[4]
我们发现
next[4]的前缀一定是next[6]的前缀
next[4]的后缀也一定是next[6]的后缀
(这是while循环的原理，可以试着举个例子验证一下)

现在我们要求next[7]，将t[7]与t[5] ( t[next[6]] )比较，发现不相等
那么可以将t[7]与t[3] (t[ next[next[6]-1] ])比较，如果相等，则next[7] = next[4] +1 ;
不相等就重复此过程，直到t[7]与t[0]比较.

上框内过程其实就是代码中，while循环里的内容
————————————————————————————————————————————
这个我在想怎么更好的讲述，接着上面说next[7],为什么要和比较t[next[6]]。因为如果相等，next[6]=x就是已知的最长子串长度。那么表示他的前缀也是x，这个确实不太好说清楚，因为最长子串是相同的所以他的前缀绝对也相同，后缀也想同。但是next数组有0开始，所以要加1