一、字符串原理
KMP算法是由它的三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt)的名字来命名的；SMP算法的核心思想跟BM算法很相似，主要不同在于BM算法是模式串由后到前比较顺序，KMP算法是模式串由前往后的比较顺序；
在模式串和主串的匹配过程中，不能匹配的字符叫坏字符，已经匹配的那段字符叫好前缀，我们主要就是要找出好前缀后缀子串跟模式串前缀子串有相同的最长字符段，把模式串移动到相同后缀子串的位置，这样可以一下移动多个位置，并且相同的字符段不用比较了，直接从相同的字符段的下个字符开始比较，具体操作如下图；
我们把好前缀的所有的后缀子串中，最长可匹配前缀子串的那个后缀子串称最长可匹配后缀子串；对应的前缀子串称最长可匹配前缀子串 。我们从上图可以看出，只要找到了最长可匹配前缀子串的位置，我们就可以知道要下一个比较字符的位置在哪里；我们用一个数组next来存储模式串中每个前缀的最长可匹配前缀子串的结尾字符下标。这个数组也被叫做失效函数。
二、失效函数的计算方法
怎么来计算这个next数组，先用画一个图来帮我们理解一下
我们来分析一下，假设一个前缀 0~i ，我们要求next[i]的值，如果我们已经计算过next[i-1]的值，那我们就可以把next[i-1]的下一位位置 i 进行比较，如果相等，那next[i] = next[i - 1] + 1;如果不相等，我把再找next[i-1]的第二长可匹配后缀子路对应的模式串的子串的下一个字符与位置 i 进行比较，如果到next[i-1]的最短可匹配后缀子路对应的模式串的子串的下一个字符位置 i 进行比较不相等，那么next[i] = -1；如下图。
我们从上右图，可以看出，next[6]的值为2，次长next[6]其实就是下标0~2的后缀子串的最长可匹配模式串前缀的下标。next的实现代码如下：
// 计算模式串每个前缀的最长可匹配前缀子串的结尾字符下标
// eg: 前缀 cacac 最长可匹配的前缀为 cac next[4] = 2;
private int[] getNext(String pattStr, int m) {
int[] next = new int[m];
// next的下标代表模式串的前缀结尾下标，数组的值是前缀最长可以匹配前缀子串的结尾字符下标
next[0] = -1;
int k = -1;
for (int i = 1; i < m; i++) {
// next[i-1]下一个字符不对应i的字符
while (k >= 0 && pattStr.charAt(k + 1) != pattStr.charAt(i)) {
// 继续找好前缀 o ~ k 对应的next值
k = next[k];
}
// 找到了next[k]下一个字符等于 i 位置的字符
if (pattStr.charAt(k + 1) == pattStr.charAt(i)) {
k++;
}
next[i] = k;
}
return next;
}
KMP算法实现代码如下：
/**
* KMP 算法，好前缀
*
* @param mainStr 主串
* @param pattStr 模式串
* @return 模式串在主串中位置
*/
public int kmp(String mainStr, String pattStr) {
int n = mainStr.length();
int m = pattStr.length();
// 获取模式串要移动的下标
int[] next = getNext(pattStr, m);
// 模式串的位置
int j = 0;
for (int i = 0; i < n; i++) {
// 不相同,计算j的位置,一直找到a[i] 和 b[j]
while (j > 0 && mainStr.charAt(i) != pattStr.charAt(j)) {
j = next[j - 1] + 1;
}
if (mainStr.charAt(i) == pattStr.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
三、KMP 算法的时间复杂度分析
第一部分：next数组第一层循环执行了m-1次；第二层循环k的值是在减少的并且它累计值不会超过m,所以while循环中k=next[k] 总的执行次数也不可能超过m，所以 next数组的时间复杂度是O(m)。
第二部分：第一层for循环，i 不会超过n，执行次数会少于n；第二层while循环 ，j 每进行一次循环也是在变小，j 的总共增长的量也不会超过n，所以这部分的时间复杂度是O(n)。
综上所述，KMP算法的时间复杂度为O(m+n)。
