Как узнать, сколько сегментов шаблона в массиве?

Question

Итак, в основном моя проблема заключается в следующем: я получаю массив целых чисел и массив с целочисленным шаблоном для поиска. Мне нужно вернуть количество сегментов шаблона в 1-м массиве.

Например:

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

это должно вернуть что-то вроде "есть 2 сегмента p в v."

Я пробовал это, но я не думаю, что это правильный метод:

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

Answer 1

Немного другое решение - просто использовать один цикл, проверять равенство и увеличивать индекс j, пока числа совпадают. Если j -индексор становится больше или равен sizep, то есть совпадение, следовательно, увеличивается ocr. В противном случае начните с 0 снова.

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;

Answer 2

Для стартеров в вашей программе переменные sizev и sizep не инициализированы.

В общем случае sizep может быть больше sizev или даже может быть равно 0 в функции,

Этот цикл из-за вложенного оператора if

    for(j=0; j < sizep; j++){
        if(v[i]==p[j] && v[i+1]==p[j+1]){
            ocr++;
        }

вызывает неопределенное поведение, поскольку значение индекса в этом выражении p[j+1] может указывать вне массива. Более того, массив с шаблоном может содержать больше элементов, чем просто два элемента.

Функция может быть определена следующим образом, как показано в демонстрационной программе. Я переименовал функцию, потому что это имя count_segments_repeated_ints не соответствует назначению.

#include <stdio.h>

size_t count_sub_arrays( const int a1[], size_t n1, const int a2[], size_t n2 )
{
    size_t count = 0;

    if ( !( n1 < n2 ) && n2 != 0 )
    {
        for ( size_t i = 0, n = n1 - n2; i <= n; )
        {
            while ( i <= n && a1[i] != a2[0] ) ++i;

            if ( !( n < i ) )
            {
                size_t j = 1;

                while ( j < n2 && a1[i + j] == a2[j] ) j++;

                if ( j == n2 )
                {
                    ++count;
                    i += n2;
                }
                else
                {
                    ++i;
                }
            }
        }
    }

    return count;
}

int main(void) 
{
   int a1[] = { 5,  2,  2,  3,  4,  4,  4,  4,  1,  1, 2, 2 };
   int a2[] = { 2, 2 }; 
   const size_t N1 = sizeof( a1 ) / sizeof( *a1 );
   const size_t N2 = sizeof( a2 ) / sizeof( *a2 );


   printf( "%zu\n", count_sub_arrays( a1, N1, a2, N2 ) );

   return 0;
}

Вывод программы:

2

Answer 3

Во-первых, вам нужно остановить внешний цикл до sizev - sizep, чтобы вы не обращались за пределы массива v.

Во-вторых, ваш внутренний цикл увеличивает ocr для каждого соответствующего символа,Он должен увеличивать его, только если все символов совпадают. И вам нужно только сравнить v[i+j] с p[j].

В-третьих, return ocr; не должно быть внутри цикла.

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

    int i,j, ocr=0;
    for(i=0; i < sizev-sizep; i++){
        for(j=0; j < sizep; j++){
            int all_match = 1;
            if(v[i+j] != p[j]){
                all_match = 0;
                break;
            }
        }
        ocr += all_match;
    }
    return ocr;

}