KMP算法的全称为Knuth-Morris-Pratt字符串查找算法，是可以在文本串s中快速查找模式串p的一种算法。
在详细讲解KMP算法之前，首先讲解一下暴力匹配。暴力匹配就是逐字符逐字符地进行匹配（比较s[i]和s[j]），如果当前字符匹配成功（s[i]==s[j]），就匹配下一个字符（i++;j++;）；如果匹配失败的话，就回溯（i=i-j+1;j=0;）。这样的算法时间复杂度是。
从上面可以看出暴力匹配算法，每次都会回溯到刚开始匹配的下一个字符，这样比较耗时，如果我们跳过之前匹配的字符从匹配失败的位置重新匹配，这样会出现缺漏。
为了解决这个问题，研究者引入了PMT（Partial Match Table，部分匹配表）。下一次j应该赋什么值只与模式串自身有关，即每个字符串都会对应一张PMT表。PMT中的pmt数组中位置i的内容是，从p[0]往后数、同时从p[i]往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。
KMP算法具体的匹配过程以ababcabaa为例：
Knuth-Morris-Pratt字符串查找算法-01.png
在匹配字符串的过程中，当我们在匹配j=8时发现s[i]与p[j]不相等，则会令j=pmt[j-1]=pmt[7]=3重新进行匹配，若此时s[i]与p[j]仍不相同，则继续令j进行回退。直至j回退到0处且仍不匹配时，我们不再令j回退，而选择移动i。
具体的KMP算法的正确匹配过程请阅读文献1。
KMP代码实现为：
public int strStr(String s, String p) {
int n = s.length(), m = p.length();
char[] cs = s.toCharArray(), cp = p.toCharArray();
int[] next = next(p);
for (int i = 0, j = 0; i < n; i++) {
while (j != 0 && cs[i] != cp[j]) j = next[j - 1];
if (cs[i] == cp[j]) j++;
if (j == m) return i - j + 1;
}
return -1;
}
PMT表的生成过程，如果使用暴力的话，时间复杂度会是。这种做法复杂度较高，因此我们采用更精妙的做法，错开一位后，让
p自己匹配自己，即用前缀去匹配后缀。其具体过程为下图所示：
Knuth-Morris-Pratt字符串查找算法-02.png
PMT数组生成的代码为：
public int[] next(String p) {
int m = p.length();
int[] pmt = new int[m];
char[] cs = p.toCharArray();
for (int i = 1, j = 0; i < m; i++) {
while (j != 0 && cs[i] != cs[j]) j = pmt[j - 1];
if (cs[i] == cs[j]) j++;
pmt[i] = j;
}
return pmt;
}
题目链接
参考文献：
