KMP是数据结构与算法课程中比较重要的一课，也是大厂面试算法的基础之一。KMP属于是算法中的几个门槛之一，理解起来会比较困难，今天我们用这篇文章详细讲一下算法的内容，希望能给大家带来帮助。
KMP算法要解决的主要问题，是一个字符串s2是否是s1的子串的问题。举个例子，假设s1 = "abababc"，s2 = "abc"，则判断s2是s1的子字符串，并返回s2在s1中的位置4，如果s2 = "abd"，则返回-1表示s2不是s1的子字符串。
这里插一句，要注意子串和子序列的区别，通俗地说，子串是指该串的一个连续的局部。如果不要求连续,则可称为它的子序列。举个例子，对于字符串"abc"，它的子串只有"", "a", "b", "c", "ab", "bc", "abc“几种，而子序列则比子串多一个"ac"，因为子序列不需要保证连续
从而可以得出一个结论，对于一个长度为n的字符串，保证字符串中字符各不相同，它的子序列的个数为2的n次方，因为字符串中的每个字符都可以有 要 和不要两种选择，而子串只有n * (n+1) / 2 + 1个
- 长度为0的子串有1个
- 长度为1的子串有n个
- 长度为2的子串有n-1个
- 长度为3的子串有n-2个
- ...
- 长度为n的子串有1个
所以所有子串的长度为1 + n + n-1 + n-2 + n-3 + ... + 1 = (1 + n) * n / 2 + 1
首先不考虑KMP，先考虑最暴力的解法，不难想到肯定是双层for循环，字符串s2首先从s1的0位置开始比较，即比较s1[0] 和 s2[0]，如果相等则继续比较s1[1] 和 s2[1]，再相等则再继续比较s1[2]和s2[2]。如果不相等，则将改为从s1的1位置开始比较，即比较s1[1]和s2[0]，以此类推。语言描述起来比较难懂，我做了一张演示图，可以帮助大家比较好理解。
然后考虑一下这种做法的时间复杂度。众所周知，时间复杂度应该以算法的最坏情况来估计，这种方法的最坏情况是什么呢？
我们给出这样的两个字符串：s1 = "aaaaaab"，s2 = "aab"，考虑一下这两个字符串通过上述解法，比较过程是什么样的呢？
可以看到，在上述的比较过程中，每一次都是s1和s2比较到最后一个字符时才判断出两个字符串不匹配，我们假设s1的长度是n，s2的长度是m，不难得出这种暴力解法的时间复杂度是O(n * m)
为什么这种暴力解法的时间复杂度这么高？我们先简单提一下，后面我们再和KMP算法对比来看，是因为，s2[0]在s1[0]处的比较结果，对于s2[0]在s1[1]处的比较结果没有任何的帮助。
学习KMP的第一步，是了解字符串中的一个重要属性，我们用一个数组next来表示。next[i]表示的是：str[0...i-2]和str[1...i-1]位置上，前缀和后缀的最长相等长度。
举个简单的例子：str = "abcabcz"，我们计算一下next[6]，即在"abcabc"这个字符串中，寻找前缀和后缀的最长相等长度。
（为什么要叫next，我们在后面会讲）
通过上表可以看出，"abcabc"这个字符串中，前缀与后缀的最长相等长度为3，我们就记next[6] = 3
换一个极端一点的例子，"aaaaab"字符串中，next[5]等于多少？要求这个值，就是要求"aaaaa"字符串中前缀和后缀的最长相等长度，我们可以得到下面的这张表：
可以看出，"aaaaa"这个字符串中，前缀与后缀的最长相等长度为4，我们计next[5] = 4
懂了next数组的含义，我们算一下这个字符串"aabaabcaabd"的next数组
i = 0时，没有要计算的字符串，我们把此时的数值计为-1；
i = 1时，字符串没有要比较的前缀和后缀，我们把此时的数值计为0，也就是说，对于每一个字符串，next[0] = -1和next[1] = 1都是固定的，至于为什么这么规定，我们到了用的时候后面就会知道。
以上，我们就掌握了KMP算法的中最重要的变量：next数组的含义，下面就是最重要的一步，KMP算法的核心
KMP算法要求首先计算出s2的next数组，在s1和s2的一次匹配过程中，s1[k] = s2[0]，s1[k+1] = s2[1]，s1[k+2] = s2[2]，...，s1[k+m] != s2[m]，在原来的暴力解法中，下一步是将s2的位置后移一位，也就是匹配s2[0]和s1[k+1]，但是在KMP中，我们可以直接匹配s1[k+m]和s2[next[m]]。语言描述比较晦涩，我用如下的动图来做演示。
kmp流程-1
图中相同颜色的矩形代表相等的字符串，可以看到，因为next[m]的的存在，所以图中蓝色区域一定相等，我们将s1[k+m]和s2[next[m]]做匹配时，会将s2的蓝色区域向后移动，保证和s1的蓝色区域一定是匹配的。
以上就是KMP算法的核心内容，下面我们尝试对它做一下证明，即为什么一定是s1[k+m]和s2[next[m]]做匹配，s1的k+m之前的位置（即s1[k+m-t]和s2[0]做匹配为什么不能匹配成功呢？
如果是s1[k+m-t]...s1[k+m]和s2[0]...s2[next[m]+t]匹配，那一定要求图中三个绿色的字符串片段是相等的，但是如果确实相等，那么s2的next[m]一定比现在算出来的更大，那只能说s2的next数组求错了，所以不成立。
给KMP算法举一个实际的例子，str1 = "aabaadaabaac"，str2 = "aabaac"，那么两个字符串KMP比较的流程如下
kmp流程实际举例
先简单看一下这个流程的代码，在文章的最后，我贴了java，c++和js版本的代码，希望前端和后端的同学们都可以看懂。
private static int kmp(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() <= 0 || s2.length() <= 0 || s1.length() < s2.length()) {
// 非法参数判断
return -1;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[] next = getNextArr(str2);
int i1 = 0, i2 = 0;
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] >= 0) {
i2 = next[i2];
} else {
// i2 == 0
i1++;
}
}
return i2 >= str2.length ? i1 - i2 : -1;
}如何看这个函数的时间复杂度呢？我们要看while循环中三个分支走的次数。在这个函数中，i1 的取值范围是[0, n]，i2 的取值范围是[0, m]，又因为m肯定是小于n的，所以我们取最大值，即i2的取值范围肯定也是[0, n]。我们把 i1 和 i2 取一个运算：i1 - i2，那么i1 - i2 的取值范围应该也是[0, n]
在这个while循环的三个分支中：
第一个分支：i1 增加，i2 - i1 不变
第二个分支：i1 增加，i2 - i1 增加
第三个分支：i1 不变，i2 - i1 增加
所以整个循环走完，最大只增加了2 * n次，所以整个while循环的时间复杂度是O(N)。
然后我们看一下next数组的求法。
我们采取从左到右的方式计算next数组，这样next[i]就可以使用之前的计算结果加速，也就是我们通常说的动态规划。
首先有一点可以确定的是，i 位置的next数值和他自己是没关系的，因为next数值的算法就是 i 位置之前的字符串前缀和后缀相等的最大长度。
如果str[i-1] == str[next[i-1]]的话，那么next[i] = next[i-1] + 1
next数组求法-1
如上面的演示图所示，已知的是i-1位置的next值即next[i-1]，也就是图中两个蓝色区域是相等的，如果str[i-1] 和 str[next[i-1]]相等，相等区域就可以向右扩一位，即next[i] = next[i-1] + 1
想一下为什么不可能大于这个值？
next数组求法-2-反证
我们使用反证法，假设next[i]比我们现在算出来的值要大， 也就是图中的黄色区域，那么意味着去掉str[i-1]和str[next[i-1]]的部分肯定也是相等的，那也就意味着我们现在的next[i-1]一定比之前算出来的next[i-1]要大，所以之前算出来的next[i-1]一定是错的
如果str[i-1] != str[next[i-1]]，那么就去检查str[i-1] 和str[next[next[i-1]]，看是否相等，如果相等就等于next[next[i-1]] + 1，如果还不相等就继续向前找，如果一直找不到就为0
语言描述比较抽象，我们举个实际的例子
我们要算k位置的next值， 即next[22]，那我们要参考next[21]
我们判断出21位置的前缀和后缀的最大相等长度是9，即next[21] = 9。如果把21位置的字符换成和9位置相同的e那将成为绝杀，可惜换不得。如果21位置和9位置相等可以直接判断next[22] = 10
然后我们继续判断next[9]。图中可以看出，next[9] = 3，我们判断str[21]是否等于str[3]，如果相等则可以直接判断next[22] = next[9] + 1 = 4，否则继续向前找。至于为什么不能大于这个值，推法和上面还是一样的，最后会得出next[9]错了的悖论，这里不再次证明。
private static int[] getNextArr(char[] str2) {
if (str2.length == 1) {
return new int[] { -1 };
}
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
// ne: next[i-1]
int i = 2, ne = 0;
while (i < next.length) {
if (str2[i-1] == str2[ne]) {
next[i++] = ++ne;
} else if (next[ne] >= 0) {
ne = next[ne];
} else {
next[i++] = 0;
}
}
return next;
}我们再考虑一下求next数组的代码的时间复杂度，我们采用和上面类似的证法，getNextArr方法中有两个变量：i，ne，假设str2的长度是m，那么 i 和 ne 两个变量的取值范围都是[0, m]。while的三个分支中，i，ne有增有减，证明不出时间复杂度，所以我们把 i 和 ne 两个变量做差得到 i - ne，i - ne 的取值范围也是[0, m]。那么在while的三个分支中：
第一个分支：i 增加，i - ne 不变
第二个分支：i 不变，i - ne 增加
第三个分支：i 增加，i - ne 不变
所以整个while循环的最大执行次数是 2 * m次，即整个方法的时间复杂度是O(m)。
在整个kmp算法中，kmp方法的时间复杂度是O(n)，getNextArr方法的时间复杂度是O(m)，在kmp中 m 一定小于 n，所以整个kmp算法的时间复杂度是O(n)。
回顾一下文章上面留下的两个坑。
首先next数组为什么叫next，是因为next数组表示了当str1[k]和str2[i]匹配失败时，str2需要匹配的下一个位置，即将str1[k]和str2[next[i]位置做匹配。
其次，kmp算法相比暴力算法的优势在于，next数组使得 str2[i] 位置的匹配结果对下一次匹配是有帮助的，因为有next数组的存在，使得下一次匹配不需要对str1回退，对str2对回溯也不一定需要回退到0位置。
以上就是kmp算法的全部内容，各个语言版本的整体代码在下面，如果有需要其他语言版本的，或者对文章内容有疑问的，也欢迎联系作者。
1. Java版
package com.dddf;
public class C01_KMP {
private static int kmp(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() <= 0 || s2.length() <= 0 || s1.length() < s2.length()) {
// 非法参数判断
return -1;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[] next = getNextArr(str2);
int i1 = 0, i2 = 0;
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] >= 0) {
i2 = next[i2];
} else {
// i2 == 0
i1++;
}
}
return i2 >= str2.length ? i1 - i2 : -1;
}
private static int[] getNextArr(char[] str2) {
if (str2.length == 1) {
return new int[] { -1 };
}
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
// ne: next[i-1]
int i = 2, ne = 0;
while (i < next.length) {
if (str2[i-1] == str2[ne]) {
next[i++] = ++ne;
} else if (next[ne] >= 0) {
ne = next[ne];
} else {
next[i++] = 0;
}
}
return next;
}
// for test
public static String getRandomString(int possibilities, int size) {
char[] ans = new char[(int) (Math.random() * size) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
}
return String.valueOf(ans);
}
public static void main(String[] args) {
int possibilities = 5;
int strSize = 20;
int matchSize = 5;
int testTimes = 5000000;
System.out.println("test begin");
int successNum = 0;
int failNum = 0;
for (int i = 0; i < testTimes; i++) {
String str = getRandomString(possibilities, strSize);
String match = getRandomString(possibilities, matchSize);
int kmpRes = kmp(str, match);
int apiRes = str.indexOf(match);
if (kmpRes != apiRes) {
System.out.println(String.format("str:%s, match:%s, kmpRes:%d, apiRes:%d", str, match, kmpRes, apiRes));
failNum++;
} else {
successNum++;
}
}
System.out.println("test finish, successNum: " + successNum + ", failNum: " + failNum);
}
}2. C++版
#include<iostream>
#include<vector>
using namespace std;
vector<int> getNext(string str)
{
int len = str.length();
vector<int> next(len);
next[0] = -1;
if (len == 1)
{
return next;
}
next[1] = 0;
int i = 2;
int ne = 0;
while (i < len)
{
if (str[i-1] == str[ne])
{
next[i++] = ++ne;
} else if (next[ne] >= 0)
{
ne = next[ne];
} else
{
next[i++] = 0;
}
}
return next;
}
int kmp(string str1, string str2)
{
if (str1.length() <= 0 || str2.length() <= 0 || str1.length() < str2.length())
{
return -1;
}
vector<int> next = getNext(str2);
int i1 = 0, i2 = 0;
while (i1 < str1.length() && i2 < str2.length())
{
if (str1[i1] == str2[i2])
{
i1++;
i2++;
} else if (next[i2] >= 0)
{
i2 = next[i2];
} else
{
i1++;
}
}
return i2 >= str2.length() ? i1 - i2 : -1;
}
int main()
{
string str1 = "ababababababc";
string str2 = "aa";
string str3 = "abc";
cout << kmp(str1, str2) << endl;
cout << kmp(str1, str3) << endl;
}3. javascript版
var getNextArr = function (str) {
if (str.length == 1) {
return [ -1 ];
}
let next = [];
next[0] = -1;
next[1] = 0;
let i = 2;
// ne = next[i-1]
let ne = 0;
while (i < str.length) {
if (str[i-1] == str[ne]) {
next[i++] = ++ne;
} else if (next[ne] >= 0) {
ne = next[ne];
} else {
next[i++] = 0;
}
}
return next;
}
var kmp = function (str1, str2) {
if (str1 == null || str2 == null || str1.length <= 0 || str2.length <= 0 || str1.length < str2.length) {
return -1;
}
let i1 = 0;
let i2 = 0;
let next = getNextArr(str2);
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] >= 0) {
i2 = next[i2];
} else {
i1++;
}
}
return i2 >= str2.length ? i1 - i2 : -1;
}
let str1 = "ababababababc";
let str2 = "aa";
let str3 = "abc";
console.log(kmp(str1, str2));
console.log(kmp(str1, str3));