pattern matching code - little help needed

[Yoon Soo]

Hi, there

in the code below I am not sure, if the two 'big' for-loops are
redundabt in some way. Could this be made also in one loop and would
this make sense?

Another question is,if I should implement the maps as bitmaps. (Pro &
Contra..on a very first sight, it looked to me, as if the implemention
as bitmap would be some more work).

thx in advance

yoon


-----------code------------------

/* based on algorithm from Baeza-Yates and Gomet */
/* returns bitmap in form of 0001000100
* where 1 are starting points of found matchings */

unsigned char *scan(char *text_ptr,char *pat_ptr,unsigned int
text_len,unsigned int pat_len) {

register unsigned int i,j;
unsigned char *bmap_ptr;
unsigned char *foundmap_ptr,*tmp;

bmap_ptr = (unsigned char *)malloc(text_len*pat_len+pat_len);
foundmap_ptr = (unsigned char *)malloc(text_len);
memset(foundmap_ptr,0,text_len);
memset(bmap_ptr,0,text_len*pat_len+pat_len);
tmp = (unsigned char *)malloc(text_len);
memset(tmp,0,text_len);

for (i=0;i<pat_len;i++)
for (j=0;j<text_len;j++) {
if (*(pat_ptr+i) == *(text_ptr+j))
*(bmap_ptr+(j*pat_len+i+1)) = 1;
else
*(bmap_ptr+(j*pat_len+i+1)) = 0;
*(foundmap_ptr+j) = *(bmap_ptr+j*pat_len+1);
}
for (i=1;i<pat_len;i++) {
for (j=i;j<text_len;j++)
*(tmp+j) = *(foundmap_ptr+j-1) & *(bmap_ptr+(j*pat_len+i+1));
for (j=0;j<text_len;j++) {
*(foundmap_ptr+j) = *(tmp+j);
*(tmp+j) = 0;
}
}
for (i=0;i<text_len-pat_len+1;i++)
*(tmp+i) = *(foundmap_ptr+i+pat_len-1);

free(bmap_ptr);
free(foundmap_ptr);
return tmp;
}

int main(void)
{
char *text = "Testing Text to test if Test could be found.Test";
char *pattern = "Test";
unsigned int text_len,pattern_len;
unsigned char *found_map;
int i;

text_len = strlen(text);
pattern_len = strlen(pattern);
found_map = scan(text,pattern,text_len,pattern_len);
for (i=0;i<text_len;i++)
if (*(found_map+i) == 1)
printf("pattern found at : %d\n",i);
return 0;
}