KMP算法是由Donald Knuth、James H.Morris和于1977年联合发明的，用来处理字符串匹配问题。
【题目描述】：对给定两个字符串str和substr，如果字符串str中含有子串substr，则返回substr在str中的开始位置，不含有则返回-1。
在介绍KMP算法之前，我们先来看普通解法（朴素模式匹配）怎么做。
最普通的解法是从左到右遍历str的每一个字符，然后看如果以当前字符作为第一个字符出发是否匹配出 substr，这里从数组下标为0开始。假设 str=“bcabcababcbabcabba”，substr=“abcabb”。
1.substr第0位字符不匹配，说明从str[0]出发进行匹配是不行的，后移1位，从str[1]出发进行匹配
b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | a | b | b |
2.substr第0位字符不匹配，后移1位
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | a | b | b |
3.substr第5位字符不匹配，后移1位
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | b |
4.substr第0位字符不匹配，后移1位
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | a | b | b |
如此循环，直到匹配成功
普通解法的时间复杂度较高，假设字符串str和substr长度分别为N和M，从每个字符出发时，匹配的代价都可能是O（M），一共有N个字符，所以整体的时间复杂度为O（N×M）。普通解法的时间复杂度这么高，是因为每次遍历到一个字符时，检查工作相当于从无开始，之前的遍历检查不能优化当前的遍历检查。
比如在第3步，我们已经知道"abcab"这5个字符是匹配的，而普通解法没有利用到这一事实，只是简单的将substr串后移；KMP算法思想就是利用这一事实，减少重复比较的次数，提高算法效率。
KMP算法是怎么实现的这一点呢？他在此使用了一个叫做 “部分匹配表” 的数据结构，如下图所示，这张表是怎样求得的在后面会讲到。
| substr | a | b | c | a | b | b |
|---|---|---|---|---|---|---|
| 部分匹配值 | 0 | 0 | 0 | 1 | 2 | 0 |
在进行到第3步时，采用KMP算法，利用部分匹配表计算substr向后移动的位数：
3.substr第5位字符’b’不匹配，查表得到部分匹配值为0，说明str当前不匹配的位置应该与substr的第0位字符进行下一次匹配，即substr向后移动5位（=已匹配串"abcab"长度5 - 查表得到的部分匹配值0）
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | b |
4.substr第3位字符不匹配，查表得部分匹配值为1，substr向后移动2位（=已匹配串"abc"长度3 - 查表得到的部分匹配值1）
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | b |
5.substr第0位字符不匹配，后移1位
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | a | b | b |
6.substr第0位字符不匹配，后移1位
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | a | b | b |
7.substr第0位字符不匹配，后移1位得到在str匹配的初始位置11
| b | c | a | b | c | a | b | a | b | c | b | a | b | c | a | b | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | b |
部分匹配表，也就是我们常说的next数组，它的求解过程是怎样的呢？首先我们需要了解两个概念"前缀"和"后缀"。
"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
如，对于字符串"abcab"，他所有的前缀为{“a”,“ab”,“abc”,“abca”}，后缀集合为{“b”,“ab”,“cab”,“bcab”}
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度
因此"abcab"部分匹配值等于2，我们不难能手动计算出substr的部分匹配表（下标0位置默认部分匹配值为0）。
【算法实现】首先给出朴素模式匹配的算法，这里只用到了一个双重循环，简单粗暴，容易理解
public static int naive(char str[], char substr[]) {
int i, j, k = 0;//k记录下一轮比较的初始位置
for (i = k; i < str.length; ) {
for (j = 0; j < substr.length; ) {
if (str[i] == substr[j]) {
++i;
++j;
} else {
i = ++k;
break;
}
}
if (j == substr.length)
return k;
}
return -1;
}
为了便于与KMP算法对照，将朴素模式匹配算法改造成如下形式，与上述代码的原理别无二致
public static int naive2(char str[], char substr[]) {
int i = 0, j = 0, k = 0;
while (i < str.length && j < substr.length) {
if (str[i] == substr[j]) {
++i;
++j;
} else {
i = ++k;
j = 0;
}
if (j == substr.length)
return k;
}
return -1;
}
然后这是KMP算法求解过程，可以与上述朴素模式匹配算法对照来看，可以看出KMP算法：
1.需要next数组
2.不需要变量k来记录下一轮比较的初始位置，因为i不需要回溯
3.返回值问题，用i - substr.length来表示与模式串substr匹配的首字符所在位置
public static int kmp(char str[], char substr[], int next[]) {
int i = 0, j = 0;//因为i不需要回溯，所以变量k不需要
while (i < str.length && j < substr.length) {
if (j == 0 || str[i] == substr[j]) {
++i;
++j;
} else {
j = next[j];
}
if (j == substr.length)
return i - substr.length;//与模式串匹配的首字符所在位置
}
return -1;
}
然后是next数组的代码实现
public static void getNext(char substr[], int next[]) {
int i, k;//k为substr[0..i]最大前后缀长度
next[0] = 0;
for (i = 1, k = 0; i < substr.length; ++i) {
while (k > 0 && substr[i] != substr[k])
k = next[k - 1];
if (substr[i] == substr[k])
k++;
next[i] = k;
}
}
