libs/algorithm/example/search_example.cpp

   1 /*
   2    Copyright (c) Marshall Clow 2010-2012.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7     For more information, see http://www.boost.org
   8 */
   9
  10 #include <string>
  11 #include <iostream>     //  for cout, etc.
  12
  13 #include <boost/algorithm/searching/boyer_moore.hpp>
  14 #include <boost/algorithm/searching/boyer_moore_horspool.hpp>
  15 #include <boost/algorithm/searching/knuth_morris_pratt.hpp>
  16
  17 namespace ba = boost::algorithm;
  18
  19 const std::string haystack ( "ABACAB is it everywhere!" );
  20 const std::string needle1  ( "ACAB" );
  21 const std::string needle2  ( "not ABA" );
  22
  23
  24
  25 int main ( int /*argc*/, char * /*argv*/ [] ) {
  26 //  In search.hpp, there are generic implementations of three classic sequence search
  27 //  algorithms. They all have the same (dual) interface.
  28
  29 //  There is a procedural interface, based on std::search:
  30     if ( ba::boyer_moore_search ( haystack.begin (), haystack.end (), needle1.begin (), needle1.end ()) != std::make_pair(haystack.end(), haystack.end()))
  31         std::cout << "Found '" << needle1 << "'  in '" << haystack << "' (boyer-moore 1)" << std::endl;
  32     else
  33         std::cout << "Did NOT find '" << needle1 << "'  in '" << haystack << "' (boyer-moore 1)" << std::endl;
  34
  35 //  If you plan on searching for the same pattern in several different data sets,
  36 //  you can create a search object and use that over and over again - amortizing the setup
  37 //  costs across several searches
  38     ba::boyer_moore<std::string::const_iterator> search1 ( needle1.begin (), needle1.end ());
  39     if ( search1 ( haystack.begin (), haystack.end ()) != std::make_pair(haystack.end(), haystack.end()))
  40         std::cout << "Found '" << needle1 << "'  in '" << haystack << "' (boyer-moore 2)" << std::endl;
  41     else
  42         std::cout << "Did NOT find '" << needle1 << "'  in '" << haystack << "' (boyer-moore 2)" << std::endl;
  43
  44 //  There is also an implementation of boyer-moore-horspool searching
  45     if ( ba::boyer_moore_horspool_search ( haystack.begin (), haystack.end (), needle1.begin (), needle1.end ()) != std::make_pair(haystack.end(), haystack.end()))
  46         std::cout << "Found '" << needle1 << "'  in '" << haystack << "' (boyer-moore-horspool)" << std::endl;
  47     else
  48         std::cout << "Did NOT find '" << needle1 << "'  in '" << haystack << "' (boyer-moore-horspool)" << std::endl;
  49
  50 //  And also the knuth-pratt-morris search algorithm
  51     if ( ba::knuth_morris_pratt_search ( haystack.begin (), haystack.end (), needle1.begin (), needle1.end ()) != std::make_pair(haystack.end(), haystack.end()))
  52         std::cout << "Found '" << needle1 << "'  in '" << haystack << "' (knuth_morris_pratt)" << std::endl;
  53     else
  54         std::cout << "Did NOT find '" << needle1 << "'  in '" << haystack << "' (knuth_morris_pratt)" << std::endl;
  55
  56     return 0;
  57     }