[up for grabs]Two-way string searching

[monarch_dodra]

On Monday, 17 June 2013 at 17:13:49 UTC, Dmitry Olshansky wrote:
> And this is all nice and have its place too but I'm mostly 
> talking about O(N*M) vs O(N).

Well... putting it that way always looks nice on paper, but for 
what values of N and M is it actually *faster* ?

Also, are we talking about *actual* O(N), or average case O(N) ? 
Because the link has a worst case scenario of O(N*M).

Actual O(N) comes with a space tradeof, which also comes with a 
very real allocation cost that doesn't appear in the complexity.