c++ - C++ 2 つの配列要素検索

Question

私は問題に遭遇しました。

配列にシーケンス内の 2 つ以上の要素があるかどうかを確認するにはどうすればよいですか?

たとえば、配列があるとしましょう

1,2,3,6,7,8,4,5

番号が6、7、8であるかどうかを確認したいのですが、その順序です。

たとえば、

1,2,3,7,6,8,4,5

false を返します。

forループを作成するだけで、1つの要素で非常に簡単であることはわかっていますが、2つ以上の配列を検索する方法がわかりません。

Answer 1

そのためのアルゴリズムがあります: std::search. それを使用し、気にしないでください (O(n·m) よりも高速な洗練されたものが必要な場合にのみ気にしてください)。

// will be superfluous in C++11
template <typename T, std::size_t N> T *begin(T (&arr)[N]) { return arr; }
template <typename T, std::size_t N> T *end  (T (&arr)[N]) { return &arr[N]; }

int main()
{
  int array[] = {1,2,3,6,7,8,4,5};
  int check[] = {6,7,8};

  int *position = std::search(begin(array), end(array), begin(check), end(check));
  if (position != end(array))
    std::cout << "found at position " << position - array << '\n';
  else
    std::cout << "not found\n";
}

Answer 2

This is should yield O(n):
(edit: but it works correctly only with sequences that don't contain cycles)

bool has_a_sequence(const std::vector<int>& where, const std::vector<int>& seq_no_cycles)
{
    if(!seq_no_cycles.size())
    {
        return false;
    }
    std::vector<int>::const_iterator where_iter;
    std::vector<int>::const_iterator seq_iter = seq_no_cycles.begin();    
    for(where_iter = where.begin(); where_iter != where.end(); where_iter++)
    {
        if(*where_iter == *seq_iter)
        {
            seq_iter++;
            if(seq_iter == seq_no_cycles.end())
            {
                break;
            }
        }
        else
        {
            seq_iter = seq_no_cycles.begin();
            if(*where_iter == *seq_iter)
            {
                seq_iter++;
            }
        }
    }
    return seq_iter == seq_no_cycles.end();
}