java - Java中.indexOf方法的算法选择

Question

我刚刚查看了 Java String 类的 .indexOf() 方法的实现，代码的作者似乎使用了蛮力算法来找到给定字符串中的子字符串。也就是说，该方法的运行时间复杂度为 O(mn)，其中 m 和 n 分别是源字符串和目标字符串的长度。

为什么作者不使用更高效的算法，如 Rabin-Karp，如果提供良好的哈希函数，其运行时复杂度为 O(m + n)？

我可能遗漏了此实现原因背后的完整知识，因此想了解。

Answer 1

我不确定为什么会做出这个决定，但如果我猜的话，这可能是因为对于小模式字符串(一个非常常见的用例)，天真的暴力算法可能和一些算法一样快，如果不是更快的话渐进更快的算法，如 Rabin-Karp、Boyer-Moore 或 Knuth-Morris-Pratt。这似乎是一种合理的默认算法，因为在许多情况下，您将在小字符串中搜索小模式，强大的匹配设置的开销可能与朴素方法的运行时间相当。

也就是说，Java 规范中没有任何地方强制要求使用这种算法。他们可以很容易地选择 Rabin-Karp 作为默认算法。

他们可能选择这种方法的另一个原因是，如果您想进行快速文本搜索，正则表达式库提供了更快的字符串匹配和更强大的搜索功能。默认情况下为用户提供简单的蛮力算法，并在需要时选择切换到更强大的工具集，这似乎是平衡渐近效率与实际效率的好方法。