如何知道数组中有多少个模式段？

Question

所以基本上我的问题是：我收到一个整数数组和一个具有要查找的整数模式的数组。我需要 return 第一个数组中有多少个模式段。

例如：

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

这需要 return 类似 "there's 2 segments of p in 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

首先，你需要在sizev - sizep之前停止外层循环，这样你就不会在v数组之外访问。

其次，您的内部循环正在为每个匹配字符递增 ocr。如果 all 个字符匹配，它应该只增加它。你只需要比较 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;

}

Answer 2

有点不同的解决方案是只使用一个循环并检查相等性并在数字匹配时递增 j-indexer。如果 j-indexer 变得大于或等于 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 3

对于初学者，您程序中的变量 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;
}

程序输出为

如何知道数组中有多少个模式段？

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

c

arrays

function

definition

sub-array