• 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“几种，而子序列则比子串多一个"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版本的代码，希望前端和后端的同学们都可以看懂。

    1. private static int kmp(String s1, String s2) {
    2.     if (s1 == null || s2 == null || s1.length() <= 0 || s2.length() <= 0 || s1.length() < s2.length()) {
    3.         // 非法参数判断
    4.         return -1;
    5.     }
    6.  
    7.     char[] str1 = s1.toCharArray();
    8.     char[] str2 = s2.toCharArray();
    9.  
    10.     int[] next = getNextArr(str2);
    11.  
    12.     int i1 = 0, i2 = 0;
    13.     while (i1 < str1.length && i2 < str2.length) {
    14.         if (str1[i1] == str2[i2]) {
    15.             i1++;
    16.             i2++;
    17.         } else if (next[i2] >= 0) {
    18.             i2 = next[i2];
    19.         } else {
    20.             // i2 == 0
    21.             i1++;
    22.         }
    23.     }
    24.  
    25.     return i2 >= str2.length ? i1 - i2 : -1;
    26. }

            如何看这个函数的时间复杂度呢？我们要看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]错了的悖论，这里不再次证明。

    1. private static int[] getNextArr(char[] str2) {
    2.     if (str2.length == 1) {
    3.         return new int[] { -1 };
    4.     }
    5.     int[] next = new int[str2.length];
    6.  
    7.     next[0] = -1;
    8.     next[1] = 0;
    9.  
    10.     // ne: next[i-1]
    11.     int i = 2, ne = 0;
    12.  
    13.     while (i < next.length) {
    14.         if (str2[i-1] == str2[ne]) {
    15.             next[i++] = ++ne;
    16.         } else if (next[ne] >= 0) {
    17.             ne = next[ne];
    18.         } else {
    19.             next[i++] = 0;
    20.         }
    21.     }
    22.  
    23.     return next;
    24. }

            我们再考虑一下求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版

    1. package com.dddf;
    2.  
    3. public class C01_KMP {
    4.  
    5.     private static int kmp(String s1, String s2) {
    6.         if (s1 == null || s2 == null || s1.length() <= 0 || s2.length() <= 0 || s1.length() < s2.length()) {
    7.             // 非法参数判断
    8.             return -1;
    9.         }
    10.  
    11.         char[] str1 = s1.toCharArray();
    12.         char[] str2 = s2.toCharArray();
    13.  
    14.         int[] next = getNextArr(str2);
    15.  
    16.         int i1 = 0, i2 = 0;
    17.         while (i1 < str1.length && i2 < str2.length) {
    18.             if (str1[i1] == str2[i2]) {
    19.                 i1++;
    20.                 i2++;
    21.             } else if (next[i2] >= 0) {
    22.                 i2 = next[i2];
    23.             } else {
    24.                 // i2 == 0
    25.                 i1++;
    26.             }
    27.         }
    28.  
    29.         return i2 >= str2.length ? i1 - i2 : -1;
    30.     }
    31.  
    32.     private static int[] getNextArr(char[] str2) {
    33.         if (str2.length == 1) {
    34.             return new int[] { -1 };
    35.         }
    36.         int[] next = new int[str2.length];
    37.  
    38.         next[0] = -1;
    39.         next[1] = 0;
    40.  
    41.         // ne: next[i-1]
    42.         int i = 2, ne = 0;
    43.  
    44.         while (i < next.length) {
    45.             if (str2[i-1] == str2[ne]) {
    46.                 next[i++] = ++ne;
    47.             } else if (next[ne] >= 0) {
    48.                 ne = next[ne];
    49.             } else {
    50.                 next[i++] = 0;
    51.             }
    52.         }
    53.  
    54.         return next;
    55.     }
    56.  
    57.     // for test
    58.     public static String getRandomString(int possibilities, int size) {
    59.         char[] ans = new char[(int) (Math.random() * size) + 1];
    60.         for (int i = 0; i < ans.length; i++) {
    61.             ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
    62.         }
    63.         return String.valueOf(ans);
    64.     }
    65.  
    66.     public static void main(String[] args) {
    67.         int possibilities = 5;
    68.         int strSize = 20;
    69.         int matchSize = 5;
    70.         int testTimes = 5000000;
    71.         System.out.println("test begin");
    72.         int successNum = 0;
    73.         int failNum = 0;
    74.         for (int i = 0; i < testTimes; i++) {
    75.             String str = getRandomString(possibilities, strSize);
    76.             String match = getRandomString(possibilities, matchSize);
    77.             int kmpRes = kmp(str, match);
    78.             int apiRes = str.indexOf(match);
    79.             if (kmpRes != apiRes) {
    80.                 System.out.println(String.format("str:%s, match:%s, kmpRes:%d, apiRes:%d", str, match, kmpRes, apiRes));
    81.                 failNum++;
    82.             } else {
    83.                 successNum++;
    84.             }
    85.         }
    86.         System.out.println("test finish, successNum: " + successNum + ", failNum: " + failNum);
    87.     }
    88.  
    89.  
    90. }

    2. C++版

    1. #include
    2. #include
    3. using namespace std;
    4.  
    5. vector<int> getNext(string str)
    6. {
    7.     int len = str.length();
    8.     vector<int> next(len); 
    9.     next[0] = -1;
    10.     if (len == 1)
    11.     {
    12.         return next;
    13.     }
    14.  
    15.     next[1] = 0;
    16.  
    17.     int i = 2;
    18.     int ne = 0;
    19.     while (i < len)
    20.     {
    21.         if (str[i-1] == str[ne])
    22.         {
    23.             next[i++] = ++ne;
    24.         } else if (next[ne] >= 0)
    25.         {
    26.             ne = next[ne];
    27.         } else 
    28.         {
    29.             next[i++] = 0;
    30.         }
    31.     }
    32.  
    33.     return next;
    34. }
    35.  
    36. int kmp(string str1, string str2)
    37. {
    38.     if (str1.length() <= 0 || str2.length() <= 0 || str1.length() < str2.length())
    39.     {
    40.         return -1;
    41.     }
    42.  
    43.     vector<int> next = getNext(str2);
    44.  
    45.     int i1 = 0, i2 = 0;
    46.     while (i1 < str1.length() && i2 < str2.length())
    47.     {
    48.         if (str1[i1] == str2[i2])
    49.         {
    50.             i1++;
    51.             i2++;
    52.         } else if (next[i2] >= 0)
    53.         {
    54.             i2 = next[i2];
    55.         } else
    56.         {
    57.             i1++;
    58.         }
    59.     }
    60.  
    61.     return i2 >= str2.length() ? i1 - i2 : -1;
    62. }
    63.  
    64. int main()
    65. {
    66.     string str1 = "ababababababc";
    67.     string str2 = "aa";
    68.     string str3 = "abc";
    69.  
    70.     cout << kmp(str1, str2) << endl;
    71.     cout << kmp(str1, str3) << endl;
    72. }

    3. javascript版

    1. var getNextArr = function (str) {
    2.     if (str.length == 1) {
    3.         return [ -1 ];
    4.     }
    5.  
    6.     let next = [];
    7.     next[0] = -1;
    8.     next[1] = 0;
    9.  
    10.     let i = 2;
    11.     // ne = next[i-1]
    12.     let ne = 0;
    13.  
    14.     while (i < str.length) {
    15.         if (str[i-1] == str[ne]) {
    16.             next[i++] = ++ne;
    17.         } else if (next[ne] >= 0) {
    18.             ne = next[ne];
    19.         } else {
    20.             next[i++] = 0;
    21.         }
    22.     }
    23.  
    24.     return next;
    25. }
    26.  
    27. var kmp = function (str1, str2) {
    28.     if (str1 == null || str2 == null || str1.length <= 0 || str2.length <= 0 || str1.length < str2.length) {
    29.         return -1;
    30.     }
    31.  
    32.     let i1 = 0;
    33.     let i2 = 0;
    34.  
    35.     let next = getNextArr(str2);
    36.  
    37.     while (i1 < str1.length && i2 < str2.length) {
    38.         if (str1[i1] == str2[i2]) {
    39.             i1++;
    40.             i2++;
    41.         } else if (next[i2] >= 0) {
    42.             i2 = next[i2];
    43.         } else {
    44.             i1++;
    45.         }
    46.     }
    47.  
    48.     return i2 >= str2.length ? i1 - i2 : -1;
    49.  
    50.  
    51. }
    52.  
    53. let str1 = "ababababababc";
    54. let str2 = "aa";
    55. let str3 = "abc";
    56.  
    57. console.log(kmp(str1, str2));
    58. console.log(kmp(str1, str3));

  • 相关阅读:
    Nacos配置中心集群原理及源码分析
    Python自学：使用多进程处理 multiprocessing
    鸿蒙HarmonyOS实战-ArkUI组件（Radio）
    AirtestIDE编辑窗内，脚本内容消失，显示一片红色怎么办？
    李想的理想，不太「理想」
    【LeetCode】【SQL】刷题笔记
    安装Docker(Linux:CentOS)
    护眼台灯横评|书客、明基、松下品牌大测评告诉你谁才是最亮的星！
    重载和重写的底层原理——虚拟机字节码执行引擎
    云原生技术中台 CNStack2.0 正式发布
  • 原文地址：https://blog.csdn.net/Jarvenman/article/details/126685284