KMP算法(思想真的不复杂)

在了解KMP之前，我们需要了解两个概念，字符串的前缀，和字符串的后缀

字符串的前缀，我举个例子你们就懂了,一个字符串abcde,它包含的前缀有，{a, ab, abc, abcd}

字符串的后缀,{bcde, cde, de, e}

知道这两个概念后，我们就可以来聊kmp的思想了，现在假如我们需要知道一个字符串（这个字符串我们称为被匹配字符串）中是否包含另一个字符串（这个字符串我们称为被目标字符串），我们最容易想到的自然就是遍历匹配字符串中每一个字符为开头，然后逐一向下匹配。这样自然是可以也很容易想到，但是我们能不能投个懒，比如我们目标字符串根匹配字符串匹配到了4个字母，abab，然后下一个字母匹配失败了，按我们之前的想法，我们肯定是从目标字符串的b开始匹配了。这时候我们仔细观察下这个匹配成功的字符串，你会发现，前面有一个ab后面有一个ab，这时候我们的匹配字符串根本不用从头开始匹配了，直接跳到ab开始，然后接着匹配下一个。

我们注意i和j的位置，上面一个就是匹配字符串，下面是目标字符串，按我们之前的暴力破解，如果i和j这时候没有匹配成功，i是要到b的位置，j是要从头开始的，我们观察结构可以发现根本不用这样，匹配到的有重复的子结构，我们i根本不用动，j的位置移到第二个ab的a处重新匹配就好了

根据上面讲的，如果我们把目标字符串，从头开始依次增加的子串建立一个前缀和后缀的最大匹配表，那么我们每次匹配成功的字符串，我们就可以知道它的前缀和后缀匹配的最大长度。依照图片上，我们i就可以不用动了，j移到对应的最大长度的下一个位置就可以接着匹配了。最关键的就是如何建立起这个最大匹配表，下面的代码就是如何建立最大匹配表（这个表我喜欢这么叫，它原来是叫部分字符匹配表，PMT）。

public static int[] getMatchTable(string str) {
	//用来存放最大的前后缀匹配长度，比如上面的abab它的最大匹配长度是2，它的长度是4，所以索引3处是2，后面依次类推
	int [] matchTable = new int(str.length());
	for(int i = 0, int j = 1; j < matchTable.length; j++) {
		//这是建立这个表最关键的地方，如果之前匹配成功了，这次没有匹配成功
		while(i > 0 && str.charAt(i) != str.charAt(j)) {
			//这里我们其实也是字符串匹配，我们可以使用前面的部分字符匹配表
			i = matchTable[i - 1];
		}
		//成功把前缀对应索引加一，索引的位置也就是匹配的数量
		if(str.charAt(i) == str.charAt(j)) {
			i++;
		}
		//把对应字符位置的最大匹配数量设置进去
		match[j] = i;
	}
	return match;
}

部分字符匹配表一出来，按照我们上面的思路，两个字符串匹配就可以省去很大的功夫了

//str为被匹配字符串
//target为目标字符串
//找了返回匹配到的开始位置，没有匹配到返回-1
private static int match(int[] matchTable, String str, String target) {
        //被匹配串索引
        int i = 0;
        //目标字符串索引
        int j = 0;
        for (; i < str.length(); i++) {
        	//没有匹配到，如果之前有匹配到，我们就需要在表里去找最大的前后缀匹配长度了
            while (j > 0 && target.charAt(j) == str.charAt(i)) {
                j = matchTable[j - 1];
            }
            
            //匹配到了接着匹配下一个
            if (target.charAt(j) == str.charAt(i)) {
                j++;
            }
            
            if (j == target.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

到此KMP算法计算结束了，还没理解的话，可以照着代码dug琢磨几遍，代码纯手打，也是为了巩固自己的记忆，如有错误遗漏之处，也请指出。