This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: fnmatch has exponential running time
- From: "James Youngman" <jay at gnu dot org>
- To: "Bruno Haible" <bruno at clisp dot org>
- Cc: libc-alpha at sourceware dot org, bug-gnulib at gnu dot org
- Date: Fri, 23 Mar 2007 09:28:47 +0000
- Subject: Re: fnmatch has exponential running time
- References: <200703222121.37936.bruno@clisp.org>
On 3/22/07, Bruno Haible <bruno@clisp.org> wrote:
fnmatch() has a worst-case complexity O(m*n) where m is the size of the
pattern and n is the size of the sample string. Unfortunately glibc has
chosen an implementation with exponential running time.
Yes. Oddly, per some testng I did about a year ago, "find -regex" is
much faster than "find -name". The former uses the Gnulib regex
support and the latter uses fnmatch().
James.