[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20250516160920.GJ1827@brightrain.aerifal.cx>
Date: Fri, 16 May 2025 12:09:20 -0400
From: Rich Felker <dalias@...c.org>
To: Nuno Cruces <ncruces@...il.com>
Cc: musl@...ts.openwall.com
Subject: Re: strcasestr("", "") returns NULL
On Fri, May 16, 2025 at 05:02:25PM +0100, Nuno Cruces wrote:
> I don't know about it not allowing optimization.
>
> The C/POSIX local does, as you wrote. And regular expression engines kinda
> prove it's at least possible not to be quadratic on the length of the
> haystack (although they spend a lot more effort preprocessing the needle).
Regular expression isn't O(1) in space so not a possible
implementation for strcasestr. And even if you do have a space budget,
the optimizations needed to make it not quadratic-in-time have very
large space tradeoffs. It's not the magic solution fans make it sound
like.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
