Re: [Final testing with benchmark tests] Fastest String Search Algorithm.

[Amit Choudhary <amitchoudhary0523@gmail.com>]

On Sat, Jun 12, 2021 at 1:31 PM Paul Zimmermann <Paul.Zimmermann@inria.fr>
wrote:

>        Dear Amit,
>
> > I ran the benchmark tests for my algorithm and for strstr().
> >
> > Total number of tests = 332.
> >
> > My algorithm is faster 182 times.
> >
> > strstr() is faster 150 times.
>
> and your algorithm can be up to 3531 times slower than strstr():
>
> s: 3.75006e+08                          106175
>
> The largest strstr() time is 1.5e6, whereas the largest time of your
> algorithm is 9.8e8, i.e., 656 times larger.
>
> Can you improve your algorithm so that the worst case time is similar to
> that
> of strstr()?
>
> Paul
>


I don't think my algorithm can be optimized more. Anyways, I had invented
my algorithm thinking about normal average case scenarios and not for worst
case scenarios.

I was talking with Dr. Moore (inventor of Boyer-Moore algorithm) and he
suggested me to demonstrate that my algorithm is better for average case by
doing exhaustive testing across a wide variety of patterns and texts.

He also told me that he had invented his algorithm for average case too and
not thinking much about worst case scenario.

==================What Dr. Moore said========================
If your algorithm is worse case O(mn) then you should
somehow argue (and demonstrate with exhausting testing
across a wide variety of patterns and texts) that its
``average'' behavior is better!  The point is that the
naive algorithm is worst-case O(mn) and why should a
person use yours rather than that simpler algorithm?
==========================================================

Regards,
Amit