Fastest String Search Algorithm.

[Amit Choudhary]

On Fri, Jun 11, 2021, 5:15 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:

>
>
> > I searched for the needle in the haystack using document editor's search
> > and found that needle was located in the beginning.
>
> No, it's always located at the end - it is even tested explicitly.
>


For some cases it is in the beginning and for some cases it is in the end.



> > The worst case scenario of my algorithm is O(mn) where m is the length of
> > the text and n is the length of the pattern.
>
> Exactly. And that is problematic if both m and n are large.
>
> > And this worst case scenario will be hit in only one case:
>
> There is not just one worst-case, the number is practically infinite.
> A typical worst case is AAAAAAAAAAAAAAA with needle AAAAAAABA.
>


I can easily fix this by recording at which index it failed the last time.
Then the first comparison will be at the index of B. And after first m
comparisons, it will fail in the first comparison itself at index of B.

So, after this fix, my algo's worst case scenario will be O(n).

"""""But, I would really appreciate if you can give me a real world
scenario where this worst case scenario will happen."""""



> > But my theory is this: We should be fastest 100% if the time. If that is
> not possible,
> > then we should try to get as close to 100% as possible.
> >
> > This means that if for average case, some algorithm is faster 99% of the
> time but
> > slower 1% of the time in the worst case scenario then we should go for
> this
> > algorithm rather than fretting over worst case scenario.
>
> For large needles and haystacks the worst case becomes more important
> because
> the slowdown becomes larger with the length. It's bad even if there is a
> 0.001%
> chance that your computer locks up for minutes.
>


The worst case scenario almost never occurs in real world situations. The
worst case scenario is almost always on paper.

Please give me an example of how would you encounter worst case sceraio in
real world.

Regards,
Amit