Straightforward Boyer-Moore is worst case O(nm), but (I believe) there are modifications that make it linear time. There are other string searching algorithms like Knuth-Morris-Pratt which are linear in the size of the two inputs. My point was that non-naive string searching algorithms absolutely do matter, and that no amount of cache-efficiency is going to save an implementation from hitting the quadratic behaviour intrinsic to a naive algorithm.