KMP

这是我第三次再次尝试学习KMP算法，以前总觉得是一个拦路虎，面对比我整个人还长的文章长度直接劝退，当再次遇到KMP后，痛定思痛下定决心来学习KMP算法，现在回头来看，只要静下心来对于聪明的你来说，一定不是难题
按照惯例，我们先来看一下暴力匹配是如何工作的

如下图所示我们利用双指针，i指向模板链的头部，j指向目标链的头部，开始逐个遍历是否相等，当不相等时，我们会令i回溯到i-j+1即模板链的下一个位置，j回溯到目标链的开头，重新开始匹配

当完全匹配时返回目标链在模板链中的位置

public int bfSearch(String s1,String s2){
    int l1 = s1.length;
    int l2 = s2.length;
    int i = 0;
    int j = 0;
    while(i<l1&&j<l2){
        if(s1.charAt(i)==s2.charAt(j)){
            i++;
            j++;
        }else{
            i = i-j+1;
            j = 0;
        }
    }
    if(j == l2){
        return i-j;
    }
    return -1;
}

在上述的暴力算法中，当目标链和模板链失配时，i会回溯到下一个位置再重新匹配，时间效率非常底下，那我们有没有办法不让i去回溯，只令指针j去移动目标链，这就是KMP算法的精髓所在，在KMP算法中我们利用部分匹配表，next数组来确定下一次j移动的位置
这也正是KMP算法的核心，部分匹配表
下面我们来解释一下什么是部分匹配表，例如字符串”abababca”的匹配表如下

例如:
index等于3对应的value值为2，表示以index等于3之前的字符串“abab”最长的公共前缀和后缀的长度
abab的前缀有a，ab，aba（不包括自身），后缀有b，ab，bab，最长公共部分ab长度为2，所以index=3位置对应的value为2，其他部分同理
了解了什么是部分匹配表，那么如何用部分比配表来加速匹配呢

如图所示，当失配时，我们发现只有最后一位是失配的，如果暴力解将i回溯会浪费大量的时间，此处我们利用next数组来是i的指针不发生回溯，只移动j指针，下面我们来分析利用next数组下一次将会移动到什么位置

如果指针能移动到_和D的对比处说明D之前的字符是匹配的，所以括号括起来的位置是相等的，又因为在目标链中，AB恰巧有一个相同的前缀AB，那么说明目标链的前缀和模板链的AB是相等的

即斜体下划线处不用再比较了，所以直接将目标链移动到如下位置

所以我们将这个过程通解化，即主字符串中i指针之前的 PMT[j −1] 位就一定与模式字符串的第 0 位至第 PMT[j−1] 位是相同的，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可
为了利于程序的编写，我们将PMT数组做一些优化
我们发现，当字符失配时，影响j指针移动的是next[j-1],所以我们将next数组整体后移一位，并将next[0]默认值设为-1，为什么设为-1呢？

如图所示我们再首位就发现失配了，按照规则我们无法移动j指针，此时我们只能移动i指针去继续匹配，当我们执行i++，j++代码后，i后移，j不变，实现移动i指针

所以KMP的代码就呼之欲出了，此处我们假设next数组已知，下文中我们将解释如何求解

public int KMP(String s1,String s2) {
		int l1 = s1.length();
		int l2 = s2.length();
		int i = 0;
		int j = 0;
		int [] next = new int[l2];
		while(i<l1&&j<l2) {
			if(j==-1||s1.charAt(i)==s2.charAt(j)) {
				i++;
				j++;
			}else {
				j = next[j];
			}
		}
		if(j==l2)
			return i-j;
		return -1;
	}

那么next数组应该怎么求呢？
我们使用错位法来求解，接下来我们将以字符串“abababca”来讲解如何求next数组

我们错开后可以看作i瞄准的是字符串的后缀（因为后缀不包括自身），同理j瞄准的就是前缀，前后缀的公共部分就是next的值，这个过程也可以看作是KMP的求解过程，其中我们要注意因为我们将next数组后移了一位，所以next[2]看的是i=1处的最长公共字串

public static void getNext(int[] next,String s) {
        //这个求解过程也可以看作是KMP搜索，自身的前后缀的搜索
		int i = 0;
		int j = -1;
		next[0] = -1;
		while(i<s.length()-1) {
		    //在第一轮中，j==-1，所以i++，j++后i=1，j=0，实现错位比较
			if(j==-1||s.charAt(i)==s.charAt(j)) {
				i++;
				j++;
				next[i] = j;
			}else {
				j = next[j];
			}
		}
	}

至此，KMP算法结束！！！！！！！！！！！！