Menu
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)?
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.
349
. contains() definitely uses naive approach and equivalent to O(nm) time complexity. Boyer-moore takes O(nm) time in the worst case. KMP takes O(n) time in the worst case.
Java String contains() Method The contains() method checks whether a string contains a sequence of characters. Returns true if the characters exist and false if not.
lang. String. contains() method searches the sequence of characters in the given string.
One of the best known algorithms is the Boyer-Moore string searching algorithm which is O(n) although it can give sublinear performance in the best case.
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.
125
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
