刚拿极越的offer能去吗？

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

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

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

它 就是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。当使用 KMP 算法的时候，如果某个字符匹配失败，主串指针不回退，而模式串指针不一定回到 它 的第一个字符，如下图所示。

当字符 e 和 d 匹配失败之后，主串指针不回退，模式串指针指向字符 c ，然后在继续判断。主串指针不回退好操作，但模式串指针怎么确定是回到字符 c ，而不是其他位置呢？这是因为在字符 e 匹配失败后，字符 e 前面有 2 个字符 ab 和最开始的 2 个字符 ab 相同，所以我们可以跳过前 2 个字符。也就是说模式串匹配某一个字符失败的时候，如果这个失败的字符前面有 m 个字符和最开始的 m 个字符相同，那么下次比较的时候就可以跳过模式串的前 m 个字符，如下图所示。

我们看到字符 e 前面有 ab 和最开始的字符 ab 相同，长度是 2 。在看第 2 个 a 前面没有（不包含自己）和最开始字符有相同的，所以是 0 。在任何模式串的第 2 个字符前面都没有和最开始字符有相同的，因为前面的是不包含第一个字符，所以 next[1]=0 。如果第 2 个没有，那么第 1 个就更没有了，为了区分，可以让 next[0]=-1 ，当然等于 0 也可以，需要特殊处理下即可。我们先来看下 next 数组怎么求。

使用两个指针 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 为止，我们拿个真实的字符串看下，如下图所示。

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         // 如果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 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 的位置，但这两个位置的字符是一样的，既然一样，拿过来比较也是不会成功，所以如果字符一样，我们可以优化一下，往前查找相同的子串。