Java 的 String 类是如何查找某个给定的子串的呢？它使用了 KMP 算法吗？

前言

2022 年 4 月 7 日的力扣每日一题是「旋转字符串」，题目描述如下：

给定两个字符串：s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true。 s 的 旋转操作 就是将 s 最左边的字符移动到最右边。  例如：若 s = 'abcde'，在旋转一次之后结果就是 'bcdea'。

这是一道简单题，运用到的知识是字符串匹配。我使用了暴力匹配的方法，执行时间竟然超过了 100% 的提交。正在纳闷，看了 官方题解 ，它更是了得：直接调用了 String 类的 contains 方法。

我注意到，官方题解中提到该解法使用了 KMP 算法 ，因此时间复杂度为 O(n)。我的暴力算法的时间复杂度是 O(n2)，超过了 100%，官方题解使用 KMP 算法，也是超过了 100%，这让我有些疑惑。或许是因为测试用例数据量不够大，区分不出效率吧。不管怎么说，我仍然对 contains 方法的实现细节产生了好奇，于是有了本文。

一探究竟

String 类的 contains 方法其实是一个 驱动方法，它层层依赖于 indexOf 方法。下面是它的完整调用链：

// 0
public boolean contains(CharSequence s) {
    return indexOf(s.toString()) > -1;
}

// 1
public int indexOf(String str) {
    return indexOf(str, 0);
}

// 2
public int indexOf(String str, int fromIndex) {
    return indexOf(    value, 0,     value.length, 
                   str.value, 0, str.value.length, fromIndex);
}

// 3
static int indexOf(char[] source, int sourceOffset, int sourceCount,
                   char[] target, int targetOffset, int targetCount,
                                                    int fromIndex) {
    ...
}

可以看出，方法 3 是最关键的。为了简化方法，我们不妨把每一步调用的参数（0 和 length）都带进去，并忽略前面的预处理操作。这样一来，方法 3 就可以精简为：

static int indexOf(char[] source, int sourceCount, char[] target, int targetCount) {
    /* 待匹配的首个字符 */
    char first = target[0];
    /* 需要匹配的字符数 */
    int max = sourceCount - targetCount;

    /* 遍历 source，匹配 target */
    for (int i = 0; i <= max; i++) {
        /* 在 source 中寻找 target 的首字符 */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        /* 找到了 target 的首字符，继续匹配 target 的剩余字符 */
        if (i <= max) {
            /* 从下一个字符开始匹配 */
            int j = i + 1;
            /* 还需要 targetCount - 1 个字符 */
            int end = j + targetCount - 1;
            /* 一旦某个字符匹配失败，则跳出循环 */
            for (int k = 1; j < end && source[j] == target[k]; j++, k++);

            /* 匹配到了 target 中的所有字符 */
            if (j == end) {
                /* 返回首个匹配的位置 */
                return i;
            }
            /* 否则说明只是部分匹配，继续流程，重新在 source 中寻找 target 的首个字符 */
        }
    }
    /* 直到遍历完 source，都没有匹配到 target，此时返回 -1，表示 target 不是 source 的子串 */
    return -1;
}

疑惑不解

这个 indexOf 方法和我自己实现的匹配算法几乎是一样的，这真的是 KMP 算法吗？

我很怀疑。我依稀记得 KMP 算法是需要一个 next 数组的。

恍然大悟

回过头去看官方题解，它的原话是：

时间复杂度：O(n)，其中 n 是字符串 s 的长度。KMP 算法搜索子字符串的时间复杂度为 O(n)，其他搜索子字符串的方法会略有差异。

我明白了，它的意思是，最优秀的字符串匹配算法是 KMP，它的时间复杂度是 O(n)。

由于我们完全可以用 KMP 算法来实现，因此估算时间复杂度时默认采用了最优的算法。

并不等于说，它的参考代码显式/隐式地使用了 KMP 算法……

这么一来，我的暴力解法也能够超过 100% 就可以理解了。想必是因为这是道简单题，考察的重点不是字符串匹配，而是如何模拟字符串「旋转」操作吧。

后语

感觉这篇文章的起承转合有些营销号的味道？好吧，我也觉得……但是这确实就是我的探索过程（说明我太菜了）。

最主要的目的当然是分享一下 String 类的 contains 和 indexOf 源码啦，希望自己和读者都能有些收获吧。

本文使用 CC BY-SA 4.0 国际协议 进行许可，欢迎 遵照协议规定 转载。
作者：六开箱
链接：https://lkxed.github.io/posts/java-string-search/