4 ms·

O(m*n) is not the same as O(n^2).

• rimantas 12y ago
  It's the same when m=n.
  • waps 12y ago
    Of course in string search it never is. In m=n case KMP would simply compare the first character, and if it doesn't match declare nothing was found. Yes there'd be much more different instructions involved but I think KMP would start beating naive pretty quickly in the m=n case.
  • deleted 12y ago
    [deleted]
• xyzzyz 12y ago
  Yes, but if something is O(m*n) and m <= n (which is the case in string search), then it's also O(n^2). On the other hand, since m can be of the order of, say, n/2, it's not too confusing to say that naive string search is O(n^2), since it's actually Theta(n^2).
  • alayne 12y ago
    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.