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