刚拿极越的offer能去吗？|kmp|下标|代码|字符串|指针|极越|算法

专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一网友在网上问刚拿到极越的offer能去吗？这是典型的只会蒙着头面试，不看新闻的结果，极越在2024年12月10日爆出“原地解散”的消息，都已经倒闭了还去干啥。截至2024年11月份，极越汽车年内累计销量约为1.3万辆，而在11月份，极越的销量仅为2485台，这些刚买极越车的，售后咋搞，当然这也不是我关心的。

--------------下面是今天的算法题--------------

这里我们来讲一下KMP算法，KMP 算法主要用于字符串匹配的，它的时间复杂度 O(m+n) 。常规的字符串匹配我们一般都这样做，使用两个指针，一个指向主串，一个指向模式串，如果它俩指向的字符一样，它俩同时往右移一步，如果它俩指向的字符不一样，模式串的指针重新指向它的第一个字符，主串的指针指向它上次开始匹配的下一个字符，如下图所示。

我们看到当模式串和主串匹配失败的时候，模式串会从头开始重新匹配，主串也会回退，但我们知道失败字符之前的子串都是匹配成功的，那么这个信息能不能被我们利用呢？当然可以，这个就是我们这里要讲的 KMP 算法。

通过上面的图我们可以知道，当某个字符匹配失败的时候，它前面的肯定都是成功的，也就是说字符串 s1 和字符串 s2 完全一样。在模式串中，匹配失败的字符前面 b4 和 b3 是相同的，所以我们可以得到 b1，b2，b3，b4 都是相同的，也就是说b2 和 b3 也是相同的，既然是相同的，跳过即可，不需要在比较了，直接从它们的下一个字符开始匹配。

KMP 算法的核心部分就是找出模式串中每个字符前面到底有多少字符和最开始的字符相同，我们用 next 数组表示。有的描述成真前缀和真后缀的相同的数量。这里要注意当前字符前面的字符不包含第 1 个字符，最开始的字符也不能包含当前字符，比如在模式串 abc 中不能说字符 c 前面有 ab 和最开始的 ab 相同，来看下表。

下标 0 1 2 3 4 5 6 模式串 a b c a b e a next[i] -1 0 0 0 1 2 0

使用两个指针 i 和 j ，其中 j 是字符 p[i] 前面与最开始字符相同的数量，也是 next[i] 。如果 p[j]==p[i]，也就是说字符 p[i+1] 前面有 j+1 个字符和最开始的 j+1 个字符相同，所以可以得到 next[i+1]=j+1 ，这个很容易理解。如果 p[j]！=p[i]，我们让指针 j 等于 next[j] ，然后重新和 p[i] 比较，这就是回退，这个回退也是 KMP 算法的最核心部分，我们来分析下为什么要这样回退。

如上图所示，如果 nxet[j] 大于 0 ，那么 j 前面的 b2 和 b1 是相同的，我们知道 S1 和 S2 也是相同的，所以我们可以得出 b1，b2，b3，b4 都是相同的，如果 p[i]!=p[j] ，只需要让 j 回退到 next[j] ，然后 i 和 j 在重新比较，这个 next[j] 就是 b1 的长度，因为 b1 和 b4 是相同的，所以不需要再比较了。如果还不相同， j 继续回退，直到回退到 -1 为止，我们拿个真实的字符串看下，如下图所示。

我们看到 b1，b2，b3，b4 是相同的，它们都是字符串 "abc" ，如果 p[i]!=p[j] ，我们就让 j 回退到 next[j] ，因为它们前面 b1 和 b4 是相同的，没必须要在比较了，最后再来看下代码。

public int strStr(String s, String p) {     int i = 0;// 主串S的下标。     int j = 0;// 模式串P的下标。     int[] next = new int[p.length()];     getNext(p, next);// 计算next数组。     while (i < s.length() && j < p.length()) {         // 如果j为-1或者p[i]==p[j]，i和j都往后移一步。当j为-1时，         // 说明p[i]!=p[0]，然后i往后移一步，j也往后移一步指向p[0]。         if (j == -1 || s.charAt(i) == p.charAt(j)) {             i++;             j++;             if (j == p.length())// 匹配成功。                 return i - j;         } else {             // 匹配失败，j回退，跳过模式串P前面相同的字符继续比较。             j = next[j];         }     }     return -1; } private void getNext(String p, int next[]) {     int length = p.length();     int i = 0;     int j = -1;     next[0] = -1;// 默认值。     // 最后一个字符不需要比较。     while (i < length - 1) {         // 如果j为-1或者p[i]==p[j]，i和j都往后移一步。         if (j == -1 || p.charAt(i) == p.charAt(j)) {             i++;             j++;             // j是字符p[i]前面和最开始字符相同的数量。             next[i] = j;         } else {             j = next[j];// 回退，KMP的核心代码。         }     } }

KMP优化

我们来看下表，当模式串在下标为 4 的位置匹配失败的时候，下一步 j 会回退到下标为 1 的位置，但这两个位置的字符是一样的，既然一样，拿过来比较也是不会成功，所以如果字符一样，我们可以优化一下，往前查找相同的子串。

下标 0 1 2 3 4 5 6 模式串 a b c a b e a next[i] -1 0 0 0 1 2 0

来看下代码：

private void getNext(String p, int next[]) {     int length = p.length();     int i = 0;     int j = -1;     next[0] = -1;// 默认值。     // 最后一个字符不需要比较。     while (i < length - 1) {         // 如果j为-1或者p[i]==p[j]，i和j都往后移一步。         if (j == -1 || p.charAt(i) == p.charAt(j)) {             i++;             j++;             // 这里要注意，i和j都已经执行了自增操作。             if (p.charAt(i) == p.charAt(j))                 next[i] = next[j];             else                 next[i] = j;         } else {             j = next[j];// 回退，KMP的核心代码。         }     } }

如果前面查找的还是相同的，我们该怎么办呢？是不是需要写个递归，继续往前找？实际上是不需要的，比如模式串 "aaaaaaaaaab" ，如果没优化它是这样的（图片可点击放大）。