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