| 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 ( corpus_first: haystack.begin (), corpus_last: haystack.end (), pat_first: needle1.begin (), pat_last: needle1.end ()) != std::make_pair(x: haystack.end(), y: 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(x: haystack.end(), y: 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 ( corpus_first: haystack.begin (), corpus_last: haystack.end (), pat_first: needle1.begin (), pat_last: needle1.end ()) != std::make_pair(x: haystack.end(), y: 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 ( corpus_first: haystack.begin (), corpus_last: haystack.end (), pat_first: needle1.begin (), pat_last: needle1.end ()) != std::make_pair(x: haystack.end(), y: 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 | } |
|---|
| 58 | |
|---|
