arrayscsizedimensional

C - 2 arrays, check if one is a sub array and return index


i have a task to write a function that will get 2 arrays and their size:

int contain(int big[], int size_b, int small[], int size_s) 

the program should check if the small array is a sub array of the big array, if true should return the Index number of the first number in the small array, else return -1.

Example: 2 4 61 5 8 5 56 89 3 -2

5 56 89 3 -2

function should return 5.

9 5 12 7 8 -2 4 32 900 13

9 5 12 8 7

function should return -1.


Solution

  • Check the comments to see the explanations

    int contain(int big[], int size_b, int small[], int size_s) {
        int contains, k;
        for(int i = 0; i < size_b; i++){
            // assume that the big array contains the small array
            contains = 1;
            // check if the element at index i in the big array is the same as 
            // the first element in the small array
           if(big[i] == small[0]){
               // if yes, then we start form k = 1, because we already know that
               // the first element in the small array is the same as the element 
               // at index i in the big array
               k = 1;
               // we start to check if the next elements in the big array
               // are the same as the elements in the small array
               // (we start from i+1 position because we already know that the element 
               // at the position i is the same as the first element in the small array)
               for(int j = i + 1; j < size_b; j++){
                   // range for k must be from 1 to size_s-1
                   // if we reached the end of the small array or if the small 
                   // array contains only one element then break the for loop
                   if(k >= size_s - 1) {
                       break;
                   }
                   // if the element at the position j in the big array is different
                   // from the element at the position k in the small array then we
                   // flag that we did not find the sequence we were looking for (contains=0)
                   if(big[j] != small[k]){
                       contains = 0;
                       break;
                   }
                   // increment k because we want the next element in the small array
                   k++;
               }
               // if contains flag is not 0 that means we found the sequence we were looking
               // for and that sequence starts from index i in the big array
               if(contains) {
                   return i;
               }
           }
        }
        // if the sequence we were looking for was not found
        // then -1 is returned
        return -1;
    }
    

    Here is the code without comments

    int contain(int big[], int size_b, int small[], int size_s) {
        int contains, k;
        for(int i = 0; i < size_b; i++){
            contains = 1;
           if(big[i] == small[0]){
               k = 1;
               for(int j = i + 1; j < size_b; j++){
                   if(k >= size_s - 1) {
                       break;
                   }
                   if(big[j] != small[k]){
                       contains = 0;
                       break;
                   }
                   k++;
               }
               if(contains) {
                   return i;
               }
           }
        }
        return -1;
    }