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

Re: strstr


From: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>
Date: Fri, 31 Mar 2006 10:11:29 -0800 (PST)

:
: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.

					-Matt
					Matthew Dillon 
					<dillon@xxxxxxxxxxxxx>



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