[up for grabs]Two-way string searching

[Dmitry Olshansky]

17-Jun-2013 22:02, 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).

I'm sure I'm reading it right:
- preprocessing phase in O(m) time and constant space complexity;
- constant space complexity for the preprocessing phase;
- searching phase in O(n) time;
- performs 2n-m text character comparisons in the worst case.



-- 
Dmitry Olshansky