Determining if one array is contained in another

How do I determine if one array is contained (element by element and in order) in another array? I have written the program below in MSVS 2010 but not too sure how to complete the boolean function that determines if one array appears in the other one

void isContained( int ar1[], int ar2[] );


int main( int argc, char** argv )
{
    ifstream fin1( "one.txt" );
    ifstream fin2( "two.txt" );

    int 开发者_高级运维i, j, value1, value2;
    int arr1[ 10 ];
    int arr2[ 10 ];

    for ( i = 0 ; fin1 >> value1 ; i++ )
    {
        arr1[ i ] = value1;
    }

    for ( j = 0 ; fin2 >> value2 ; j++ )
    {
        arr2[ j ] = value2;
    }

    isContained( arr1, arr2 );

    system( "PAUSE" );
}


void isContained( int ar1[], int ar2[] )
{
    ???
}

What you're after is essentially a string searching algorithm (except that in your case your "characters" are the integer elements of your arrays).

There exists a variety of such algorithms, see Wikipedia.

As far as your code so far is concerned:

1. You might want to make sure you don't go past the end of the arrays in your two for loops.
2. You need to pass the sizes of the two arrays to isContained (and its return type probably shouldn't be void).

Simple. Let's say you want to check if ar2 is contained in ar1.

An example:

Ar1: 1 2 3 4 5 6 7 8 9 10 5 2 8 2 4 2 4 6 2 9 1
Ar2: 2 4 6 2

Let's also assume you have the lengths of the arrays in Ar1_len and Ar2_len

You have to go through Ar1, find an element that matches the first element of Ar2 then from there on, try to see if all elements match. If not, you continue on Ar1 to find another element that matches the first element of Ar2

So basically the code would look something like this:

if (Ar2_len == 0)
    return true;
for (unsigned int i = 0; i < Ar1_len-(Ar2_len-1); ++i)
    if (Ar1[i] == Ar2[0])
    {
        bool matches = true;
        for (unsigned int j = 1; j < Ar2_len; ++j)
            if (Ar1[i+j] != Ar2[j])
            {
                matches = false;
                break;
            }
        if (matches)
            return true;
    }

Note that i goes to Ar1_len-(Ar2_len-1) because if you are too far in the end of Ar1 (where there are less than Ar2_len elements are left), it's obviously impossible to find Ar2.

Second note is that this is not the most efficient method. The most efficient method involves building a DFA from Ar2 and using Ar1 as its input and trace it. If it reaches final state you return true. This is probably a bit complicated for you know, but if you are interested, you could look up algorithms in string matching.

Final note is that, the code provided here is not meant for copy-paste. It may lack sufficient error checking and is solely here to give you the idea.

It's not possible with the prototype you gave the function.

Arrays decay to pointers when passed to functions, therefore there is no way the function could determine how many elements are in the arrays.

You can find the position in the containing array that would make mismatch return the end of the contained array:

using namespace std;

template<typename OutIt, typename SeqIt>
OutIt find_sequence( OutIt outer_begin   , OutIt outer_end, 
                     SeqIt sequence_begin, SeqIt sequence_end ){
   assert( 
        distance(outer_begin,outer_end) >= distance(sequence_begin,sequence_end);

   // limit the possible iterator positions:
   OutIt outer_limit = outer_begin;
   advance( outer_limit, distance(sequence_begin, sequence_end) );

   for( OutIt outer_it = outer_begin; outer_it != outer_limit; ++outer_it ) 
   {
     if( mismatch( sequence_begin, sequence_end, outer_it ).first==sequence_end) 
     {
          return outer_it;
     }
   }
   // none found...
   return outer_end;
}

And use it like this:

 int values[]  = { 1,2,3,4,5, 6 };

 int pattern[] = { 3,4,5 };

 int* pFound = find_sequence( values, end(values), pattern, end(pattern) );
 bool bFound = pFound != std::end(values);

You can use the std::search template in <algorithm> to search for a sub-sequence within another sequence. Note: I modified your function signature to pass the array sizes.

bool isContained(int ar1[], int size1, int ar2[], int size2)
{
    return std::search(ar1, ar1 + size1, ar2, ar2 + size2) != (ar1 + size1);
}

This is same as searching a substring in a string. There we are comparing characters, here we will compare numbers or array elements.

KMP1 algorithm is sought for such questions.