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

For the third for loop when you're doing the check, you're (1) not actually checking every element of B against the corresponding element of A and (2) not checking the different start indices. What you probably meant to do is something like

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 に答える
1

シーケンスに一致しない場合、リセットjすることはないため、残っていた値から始まるシーケンスの残りを探し始めますj。プログラムはシーケンスを探しますが、B連続している必要はありません。

また、シーケンスがいつ完了したかを確認しないため、たとえばB開始時にインクリメントし続けA、一致する可能性が低い不明なメモリにオーバーフローするため、誤った結果が得られます。これを修正するには、 の全体がいつ見つかったかを確認して、ループを終了します。jB[j]AB

次のように置き換えると、これが修正されます。

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 に答える
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 に答える
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

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

B の要素が A と一致しないことがわかった場合は、A をスピンして、j を 0 に戻す必要があります。

于 2013-08-09T18:11:44.560 に答える