Find masked pattern in 1D array – C source code

F

The following example finds the first occurrence of pattern in a given array and returns the address of that position. Moreover it takes into account a mask, which is helpful for inconsistent pattern formats like : 2,3,X,X,3,1 where X should be ignored. Below you will find the source code and a working sample.

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

////////////////////////////////////////////////////////////////////

typedef struct
{
    int *in_array;        // the input array
    size_t in_array_size; // size of the input array
    int *pattern;         // the pattern array we are looking for
    int *pattern_mask;    // a mask of the pattern
    size_t pattern_size;  // the size of the pattern and mask  (same sizes)
}find_pattern_1d_args_t;

////////////////////////////////////////////////////////////////////

int* find_pattern_1d(find_pattern_1d_args_t* arguments);

////////////////////////////////////////////////////////////////////

int* find_pattern_1d(find_pattern_1d_args_t* arguments)
{
    // make arguments as locals to shrink the names;

    int *in_array		= arguments->in_array;
    int *pattern		= arguments->pattern;
    int *pattern_mask	        = arguments->pattern_mask;
    size_t in_array_size	= arguments->in_array_size;
    size_t pattern_size         = arguments->pattern_size;
	
    if (pattern_size > in_array_size)
	return NULL;

    size_t searchable_area = (in_array_size - pattern_size)+1;
	
    for (size_t i = 0; i < searchable_area; i++)
    {
	int found = 0;	
	for (size_t j = 0; j < pattern_size; j++)
	{
	    found = j;
	    // if (matched) skip the break found afterwards 
	    if (pattern_mask[j] == 0)
		continue;
	    else if (in_array[i+j] == pattern[j])
		continue;
   	    // if not matched break the for
	    found = 0;
	    break;
        }
	if (found != 0)
	    return &in_array[i];
    }
   
    return NULL;
}

////////////////////////////////////////////////////////////////////

int main()
{
    int in_array[] = { 1,1,3,8,6,0,4,6,1,0,0,3,-2,6,0,5,3,7,6,-3,2,8,2,9,4 };
    int pattern[] =    { 6,0,5,3 };
    int mask[] =       { 1,1,0,1 };

    find_pattern_1d_args_t arguments =
    {
	.in_array = in_array,
	.in_array_size = sizeof(in_array)/sizeof(in_array[0]),
	.pattern = pattern,
	.pattern_mask =mask,
	.pattern_size = sizeof(pattern) / sizeof(pattern[0])
    };

    int* result = find_pattern_1d(&arguments);

    printf(result != NULL ? "Found!\n" : "Not Found!\n");
    return 0;
}

Disclaimer: The present content may not be used for training artificial intelligence or machine learning algorithms. All other uses, including search, entertainment, and commercial use, are permitted.

Categories

Tags