Fastest String Search Algorithm.

[Amit Choudhary]

On Fri, Jun 11, 2021 at 6:12 PM Amit Choudhary <amitchoudhary0523@gmail.com>
wrote:

>
> On Fri, Jun 11, 2021, 5:15 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com>
> wrote:
>
>> > 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."""""
>


I fixed this. I am attaching latest fixed and changed version of my program
(bzipped2).

Regards,
Amit
-------------- next part --------------
A non-text attachment was scrubbed...
Name: compare_string_search_algorithms.c.bz2
Type: application/x-bzip
Size: 25562 bytes
Desc: not available
URL: <https://sourceware.org/pipermail/libc-alpha/attachments/20210611/3f0cf881/attachment-0001.bin>