Java 中 String.contains() 的 Big-O 是什么？

What is the Big-O of String.contains() in Java?

提问by Jason

I'm working on a project, and need to optimize the running time. Is String.contains()runtime the same as TreeSet.contains(), which is O(logN)?

我正在做一个项目，需要优化运行时间。是String.contains()运行一样TreeSet.contains()，这是O（logN）的？

The reason I'm asking is I'm building a TreeMap<String, TreeSet<Song>>, where Songs contain a String of lyrics. Depending on the efficiency, I am considering including a Set of the lyric words inside the Song and running searches on that rather than the String.

我问的原因是我正在构建一个TreeMap<String, TreeSet<Song>>，其中 Songs 包含一串歌词。根据效率，我正在考虑在 Song 中包含一组歌词，并对其进行搜索而不是 String。

采纳答案by Mark Byers

One of the best known algorithms is the Boyer-Moorestring searching algorithm which is O(n) although it can give sublinear performance in the best case.

最著名的算法之一是Boyer-Moore字符串搜索算法，它是 O(n)，尽管它可以在最佳情况下提供次线性性能。

Which algorithm is used in Java depends on which implemetation you download. It seems that for example OpenJDK uses a naive algorithm that runs in O(nm) and linear performance in the best case. See lines 1770-1806 here.

Java 中使用哪种算法取决于您下载的实现。例如，似乎 OpenJDK 使用了一种在 O(nm) 中运行且在最佳情况下具有线性性能的朴素算法。请参阅此处的第 1770-1806 行。

回答by dty

You could also try using a Trie instead of a TreeMap (although Java has no built-in Trie implementation)

您也可以尝试使用 Trie 而不是 TreeMap （尽管 Java 没有内置的 Trie 实现）

回答by Nishant Thapliyal

.contains()definitely uses naive approach and equivalent to O(nm)time complexity.

.contains()绝对使用天真的方法，相当于O(nm)时间复杂度。

• Boyer-mooretakes O(nm)time in the worst case.
• KMPtakes O(n)time in the worst case.

• Boyer-mooreO(nm)在最坏的情况下需要时间。
• KMPO(n)在最坏的情况下需要时间。

In one of the problems related to pattern matching, I used .contains()and it took 70 mswhereas replacing that line with patternSearch() //KMP searchreduced the time to 14 ms.

在与模式匹配相关的问题之一中，我使用.contains()并花费了将时间70 ms替换patternSearch() //KMP search为14 ms.

Java source code | KMP search vs .contains()

Java源代码| KMP 搜索与 .contains()