为什么String.indexOf()不使用KMP？

Question

我读了java.lang.String的源代码，我惊讶地发现String.indexof()不使用Knuth-Morris-Pratt算法？如我们所知，KMP更有效。那么为什么String.indexOf()不使用它呢？

我周围的人告诉我，对于短字符串，KMP已经足够好了，但是如果您需要性能，并且打算使用大字符串，那么就不是一个好的选择。但是他没有告诉我细节。

下面是我的问题：

1. 我们为什么不在String.indexOf()中使用KMP呢？
2. 为什么KMP不是一个大字符串的好选择？

Answer 1

KMP在最坏情况下的性能更好，但实际上需要一点预先计算(以生成偏移表)。它还需要一个初始内存分配，这也可能影响性能。

对于(大概)常见的用例--在相对较短的字符串中进行搜索，这实际上可能会比原始实现慢一些。

这与这样一个事实捆绑在一起:对于非常庞大的数据集，您可能会使用比简单的String更专业的数据结构，这意味着增加的实现(可能是运行时)成本不值得投资。

注意，在未来的Java版本中，这可能会发生变化，因为没有指定实际的算法。

Answer 2

KMP和其他几种渐进有效的字符串搜索方法，如Boyer-Moore和Boyer-Moore-Horspool需要额外的内存--对于KMP，O(m)内存，其中m是所搜索子字符串的大小。虽然这通常是可以接受的，但是库设计人员必须做出权衡，这样他们的代码才能在许多不同的情况下执行得很好。主要原因可能是由于KMP所需的预处理，以及在搜索阶段它的内部循环比较复杂，在许多常见情况下，常数因子减速可能使它比朴素O(mn)子字符串搜索慢几倍(例如，在长字符串中搜索<10个字符的子字符串)。此外，当运行库试图为KMP回退函数表分配大型内存缓冲区时，搜索大型子字符串的人可能会感到困惑，因为运行时库将耗尽内存。

也许更好的问题是，为什么主流语言运行库尚未采用O(m+n)-time、O(1)-space算法(如双向算法 )。同样，答案很可能是常见情况下的持续因素放缓。然而，在至少一个C运行时库实现中，对应的strstr()函数已被更新为使用此算法。。

我周围的人告诉我，对于短字符串来说，KMP已经足够好了，但是如果您需要性能并且打算使用大字符串，那么就不是一个好的选择。

从我的理解来看，这是完全相反的，那就是，对于短字符串来说，朴素的O(mn)子字符串搜索足够好(也可能是最好的)，但是随着字符串变得更长，最终会输给渐近更快的O(m+n)算法，比如KMP。