c++ - C++ 两个数组元素搜索

Question

我遇到了一个问题。

我如何检查一个数组是否在一个序列中有两个或多个元素。

例如，假设我有一个数组

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

我想检查它是否有数字 6,7,8 但按那个顺序。

例如，如果它是

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

它会返回假。

我知道使用一个元素很容易，只需创建一个 for 循环，但我不知道如何搜索两个或更多数组，以及我希望它们的顺序。

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();
}