RE: Fastest String Search Algorithm.

["Guo, Wangyang" <wangyang.guo@intel.com>]

I have tried to convert Amit's algorithm in C and benchmark with bench-strstr.
The result shows no advantage compared to existing implementations.

BR
Wangyang

-----Original Message-----
From: H.J. Lu <hjl.tools@gmail.com> 
Sent: Sunday, June 6, 2021 10:30 PM
To: Amit Choudhary <amitchoudhary0523@gmail.com>; Guo, Wangyang <wangyang.guo@intel.com>
Cc: GNU C Library <libc-alpha@sourceware.org>
Subject: Re: Fastest String Search Algorithm.

On Sun, Jun 6, 2021 at 7:15 AM Amit Choudhary via Libc-alpha <libc-alpha@sourceware.org> wrote:
>
> Hi All,
>
> I have invented the fastest string search algorithm. It is called 
> "Choudhary Algorithm". I am sharing it here, in case glibc wants to 
> include it in for strstr().

We have been trying to improve strstr in glibc:

https://gitlab.com/x86-glibc/glibc/-/merge_requests/46

But we couldn't find a solution which is fast for all cases.
Wangyang, please work
with Amit to improve strstr in glibc.

> I have compared my algorithm my other standard algorithms and below 
> are the results.
>
> You can view the results and source code of the algorithm and 
> text/pattern
> here: 
> https://sourceforge.net/projects/fastest-string-search-algo/files/
>
> The search text is around 60 KB long and the pattern is 27 bytes.
>
> Result:
> ---------
>
> Pattern found at index 30384
>
> Time taken by Brute Force algorithm = 57,151,900 ns.
> Time taken by Boyer Moore algorithm = 25,012,100 ns.
> Time taken by Rabin Karp algorithm = 613,410,200 ns.
> Time taken by Knuth Morris Pratt Force algorithm = 58,461,200 ns.
> Time taken by Choudhary algorithm = 17,413,000 ns. (Fastest).
>
> Choudhary string search algorithm is the fastest.
>
> ----------------------------------------------------------------------
> ---------
>
> Regards,
> Amit

Thanks.

--
H.J.