leetcode 题目：28. 实现 strStr()

上文 [一文说透] KMP 字符串匹配算法 中的 next 还有优化空间。

next 数组的失配状态转移图

观察上图可以发现，模式串在第 6 位失配时，需要跳转到第 1 位，但是 pattern[6] == pattern[1]，因此第 1 位肯定也会失配。

这样就做了无用功。

通过 [一文说透] KMP 字符串匹配算法 的讲解我们知道——next[j] = k 表示模式串在第 j 位和文本串失配后，模式串指针应该跳转到第 k 位。

文本串指针保持不变的情况下，如果 pattern[j] == pattern[k]，模式串在第 j 位失配，那么模式串在第 k 位也会失配。

于是我们可以改进计算 next[] 的方法，完整代码如下所示：

    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];

        next[0] = -1;
        int k = -1;
        for (int j = 1; j < pattern.length(); ++ j) {
            // 循环计算
            // 结果(1) 为 k = -1
            // 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
            while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
                k = next[k];
            }

            // -1 ++ 后等于 0
            // 所以 next[1] 也可以合并到循环中处理
            k ++;

            // 如果 pattern[j] == pattern[k]
            // 那么第 j 位失配的话，第 k 位也会失配
            if (pattern.charAt(j) == pattern.charAt(k)) {
                // 所以让 next[j] = next[k]
                // 从而直接跳过第 k 位的匹配
                next[j] = next[k];
            } else {
                next[j] = k;
            }
        }
        return next;
    }

输出为：

A  B  A B C  A B  A B D 
-1 0 -1 0 2 -1 0 -1 0 4 

next 数组 2.0 的失配状态转移图

参考

• KMP算法还不懂？next数组不会求？本文一键帮你搞定这些疑难杂症
• 第四章 KMP 串的模式匹配算法