Re: [boost] Does this algorithm exist?

From: Chris Jefferson (caj_at_[hidden])
Date: 2005-03-24 10:43:22

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Michael Goldshteyn wrote:
| Given:
|
| typedef std::deque<char> DequeString;
| std::string s("Hello sweet world!");
| std::string word("sweet");
| DequeString dequeString;
|
| // Copy "Hello sweet world!" into the deque string
| std::copy(s.begin(),s.end(),std::back_inserter(dequeString));
|
| // Now, I want to find where "sweet" appears in the dequeString. An
iterator
| to its location would be fine.
|
| // This doesn't quite do it, since it looks for _any_ occurrence of a
| character from word in dequeString
|
std::find_first_of(dequeString.begin(),dequeString.end(),word.begin(),word.end());
|
| // But, I want to find where _the whole_ word occurs in dequeString,
similar
| to how std::string::find() does it:
| std::string::size_type wordPos=s.find(word);
|
| Is there something in boost or the standard C++ lib that can be used?
|

std::search sounds like what you are looking for :) Note that most
implementations don't specialise search for characters or anything, an
in general it's impossible to get any better than O((n-m)m) where n is
the length of the string you are looking in, and m is the length of the
string you are looking for... a more specialised algorithm that just
looked for strings in strings could do better than that..

Chris
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)

iD8DBQFCQuAa3FpDzErifpIRArdiAJsFJyS1N5H3l0SBjkBDleTEvnlypACgmX70
xBLOexamYHtjUAG9BMhk6is=
=mTYV
-----END PGP SIGNATURE-----