简介
- KMP算法是一种字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
算法分析
假设主串T用i指针遍历，而模式串P用j指针遍历。
和暴力法的区别
情况1：如果P[0]就不匹配了，那么i指针指向下一位，而j指针不变，这在暴力和KMP都一样，不用多说。
情况2：如果P的前几个字符匹配的话，情况就有所不同。在暴力算法中，如果T[i] != P[j]，i需要回溯到i-j+1的位置，而j变为0。而在KMP算法中，则是利用已经部分匹配的有效信息，i指针不回溯，通过修改j指针，让模式串移动到有效的位置。
重点和难点
KMP算法的重点和难点是如何求j指针在不匹配时的下一位置，这里将该位置设为k。这里引入一个next数组，next[j]表示P[j]匹配失败后，j指针应指向的位置，即next[j] = k。
分析
为什么要求k值呢？k值是怎么来的？
当T[i] != P[j]时（j>0），已知P[0 ... j-1] == T[i-j ... i-1]，若P[0 ... k-1] == P[j-k ... j-1]，
则P[0 ... k-1] == T[i-k ... i-1]，此时只需将j指针移动到k，而i指针不需要移动，即可继续进行比较。
所以此时问题转化为求令P[0 ... k-1] == P[j-k ... j-1]的k的最大值，即P的前j个字符组成的子串的最长相同前缀后缀的长度（k）。
next数组如何求
- 特殊情况：next[0] = -1（此时j不用动，i向后移一位）；next[1] = 0（此时i不用动，j回溯到第0位）；如果前j个字符都相同，则next[j] = j-1。
- 其他情况：next[j] = k，其中k为P[0 ... j-1]中最长相同前缀后缀的长度
实战：实现strStr()（LeetCode第28题）
题目描述
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
示例
示例1：
输入: haystack = "hello", needle = "ll"
输出: 2
示例2：
输入: haystack = "aaaaa", needle = "bba"
输出: -1
代码
/**
* 利用KMP算法求解
*
* 需要进行匹配的字符（即haystack字符串），称为主串，简称T
* 模式（Pattern）字符串（即needle字符串），简称P
*
*/
private static int strStr_KMP(String haystack, String needle) {
if (needle.equals("")) {
return 0;
}
char [] T = haystack.toCharArray();
char [] P = needle.toCharArray();
int [] next = getNext(needle);
int i = 0;
int j = 0;
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || T[i] == P[j]) { //当j == -1时，i向后移动一位，j也要归零
i++;
j++;
} else { //T[i] != P[j]时，i指针不用动，j指针移动到相应的位置
j = next[j];
}
}
if (j == needle.length()) { //说明在主串T中找到了模式串P
return i - j;
} else {
return -1;
}
}
/**
* 根据模式串P获取next数组，next[j]表示P[j]匹配失败后，j指针应指向的位置。
*
* @param P 模式串
* @return next数组
*/
private static int [] getNext(String P) {
int [] next = new int[P.length()];
next[0] = -1;
int k = -1; //存储当前next[j]对应的k值
int j = 0;
while (j < P.length()-1) {
if (k == -1 || P.charAt(k) == P.charAt(j)) { //隐含条件P[0 ... k-1] == P[j-k ... j-1]
//当k == -1时，next[j++] = 0，例如next[1] = 0，或者前j字符没有相同前缀后缀时也为0。
//当P[k] == P[j]时，由于P[0 ... k-1] == P[j-k ... j-1]，则此时P[0 ... k] == P[j-k ... j]，所以此时next[j+1] = k+1
next[++j] = ++k;
} else {
//当P[k] != P[j]时，next[j+1]必定小于k，此时可以缩小k的值（最小小到-1）
k = next[k];
}
}
return next;
}
