[PATCH] improve string find algorithm

[Jakub Jelinek]

On Fri, Jan 06, 2017 at 03:34:22PM +0000, Jonathan Wakely wrote:
> > The description of Two-Way algorithm is in
> > http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
> > Boyer-Moore in
> > http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
> 
> And in std::boyer_moore_searcher in <functional> :-)
> We also have std::boyer_moore_horspool_searcher in <functional>.
> 
> We could try allocating memory in std::string::find() and fall back to
> the dumb algorithm if it fails, but we don't want to throw bad_alloc.

glibc memmem algorithm doesn't allocate any memory for short needles (< 32
chars) and for longer needles uses size_t shift_table[1U << CHAR_BIT];
automatic array (i.e. 1KB on 32-bits, 2KB on 64-bits).

	Jakub