What is the cost / complexity of a String.indexOf() function call?
See Question&Answers more detail:osWhat is the cost / complexity of a String.indexOf() function call?
See Question&Answers more detail:osIIRC 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.