[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAM0U__8Bx0j0RGTpnMFD8KPmbrYSyu4X-LyTRhYODWA3k6ZegQ@mail.gmail.com>
Date: Fri, 16 May 2025 17:59:22 +0100
From: Nuno Cruces <ncruces@...il.com>
To: Rich Felker <dalias@...c.org>
Cc: musl@...ts.openwall.com
Subject: Re: strcasestr("", "") returns NULL
I wasn't suggesting they'd be used, just that they kinda demonstrate the
problem is not absolutely intractable.
In any case, if you're interested, glibc seems to use two-way for
strcasestr, though I'm not sure if it supports every locale.
I haven't looked into the details.
Thanks a lot for musl!
Regards,
Nuno
On Fri, 16 May 2025 at 17:09, Rich Felker <dalias@...c.org> wrote:
> 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
>
Content of type "text/html" skipped
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.
