Finding an array as a substring into another array

3
votes

I would like to know if I can find an array {67,55,65} into another array {23,45,67,55,65,66,76,78}. I am not interested to find individual elements of array, but the array as a whole. I tried some code

#include <iostream>
#include <algorithm>
#include <array>

int main()
{
    std::array<int,8> in = {23,45,67,55,65,66,76,78};
    std::array<int,3> sstr = {67,55,65};
   auto it = std::search(in.begin(), in.end(),
                   std::make_boyer_moore_searcher(
                       sstr.begin(), sstr.end()));
    if(it != in.end())
        std::cout << "The string " << sstr << " found at offset "
                  << it - in.begin() << '\n';
    else
        std::cout << "The string " << sstr << " not found\n";
}

Edit: The reason to go with make_boyer_moore_searcher is the size of my array, roughly calculating, may be some 10 million. I want an efficient search technique.

I am not sure if my code is supposed to work. I got many errors

bm.cpp:12:20: error: ‘make_boyer_moore_searcher’ is not a member of ‘std’ std::make_boyer_moore_searcher( ^ bm.cpp:15:19: error: cannot bind ‘std::basic_ostream’ lvalue to ‘std::basic_ostream&&’ std::cout << "The string " << re << " found at offset " ^ In file included from /usr/include/c++/4.8/iostream:39:0, from bm.cpp:1: /usr/include/c++/4.8/ostream:602:5: error: initializing argument 1 of ‘std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&&, const _Tp&) [with _CharT = char; _Traits = std::char_traits; _Tp = std::array]’ operator<<(basic_ostream<_CharT, _Traits>&& __os, const _Tp& __x) ^ bm.cpp:18:19: error: cannot bind ‘std::basic_ostream’ lvalue to ‘std::basic_ostream&&’ std::cout << "The string " << re << " not found\n"; ^ In file included from /usr/include/c++/4.8/iostream:39:0, from bm.cpp:1: /usr/include/c++/4.8/ostream:602:5: error: initializing argument 1 of ‘std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&&, const _Tp&) [with _CharT = char; _Traits = std::char_traits; _Tp = std::array]’ operator<<(basic_ostream<_CharT, _Traits>&& __os, const _Tp& __x) ^

2
c++arrayssearch
Have you looked at the reference page of that function? – Bob__
@Bob__ Thanks for your comment. I had a look at the function and there is an example of string match. I am not sure if that works for an array match. May be i am missing something. – AwaitedOne
You should include the right headers and those function belong to std::experimental not std::. Besides you should implement operator<< for array<int> or use a loop to print out the values ;) – Bob__
@JonathanMee. I can't afford slow search, as my array in which i am searching is too large and i am sure make_boyer_moore_searcher is very fast. I am not sure what logic search use. – AwaitedOne
@AwaitedOne Have you benchmarked the default method used by std::search? It's only recommended to use specialisations if a need is proven. Also, your proposed alternative is experimental only and thus is not guaranteed to exist in all implementations, which has been proven below for yours. – underscore_d

2 Answers

4
votes

If you want to use make_boyer_moore_searcher you should include the right headers, as explained in the reference page:

#include <experimental/algorithm>
#include <experimental/functional>

Then, as those not belongs to std, you should call them using:

auto it =   std::experimental::search(in.begin(), in.end(),
                 std::experimental::make_boyer_moore_searcher(
                   sstr.begin(), sstr.end()));

In your code, also you are trying to use operator<< to print out an std::array of int (which you call string). You can overload it or use a loop instead:

for ( int i : sstr ) {
     std::cout << i << ' ';
}

With your data you should obtain:

The string 67 55 65  found at offset 2
3
votes

Remove make_boyer_moore_searcher and use just std::search. Test it

#include <iostream>
#include <algorithm>
#include <array>

int main()
{
    std::array<int,8> in = {23,45,67,55,65,66,76,78};
    std::array<int,3> sstr = {67,55,65};
   auto it = std::search(in.begin(), in.end(), sstr.begin(), sstr.end());
    if(it != in.end())
        std::cout << "The string found at offset "
                  << it - in.begin() << '\n';
    else
        std::cout << "The string not found\n";
}

Edit:

In response to the comment, it is also possible to search a 2d array. In std::search elements are compared using operator==. So in this case you can make it work by changing the code to:

std::array<std::array<int, 3>, 4> in {{ {1,2,3}, {4,5,6}, {7,8,9}, {10,11,12} }};
std::array<std::array<int,3>, 1> sstr = {10,11,12};
...

Test it