This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: What algorithm used for searching substring
- From: Tim Shen <timshen91 at gmail dot com>
- To: Habibutsu <habibutsu at gmail dot com>
- Cc: "libstdc++" <libstdc++ at gcc dot gnu dot org>
- Date: Wed, 9 Oct 2013 13:24:59 -0400
- Subject: Re: What algorithm used for searching substring
- Authentication-results: sourceware.org; auth=none
- References: <525589B3 dot 8020103 at gmail dot com>
On Wed, Oct 9, 2013 at 12:52 PM, Habibutsu <habibutsu@gmail.com> wrote:
> When i use "std::string::find" it's mean that in actually will be used
> "std::search" or will be used more effective algorithm (for example
> Knuth–Morris–Pratt)
I think std::basic_string::find use brute force here
http://gcc.gnu.org/viewcvs/gcc/trunk/libstdc++-v3/include/bits/basic_string.tcc?revision=195701&view=markup
IMHO, please notice that worst cases for brute force algorithm *may*
be uncommon in daily use, while the brute force probablly wins KMP in
it's best case, which *may* be common in daily use.
--
Tim Shen