我阅读了的源代码，java.lang.String我惊讶地发现String.indexof()不使用Knuth-Morris-Pratt 算法？众所周知，KMP 更有效。那么为什么不使用它String.indexOf()呢？
我周围有人告诉我，对于短字符串，KMP 已经足够了，但是如果您需要性能并且打算使用大字符串，那么它不是一个好的选择。不过他没有告诉我细节。
所以，这是我的问题：
String.indexOf()呢？KMP 具有更好的最坏情况性能，但实际上需要一些前期计算（以生成偏移量表）。它还需要初始内存分配，这也会影响性能。
对于（可能）在相对较短的字符串中搜索的常见用例，这实际上可能比原始实现慢。
这与这样一个事实捆绑在一起，即对于真正庞大的数据集，您可能会使用更专业的数据结构而不是简单的String意味着增加的实现（可能还有运行时）成本不值得投资。
请注意，这可能会在未来的 Java 版本中发生变化，因为未指定实际算法。
KMP 和其他几种渐近高效的字符串搜索方法（如 Boyer-Moore 和 Boyer-Moore-Horspool）需要额外的内存——在 KMP 的情况下，O(m) 内存，其中 m 是要搜索的子字符串的大小。尽管这通常是可以接受的，但库设计者必须做出权衡，以便他们的代码在许多不同情况下都能以可接受的方式运行。可能主要原因是由于 KMP 所需的预处理以及其在搜索阶段更复杂的内循环，在许多常见情况下，常数因子减速可能使其比天真的 O(mn) 子字符串搜索慢几倍（例如，在长字符串中搜索小于 10 个字符的子字符串）。还，
也许更好的问题是，为什么主流语言运行时库还没有采用像双向算法这样的O(m+n) 时间、O(1) 空间算法。同样，答案很可能是常见情况下的恒定因素放缓。尽管如此，在至少一个 C 运行时库实现中，相应的函数已更新为使用该算法。strstr()
我身边的人告诉我，对于短字符串 KMP 已经足够了，但是如果你需要性能并且打算使用大字符串，那么它不是一个好的选择。
嗯，这与我的理解完全相反，即天真的 O(mn) 子字符串搜索对于短字符串来说已经足够好（并且可能是最好的），但最终会输给像 KMP 这样的渐近更快的 O(m+n) 算法随着琴弦变长。