DragonFly BSD
DragonFly kernel List (threaded) for 2006-04
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: strstr


From: joerg@xxxxxxxxxxxxxxxxx
Date: Sat, 1 Apr 2006 19:43:49 +0200
Mail-followup-to: kernel@crater.dragonflybsd.org

On Fri, Mar 31, 2006 at 10:11:29AM -0800, Matthew Dillon wrote:
> 
> :
> :I thought I saw something a while ago about making
> :strstr O(n + m) instead of O(nm). In looking at
> :the source, it still looks O(nm). If they have been
> :fixed, can someone point me to the commit? Is there
> :interest in doing one of the fast string search
> :algorithms like Boyer Moore or KMP?
> :
> :Kyle
> 
>     Well, its really only O(nm) if the first character of the little
>     matches a large number of characters in the big string.  Considering
>     that 99.9% of the use of strstr() either operates on short strings,
>     or operates on strings where that case is not likely, it would be a
>     waste of code to try to make it more sophisticated.

Especially if you keep in mind that almost all the faster algorithms
have a similiar result as regex(3).

Joerg



[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]