What is the cost / complexity of a String.indexOf() function call?
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.
.indexOf()
O(n+m)
O(n*m)
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.
1.4m articles
1.4m replys
5 comments
56.9k users