在一个数组中查找另一个数组作为子串

Question

在一个数组中查找另一个数组作为子串

3

我想知道是否可以在另一个数组{23,45,67,55,65,66,76,78}中找到一个数组{67,55,65}。我不想找到数组中的单个元素，而是整个数组。我尝试了一些代码。

#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";
}

编辑: 使用make_boyer_moore_searcher的原因是我的数组大小，大约有1000万个元素。我希望有一个高效的查找技术。

我不确定我的代码是否能够正常工作。我收到了许多错误信息。

bm.cpp:12:20: 错误：‘make_boyer_moore_searcher’不是‘std’的成员 std::make_boyer_moore_searcher( ^ bm.cpp:15:19: 错误：无法将‘std::basic_ostream’绑定到‘std::basic_ostream&&’ std::cout << "The string " << re << " found at offset " ^ 在文件中从/usr/include/c++/4.8/iostream:39:0包括， from bm.cpp:1: /usr/include/c++/4.8/ostream:602:5: 错误：初始化参数1时，‘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: 错误：无法将‘std::basic_ostream’绑定到‘std::basic_ostream&&’ std::cout << "The string " << re << " not found\n"; ^ 在文件中从/usr/include/c++/4.8/iostream:39:0包括， from bm.cpp:1: /usr/include/c++/4.8/ostream:602:5: 错误：初始化参数1时，‘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) ^

- AwaitedOne

2

你看过那个函数的参考页面了吗？ - Bob__

1

你应该包含正确的头文件，这些函数属于 std::experimental 而不是 std::。此外，你应该为 array<int> 实现 operator<< 或使用循环打印出值 ;) - Bob__

1

@JonathanMee。我负担不起慢速搜索，因为我要搜索的数组太大了，而且我相信make_boyer_moore_searcher非常快速。对于search使用的逻辑，我还不确定。 - AwaitedOne

@Bob__ 如果你觉得打出来是正确答案的话，我会点赞的。 - Jonathan Mee

1

@AwaitedOne 你有对 std::search 默认方法进行基准测试吗？只有在证明需要的情况下才建议使用特殊化。此外，你提出的替代方案仅为“实验性”的，因此不能保证存在于所有实现中，这已经在你的方案中得到了证明。 - underscore_d

显示剩余2条评论

2个回答

3

移除make_boyer_moore_searcher函数，直接使用std::search函数。测试链接

#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";
}

编辑:

针对评论的回复，也可以搜索一个二维数组。在std::search中，元素使用operator==进行比较。因此，在这种情况下，您可以通过将代码更改为以下内容使其正常工作:

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

- Dimitri Podborski

它会在二维数组中搜索吗？比如我有std::array<std::array<int, 3>, 4> in { { { {1, 2, 3, 4} }, { {5, 67, 55, 65} }, { {9, 10, 11, 12} } } }; - Agaz Wani

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bob__ · Accepted Answer

如果您想使用make_boyer_moore_searcher，则应包含正确的头文件，如参考页面中所述：

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

那么，对于不属于 std 的内容，您应该使用以下方式调用它们：

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

在你的代码中，你也试图使用operator<<来打印一个int类型的std::array（你称之为字符串）。你可以重载它或者使用循环代替。

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

使用您的数据，您应该获得：

The string 67 55 65  found at offset 2