张作霖，下雪了，你学会KMP了吗——一篇文章彻底弄懂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"共7种，而子序列则比子串多一个"ac"，因为子序列不需要保证连续。

因此可以得出一些结论，对于一个长度为n的字符串，保证字符串中没有重复字符，则它的子序列的个数为2n2^n2n，因为字符串中的每个字符都有“要”和“不要”两种选择。而子串则只有n(n+1)2+1\frac {n(n+1)} {2} + 12n(n+1)​+1个，原因如下：

• 长度为0的子串有1个；
• 长度为1的子串有n个；
• 长度为2的子串有n-1个；
• 长度为3的子串有n-2个
• ...
• 长度为n的子串有1个

因此所有子串的长度为1+n+(n−1)+(n−2)+...+1=(1+n)×n2+11 + n + (n-1) + (n-2) + ... + 1 = \frac {(1 + n) \times n} {2} + 11+n+(n−1)+(n−2)+...+1=2(1+n)×n​+1

暴力解法

流程描述

首先考虑最暴力的解法，不难想到肯定是双层for循环。字符串s2首先从s1的0位置开始比较，即比较s1[0]和s2[0]，如果相等则继续比较s1[1]和s2[1]，再相等则再继续比较s1[2]和s2[2]，...。如果不想等，则改为从s1的1位置开始比较，即比较s1[1]和s2[0]，以此类推。

举个例子，假设s1 = "abababca"，s2 = "abc"，则两个字符串的比较过程如下。

时间复杂度分析

时间复杂度应该以算法的最差情况来估算，那么思考一下暴力解法的最坏情况是什么呢？

我们给出这样的两个字符串：s1 = "aaaaaab"，s2 = "aab"，这两个字符串在上述流程中的比较过程是什么样的呢？

可以看到，在上述的比较过程中，每一次都是比较到s2的最后一个字符时才判断出两个字符串不匹配。我们假设s1的长度是n，s2的长度是m，那么这种暴力解法的时间复杂度就应该是O(n×m)O(n \times m)O(n×m)

KMP算法

next数组

学习KMP算法的第一步，是了解字符串中的一个重要属性，我们用一个数组next来表示。对于一个字符串str，next[i]表示的含义是：对于str[0...i-1]这个子串，它的前缀和后缀的最长相等长度。

举例说明：str = "abcabcz"，在这个字符串中next[6]的含义是在"abcabc"这个子串中寻找前缀和后缀的最长相等长度。

前/后缀长度	1	2	3	4	5
前缀值	a	ab	abc	abca	abcab
后缀值	c	bc	abc	cabc	bcabc
是否相等？	❌	❌	✅	❌	❌

通过上面这张表可以看出，"abcabc"这个字符串中，前缀与后缀的最长相等长度为3，所以我们记next[6] = 3

换一个极端一点的例子。在"aaaaab"这个字符串中，next[5]的值等于多少？

要求这个值，就是要求"aaaaa"字符串中前缀和后缀的最长相等长度，我们可以得到下面的这张表：

前/后缀长度	1	2	3	4
前缀值	a	aa	aaa	aaaa
后缀值	a	aa	aaa	aaaa
是否相等？	✅	✅	✅	✅

可以看出，"aaaaa"这个字符串中，前缀与后缀的最长相等长度为4，因此我们计next[5] = 4。

理解了next数组的含义，我们来算一下字符串"aabaabcaabd"的next数组。

• i = 0时，没有要计算的字符串，我们把此时的next值记为-1；
• i = 1时，字符串没有要比较大前缀和后缀，我们把此时的next值记为0。

也就是说，对于每一个字符串，next[0] = -1和next[1] = 1都是固定的。为什么这样记我们会在后面的使用部分来解答。

这样，我们就得到了下面的这张表。

i	0	1	2	3	4	5	6	7	8	9	10
substring	""	"a"	"aa"	"aab"	"aaba"	"aabaa"	"aabaab"	"aabaabc"	"aabaabca"	"aabaabcaa"	"aabaabcaab"
next[i]	-1	0	1	0	1	2	3	0	1	2	3

以上，我们就掌握了KMP算法中最重要的变量：next数组的含义。

核心流程

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]]。

途中相同颜色的矩形代表相等的字符串。可以看到，由于next[m]的存在，所以图中的蓝色区域一定相等。我们将s1[k+m]和s2[next[m]]做匹配时，相当于将s2的蓝色区域向右移动了一大块，保证和s1的蓝色区域一定是匹配的。

那么为什么一定是s1[k+m]和s2[next[m]]做匹配呢？如果s1[k+m]之前的位置（假设是s1[k+m-t]）和s2[next[m]]做匹配为什么一定不能成功呢？

如上图所示，如果s1[k+m-t]和s2[next[m]]匹配（也可以看成是s1[k+m]和s2[next[m] + t]匹配，那么一定要求图中三个绿色的字符串片段是相等的。如果符合上面的要求，那说明s2的next[m]一定比现在算出来的更大，说明s2的next数组求错了，肯定不成立。

核心代码

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循环，算法的时间复杂度就取决于while循环中三个分支执行的次数。在第一个分支中i1增加，i2不变；第二个分支中i1不变，i2回退，这样的变化规律我们很难估算出循环的执行次数，所以我们需要换一个思路。

在这个代码的执行过程中，i1的取值范围是[0, n]，i2的取值范围是[0, n]，那么i1 - i2的取值范围应该也是[0, n]。在while循环内的三个分支中：

• 第一个分支：i1增加，i1 - i2不变；
• 第二个分支：i1不变，i1 - i2增加；
• 第三个分支：i1增加，i1 - i2增加

所以整个while循环走完后，一定最多只走了2n次，所以整个while循环的时间复杂度是O(n)O(n)O(n)

next数组的求法

流程

我们采取从左到右的方式计算next数组，这样next[i]就可以使用next[0...i-1]的结果加速，就是所谓的动态规划。

next[i]如何求：

• 如果str[i-1] == str[next[i-1]]，则next[i] = next[i-1] + 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，那么next[22]就可以直接得出等于10。

但现在可以看到str[21] != str[9]，next[9] = 3，所以我们继续判断str[21]是否等于str[3]，如果相等直接直接判断next[22] = next[9] + 1 = 4 ，否则继续向前找。

代码

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;
}

如果这篇文章有帮助到你，请你帮我点一个免费的赞，这对我非常重要，谢谢！（手动鞠躬）

欢迎关注公众号：程序员冻豆腐， 里面有我所有的首发文章。