i've come across a problem.
How do i check if an array has two,or more elements in a sequence.
For example,let's say i have an array
1,2,3,6,7,8,4,5
and i want to check if it has numbers 6,7,8 but in that sequence.
For example,if it would be
1,2,3,7,6,8,4,5
it would return false.
I know that it's pretty easy with one element,just make a for loop,but i can't figure out how to search for two or more arrays,and in the sequence i want them to be.
There's an algorithm for that: std::search. Use it and don't care (only care if you want have something sophisticated that is faster than 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";
}
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();
}
