Re: string::find complexity.

[Dhruv Matani <dhruvbird at gmx dot net>]

On Fri, 2004-06-11 at 18:04, Paolo Carlini wrote:
> Dhruv Matani wrote:
> 
> >Here are the results for the tests on my system:
> >
> >1. n^2 algo. re-implemented.
> >4. find in terms of std::search -> as suggested by Matt Austern.
> >
> >The numbers for (1) and (4) are the best in most cases. However, (1)
> >does not come out a winner in all cases, whereas (4) seems to be the
> >best for the general case.
> >  
> >
> (4) is definitely the way to go, everything considered.
> 
> >string::size_type
> >s_search(const string& data, const string& src)
> >{
> >  string::const_iterator i = 
> >    std::search(src.begin(), src.end(), 
> >		data.begin(), data.end());
> >  return (i - src.begin());
> >}
> >  
> >
> By the way, this implementation is incorrect, strictly speaking (not 
> that this
> changes considerably your numbers!), since doesn't deal correctly with the
> various corner cases. 

Yes, correct, this does not deal with:
1. Returning npos.
2. Input.size() < search_string.size()
3. Probably more, but you get the general idea.

For that matter, str_find(), which is modifies KMP, can also use some
optimization, and s_find can also use optimization(2).



> Also, actually, we need the overload taking
> (const charT*, size_type, size_type).

Yes, that can also be done.

> 
> Thanks for your numbers! I'm finishing up implementing (4) and will include
> in the patch your performance testcases.

Thanks.

-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html