6

タイトルが奇妙に聞こえる場合は、別の説明を次に示します。

範囲 a があり、別の範囲bが範囲aに何回出現したかをカウントしたい場合、それを行う関数はありますか?std::

いいえの場合、それを行う簡単な方法はありますか（ofcを使用して手動でループできます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

よりも効率的にこれを行いたい場合は、パターン内O(nm)の文字、検索対象の文字列に対して、サフィックス ツリーを検討できます。本質的にこれが意味することは、文字列のすべての可能なサフィックスを同時に記述する特殊なツリー構造を構築することです。したがって、文字列が "ratatat" の場合、サフィックス文字列は "ratatat"、"atatat"、"tatat"、"atat"、"tat"、"at"、および "t" を同時に表します。したがって、ツリーを作成すると、特定の文字列のすべての出現箇所を非常に迅速に見つける (およびカウントする) ことができます。もちろん、ビルドにはプログラミングの労力とメモリが必要です。mn

ここに非常に優れた説明があります(これは、Skiena の本The Algorithm Design Manualを参照しており、私がそれらについて読んだ場所です)。

PS サフィックス ツリーの C++ 実装の検索から始めました。これにはいくつかの便利なスタックオーバーフローの質問がありますが、私が知る限り、std には何もありません。

編集して代替アルゴリズムを追加

よく考えてみると、 Boyer-Moore文字列マッチングがおそらくより良い解決策であると思います。特に、すぐに利用できるboost実装があるためです。そして、あなたがやりたいと言ったのは、特定の検索文字列を見つけることだけです (接尾辞ツリーは良い方法です)。異なる検索文字列の出現回数をカウントしたい場合)。基本的に、bm アルゴリズムが行うことは、検索文字列の構造を利用して、不一致がある場合に先にジャンプし、検索文字列用に事前計算されたテーブルを使用することです (検索する文字列を前処理する接尾辞ツリーを参照)。そのため、Boyer-Moore ブー​​スト検索 (標準検索ではなく) を使用して手動でループし、効率を大幅に向上させることができるはずです。

于 2013-05-09T15:27:17.483 に答える
1

範囲 A でstd::count_ifを使用し、範囲 B で std::find を使用するラムダを使用できます。

編集: std::search を std::find に置き換えました。

于 2013-05-09T15:18:06.267 に答える