Yes, you are right of course. I really just meant that "in practice" the growth of the string length (m) varies independently and common cases behave more like

Yes, you are right of course. I really just meant that "in practice" the growth of the string length (m) varies independently and common cases behave more like O(n) than O(n^2). Also that naive search is probably heavily optimized with SSE assembly instructions and cache tuned. I have implemented several of these algorithms in C and it is difficult to impossible to beat C's strstr consistently with a simple implementation, even on cases that start to make the naive algorithm really inefficient. You'd most likely need a hybrid approach to make a good general purpose string search function that is effective across many domains.