CODEWITHSUNDEEP
carrays
Mazzy
Mazzy

Reputation: 14219

Input sequence contained in an array

I'm trying to implement this excercise but it doesn't work very well. It should tell me if the sequence in array B is contained in A. Any ideas? I have a problem getting it to work for every sequence.

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

Upvotes: 0

Views: 137

Answers (6)

wildplasser
wildplasser

Reputation: 44250

GCC has the memmem() extention function (which is basically strstr(), but does not rely on NUL-terminated strings)

if (memmem(A, N * sizeof *A, B, M * sizeof *B)) {
   printf("Found\n" );
} else {
   printf("Not Found\n" );
   }

Upvotes: 0

P0W
P0W

Reputation: 47824

For searching B in A you may want to do something like following:

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

Upvotes: 0

Dennis Meng
Dennis Meng

Reputation: 5187

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!");
    }
}

Upvotes: 1

Shivam
Shivam

Reputation: 2132

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;

Upvotes: 0

DrYap
DrYap

Reputation: 6647

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

Upvotes: 1

tallen
tallen

Reputation: 697

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

Upvotes: 0

Related Questions