What is the cost / complexity of a String.indexof() function call
A:
In java, if the call is string1.indexOf(string2) the time cost would be O(m - n) where m is the length of string1 and n is the length of string2.
MEURSAULT
2010-08-25 04:51:52
+2
A:
IIRC Java's implementation of .indexOf() is just the naive string matching algorithm, which is O(n+m) average and O(n*m) worst case.
In practice this is fast enough; I tested it for relatively large needle (>500 char) and haystack (few MB) strings and it would do the matching in under a second (in an average household computer). Mind you I forced it to go through the whole haystack.
NullUserException
2010-08-25 05:09:14
A:
Depends on the implementation.
For example, when searching for a string within a longer string, "The Turbo Boyer-Moore algorithm takes an additional constant amount of space to complete a search within 2n comparisons (as opposed to 3n for Boyer-Moore), where n is the number of characters in the text to be searched." (see Wikipedia).
jm
2010-08-25 05:09:20