Search code examples
carraysfunctiondefinitionsub-array

How to know how many pattern segments are in the array?


So basically my problem is: I receive an array of ints and an array with an ints pattern to look for. I need to return how many pattern segments are in the 1st array.

For example:

v=[5,  2,  2,  3,  4,  4,  4,  4,  1,  1, 2, 2] 
p=[2, 2]

this needs to return something like "there's 2 segments of p in v."

I've tried this but i don´t think it's the right method:

int main()
{
   int v[] ={5,  2,  2,  3,  4,  4,  4,  4,  1,  1, 2, 2};
   int p[] ={2,2};
   int sizev, sizep;
   printf("%d", count_segments_repeated_ints(v,sizev,p,sizep));
   return 0;
}


int count_segments_repeated_ints(int v[], int sizev, int p[], int sizep){

    int i,j, ocr=0;
    //sizeof
    for(i=0; i < sizev; i++){
        for(j=0; j < sizep; j++){
            if(v[i]==p[j] && v[i+1]==p[j+1]){
                ocr++;
            }
        }
        return ocr;
    }
}


Solution

  • A bit different solution is to just use a single loop and check for equality and increment the j-indexer while numbers match. If the j-indexer becomes greater or equal to sizep then there is a match hence increment ocr. Otherwise start from 0 again.

    int i, j = 0, ocr = 0;
    
    if (sizep > sizev) return 0;
    
    for (i = 0; i < sizev; i++)
    {
      if (v[i] == p[j]) j++;
      else
      {
        if (j > 0) i--;
        j = 0;
      }
    
      if (j >= sizep)
      {
        ocr++;
        j = 0;
        // If overlapping segments are allowed uncomment the following line:
        // i -= sizep - 1;
      }
    }
    
    return ocr;