Re: divide & conquer algorithm to implement string matching

A generalized version of the above code :

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

#define SEQUENCE "0110"

int count_sequence(char const arr[], int arrlen,
char const pattern[], int patternlen);

int main(int argc,char **argv)
{
char arr[] = "01101011000110101100";
//char arr[] = "01101101";
printf("number of sequences found = %d\n",
count_sequence(arr, strlen(arr),
SEQUENCE, strlen(SEQUENCE)));
return 0;
}

void static cnt_seq_rec(char const arr[], int start, int end,
int arrlen, char const pattern[], int patternlen,
int *cnt, int *visited)
{
int slice = end - start;
if (slice > patternlen) {
int mid = (start + end) / 2;
cnt_seq_rec(arr, start, mid, arrlen,
pattern, patternlen, cnt, visited);
cnt_seq_rec(arr, mid + 1, end, arrlen,
pattern, patternlen, cnt, visited);
} else {
if (((start + (patternlen - 1)) >= arrlen) ||
visited[start])
return;
printf("sequence[%d] = ", start);
for(int i = 0; i < patternlen; ++i)
printf("%c", arr[start + i]);
printf("\n");
if (!strncmp(pattern, &arr[start], patternlen))
(*cnt)++;
visited[start] = 1;
}
}

int count_sequence(char const arr[], int arrlen,
char const pattern[], int patternlen)
{
int cnt = 0;
int fake_arrlen = arrlen + 2;
int *visited = (int *)malloc(sizeof(int) * arrlen);
for (int i = 0; i < arrlen; ++i)
visited[i] = 0;
for(int i = 0; i < patternlen; ++i)
cnt_seq_rec(arr, i, fake_arrlen + i, arrlen,
pattern, patternlen, &cnt, visited);
free(visited);
return cnt;
}

-----------------------------------------------------------------------


.

Relevant Pages