6

如果标题听起来很奇怪，这里还有另一种解释：

如果我有一个范围a，并且我想计算另一个范围b出现在范围a中的次数，有没有一个std::函数可以做到这一点？

如果没有，是否有一种简单的方法来做到这一点（我可以手动循环使用std::search- 我说的是更优雅的东西）？

4

4 回答 4

3

我认为你需要建立自己的。这是我想到的实现。

template <typename Iterator1, typename Iterator2>
size_t subsequence_count(Iterator1 haystack_begin, Iterator1 haystack_end, Iterator2 needle_begin, Iterator2 needle_end) {
    size_t count = 0;
    while (true) {
        haystack_begin = std::search(haystack_begin, haystack_end, needle_begin, needle_end);
        if (haystack_begin == haystack_end)
            return count;
        count++;
        haystack_begin++;
    }
}

template <typename Iterator1, typename Iterator2, typename BinaryPredicate>
size_t subsequence_count(Iterator1 haystack_begin, Iterator1 haystack_end, Iterator2 needle_begin, Iterator2 needle_end, BinaryPredicate predicate) {
    size_t count = 0;
    while (true) {
        haystack_begin = std::search(haystack_begin, haystack_end, needle_begin, needle_end, predicate);
        if (haystack_begin == haystack_end)
            return count;
        count++;
        haystack_begin++;
    }
}

一些使用这个的代码：

int main() {
    std::vector<int> haystack = {1, 19, 7, 23, 2, 19, 19, 19, 19};
    std::vector<int> needle   = {19, 19};

    assert(subsequence_count(begin(haystack), end(haystack), begin(needle), end(needle) == 3);
}
于 2013-05-09T15:20:55.230 回答
1

您可以在范围 A 上使用std::count_if和在范围 B 上使用 std::find 的 lambda。

编辑：用 std::find 替换了 std::search。

于 2013-05-09T15:18:06.267 回答
1

如果您想比 更有效地执行此操作O(nm)，对于m模式中的字符，n在要搜索的字符串中，您可以考虑使用后缀树。本质上，这意味着您构建了一个专门的树结构，该结构同时描述了字符串的所有可能后缀。因此，如果您的字符串是“ratatat”，那么您的后缀字符串将同时表示“ratatat”、“atatat”、“tatat”、“atat”、“tat”、“at”和“t”。因此，一旦您构建了树，您就可以非常快速地找到（并计算）特定字符串的所有出现。当然，构建它需要一些编程工作和一些内存！

这里有一个很好的描述（这指的是 Skiena 的书The Algorithm Design Manual，这是我读到的关于它们的地方）。

PS 我开始搜索后缀树 C++ 实现。对此有几个有用的stackoverflow问题，但据我所知，std中没有任何内容。

编辑以添加替代算法

再三考虑，我认为Boyer-Moore字符串匹配可能是一个更好的解决方案，尤其是因为有一个现成的boost实现——而你所说的你想要做的就是找到一个特定的搜索字符串（后缀树很好如果要计算不同搜索字符串的出现次数）。本质上，bm 算法所做的是利用搜索字符串中的结构在出现不匹配时向前跳转，使用搜索字符串的预计算表（参见预处理要搜索的字符串的后缀树）。因此，您应该能够使用 boyer-moore boost 搜索（而不是 std 搜索）手动循环并获得显着的效率提升。

于 2013-05-09T15:27:17.483 回答
0

如有疑问，请使用 boost :)

#include <boost/algorithm/string/finder.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/foreach.hpp>

using namespace std;
using namespace boost;
using boost::algorithm::find_all;

int main(int argc, char* argv[])
{
    std::vector<double>  haystack{11.0,22.0,33.0,22.0,33.0,44.0,22.0,33.0,22.0};
    std::vector<double> needle{22.0,33.0};

    std::vector<boost::iterator_range<std::vector<double>::iterator>> out;
    boost::algorithm::find_all(out, haystack, needle);

    cout << "matches=" << out.size() << endl;
    cout << endl;

}

基于作为 find_all 中的错误示例发布的代码 - 在评论中链接到问题。

于 2013-05-13T15:39:06.963 回答