Re: divide & conquer algorithm to implement string matching

This is the code I've come up with,but if you look at what it
prints,you can see that it misses the sequences at posistions 10 and
15.

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

int count_sequence(char arr[], int arrlen);

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

#define SEQUENCE "0110"

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

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

.

Relevant Pages

  • Re: Calling Stored Proc from a Function
    ... DECLARE @rc AS INT, @seqid AS INT; ... UPDATE sequences ... > need to do an update statement, I have to use a stored proc as you can ...
    (microsoft.public.sqlserver.programming)
  • Re: [PATCH] console UTF-8 fixes
    ... * malformed UTF sequences represented as sequences of replacement glyphs, ... int first; ...
    (Linux-Kernel)
  • Re: Sequence matching exercise
    ... > The program should monitor a possibly infinite stream of characters ... > DO NOT detect sequences within sequences. ... int main ...
    (comp.lang.c)
  • Re: Help! mem leak in c extension.
    ... working as expected as I only aligned 2 sequences and printed the ... signed int x, xmax, y, ymax, itemscore, best, i, t; ... existing object to hold the objc elements of the array ... the reference counts of the elements in objc since the list ...
    (comp.lang.tcl)
  • Re: Sequence matching exercise
    ... >> The program should monitor a possibly infinite stream of characters ... >> DO NOT detect sequences within sequences. ... > int main ...
    (comp.lang.c)