String.indexof（）函数调用的成本/复杂性是多少？

String.indexof（）函数调用的成本/复杂性是多少？

Answer 1

IIRC Java的.indexOf()实现只是天真的字符串匹配算法 ，它是O(n+m)平均值和O(n*m)最坏情况。

在实践中，这足够快; 我测试了相对较大的针（> 500个字符）和干草堆（几个MB）字符串，它可以在一秒钟内（在普通家用电脑中）进行匹配。 请注意，我强迫它穿过整个大海捞针。

Answer 2

在java中，如果调用是string1.indexOf（string2），则时间成本为O（m-n），其中m是string1的长度，n是string2的长度。

Answer 3

取决于实施。

例如，当在较长的字符串中搜索字符串时，“Turbo Boyer-Moore算法需要额外的恒定空间量才能在2n比较中完成搜索（而不是Boyer-Moore的3n），其中n是数字要搜索的文字中的字符。“ （见维基百科 ）。