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
