KMP算法原理 JAVA实现

一、什么是KMP算法

1. 实际上KMP只是发明这个算法的三个人的英文名首字母短称，KMP本身无意义；
2. KMP其实是用来做字符串匹配的一种算法。

二、为什么需要KMP算法

1. 算法背景

1. 有这么两个字符串，目标target字符串acabacaf，需要匹配的source字符串acaf，我们需要找到source在target的索引匹配位置，匹配不到返回-1。
2. 如何解决该问题，最简单的肯定是暴力匹配；

1.1 暴力匹配过程

1. 从target字符串的首字母开始，与source字符串进行匹配
2. 匹配不上，则target字符串右移一位，然后重新与source字符串进行匹配
3. 匹配成功，则返回target字符串匹配成功的索引位置；
4. 代码如下

/**
 * @param haystack target字符串
 * @param needle source字符串
 */
public int strStr(String haystack, String needle) {
    if (needle.length() > haystack.length()) {
        return -1;
    }
    char first = needle.charAt(0);
    int dis = needle.length() - 1;
    char[] chars = haystack.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == first && i + dis < chars.length && haystack.substring(i, i + dis + 1).equals(needle)) {
            return i;
        }
    }
    return -1;
}

1.2 暴力匹配的优劣

1. 优点：非常容易理，代码简单
2. 缺点：耗时，非常耗时，理论上速度为O(n * m)

2. KMP算法的诞生

1. 由于暴力匹配，时间复杂度过高，所以就想办法降低复杂度，有什么办法呢？就是减少字符串匹配次数，不回溯target字符串的索引，而仅仅移动source字符串的索引！

2. 如何优化，我们可以先看暴力匹配法的比对信息
   

3. 从上图可以得到一个信息，以kmp思想优化，从第二行开始是f字母无法匹配，此时target索引已经来到b，那么仅移动source索引，只可能以source的c字符来匹配，因为只有前面的a重复，当c无法匹配成功时，source仅剩0角标处的a字符进行匹配

4. 我们将source和target字符串全部翻倍，再次查看一下暴力匹配
   

5. 从上图可以得到一个信息，以kmp思想优化，从第二行开始是f字母无法匹配，此时target索引已经来到6角标的b字符，那么仅移动source索引，只可能以source的3角标处的c字符来匹配，因为只有前面的aa重复，当c无法匹配成功时，source还能以1角标处的a字符来匹配一次，因为前面的a字符重复，当a无法匹配成功时，source仅剩0角标处的a字符进行匹配。

3. next数组

3.1 kmp算法的关键

1. 从上面kmp的思想可以知道，最关键的就是未匹配时，需要知道source字符串未匹配字符之前的，最长相同的前后缀长度，只要知道该长度，就可以推算出不匹配时，source字符串再次用来对比的字符索引，而source字符串每个字符的最长相同前后缀长度组成的数组即为next数组。
2. 字符串前后缀，前缀就是当前字符串不包含最后一个字符的所有字符的顺序组合的各个字符串，后缀就是当前字符串不包含第一个字符的所有字符的顺序组合的各个字符串，例如source字符串acaf，它的前缀有a,ac,aca，后缀就是c,ca,caf，可以看的出来没有相同的前后缀，即f处的next数组值为0，那么按照该方法，我们分别推算source字符串的next数组过程如下：
   1. next[0]：a字符索引的字符串为a，不存在前后缀，结果为0
   2. next[1]：c字符索引的字符串为ac，前后缀分别为a和c，不存在相同的前后缀，结果为0
   3. next[2]：a字符索引的字符串为aca，前后缀分别为a,ac和ca,a，相同的前后缀只有a，结果为1
   4. next[3]：已经在上面举过例子了，结果为0
3. next数组的含义如上，而且由于索引是从0开始的，字符串加起来的长度刚好是未匹配上的字符，比如next[1]值为1，它对应的索引刚好是c字符，也就是未匹配上的，这个可以用数学公式来证明，当然我对数学公式有点头疼，用经验归纳法也可以得出该结果，你们可以试一下。
4. 如何求解next数组呢，这个也有数学公式可以推导，可以用动态规划去做。
   1. 默认第一个字符next结果为0，第二个字符如果和前一个字符相同，则直接+1，后续如果满足当前字符和前一个字符相同的条件，则不断+1，这个应该理解很简单，多一个字符，前后缀长度相当于都+1，而如果前缀最后一个字符和后缀最后一个字符相同，则结果就是上一个next值+1，所以理论上总结为上一个前缀的后一个字符串与当前字符串相同，则next值为上一个next值+1，可以理解为aaaaaaa，next数组为[0,1,2,3,4,5,6]
   2. 如果当前字符和前一个字符不相同，那么前缀字符串就没法增加了，我们就要在上一个前缀的基础上，判断它后面的字符和当前字符是否相同，如果相同则+1，如果不同，则继续找上上一个前缀，并在这个基础上，继续进行判断，直到前缀长度为0后，不再进行循环。例如aacaac，next数组就是[0,1,0,1,2,3]
   3. 代码如下

public int[] getNextStr(String source) {
	int[] next = new int[source.length()];
	next[0] = 0;
	int k = 0;
	for (int i = 1; i < source.length(); i++) {
	    // 此处的k就代表上一个前缀的后一个字符索引位置，next[k-1]就是求解，因为next值代表相同前后缀的长度，同时也代表了前缀的后一个字符索引位置
		while (k > 0 && source.charAt(i) != source.charAt(k)) {
			k = next[k-1];
		}
		if (source.charAt(i) == source.charAt(k)) {
			k++;
		}
		next[i] = k;
	}
	return next;
}

三、求解KMP

public int getKMP(String haystack, String needle) {
	int[] next = getNextStr(needle);
	int k = 0;
	for (int i = 0; i < haystack.length(); i++) {
		// 与上面next数组的k值同理
		while (k > 0 && haystack.charAt(i) != needle.charAt(k)) {
			k = next[k - 1];
		}
		if (haystack.charAt(i) == needle.charAt(k)) {
			k++;
		}
		if (k == needle.length()) {
			return i - k + 1;
		}
	}
	return -1;
}