0

我正在尝试实施此练习，但效果不佳。它应该告诉我数组 B 中的序列是否包含在 A 中。有什么想法吗？我很难让它适用于每个序列。

#include <stdio.h>
#include <stdlib.h>

#define N 6
#define M 3

int contains(int v[], int n);

/*
 * 
 */
int main(int argc, char** argv)
{
    int A[N], B[M];
    int i, j = 0, flag = 0, contained = 1;

    printf("Array A\n");
    for (i = 0; i < N; i++)
    {
        printf("Insert element: ");
        scanf("%d", &A[i]);
    }

    printf("Array B\n");
    for (i = 0; i < M; i++)
    {
        printf("Insert element: ");
        scanf("%d", &B[i]);
    }

    for (i = 0; i < (N - M + 1); i++)
    {
        flag = 0;

        if (A[i] == B[j])
        {
            flag = 1;
            j++;
        }

        if (flag == 0 && (i == N-M))
        {
            contained = 0;
            printf("The sequence B is not contained in A!\n");
            break;
        }
    }

    if (contained == 1)
    {
        printf("The sequence B is contained in A\n");
    }

    return (EXIT_SUCCESS);
}
4

6 回答 6

1

When you have a non match in the sequence, you never reset j so you start looking for the rest of the sequence starting to what ever value j was left at. Your program looks for the sequence B but doesn't require it to be contiguous.

You also don't check for when the sequence is completed so it for example B is at the start of A the j will keep incrementing and B[j] will overflow into unknown memory which is unlikely to match A so will give you an incorrect result. To fix this just check for when the whole of B is found and exit the loop.

Substituting the following will fix this:

if (j == M) break; // Break the loop when B sequence is found
if (flag == 0)
{
    j = 0;    // This was missing
    if (i == N-M)
    {
        contained = 0;
        printf("The sequence B is not contained in A!\n");
        break;
    }
}
于 2013-08-09T18:10:19.530 回答
1

对于第三个for循环，当您进行检查时，您 (1) 实际上并没有B根据相应的元素检查 的每个元素，A并且 (2) 没有检查不同的起始索引。你可能打算做的是

for (i = 0; i < (N - M + 1); i++) {
    for (j = 0; j < M; j++) {
        if (A[i + j] != B[j]) {
            break;
        }
    }
    if (j == M) {
        printf("Found a match!");
    }
}
于 2013-08-09T18:20:13.530 回答
0

as your spinning through A if you find that an element of B does not match A then you need to set j back to 0

于 2013-08-09T18:11:44.560 回答
0

GCC 有 memmem() 扩展函数（基本上是 strstr()，但不依赖 NUL 终止的字符串）

if (memmem(A, N * sizeof *A, B, M * sizeof *B)) {
   printf("Found\n" );
} else {
   printf("Not Found\n" );
   }
于 2013-08-09T18:36:42.613 回答
0 
for (i = 0; i < (N - M + 1); i++)
{
    int j;
    for(j = 0; j < M; j++) 
    {
        if(B[j] != A[j + i])
            break;
    }
    /* sequence found */
    if(j == M)
    {
        return true;
    }
}

return false;
于 2013-08-09T18:19:54.557 回答
0

要在 A 中搜索 B，您可能需要执行以下操作：

for (i = 0; i < (N - M + 1) ; i++)
    if (A[i] == B[0])
    {  j=0;
       while (A[++i] == B[++j] && j<M);
       break;
    }

if (j == M)
{
    printf("The sequence B is contained in A\n");
}

else{
    printf("The sequence B is not contained in A\n");
}
于 2013-08-09T18:17:11.263 回答