CC = gcc

FLAG = -o

all: naive_search rabin_karp_search boyer_moore_search

naive_search : naive_search.c

$(CC)$(FLAG) naive_search naive_search.c

rabin_karp_search : rabin_karp_search

$(CC)$(FLAG) rabin_karp_search rabin_karp_search.c

boyer_moore_search: boyer_moore_search boyer_moore_search.c

$(CC)$(FLAG) boyer_moore_search boyer_moore_search.c

clean:

rm naive_search rabin_karp_search boyer_moore_search

#defineNUM_OF_CHARS 256

intmax(inta,intb) {return (a>b)?a:b;}

voidcomputeArray(char*pattern,intsize,intarr[NUM_OF_CHARS])

{

inti;

for(i=0;i<NUM_OF_CHARS;i++)

arr[i]=-1;

for(i=0;i<size;i++)

arr[(int)pattern[i]]=i;

}

voidboyer_moore_search(char*str,char*pattern)

{

intn=strlen(str);

intm=strlen(pattern);

intshift=0;

intarr[NUM_OF_CHARS];

computeArray(pattern,m,arr);

while(shift <= (n-m))

{

intj=m-1;

while (j >=0&&pattern[j]==str[shift+j])

j--;

if (j<0)

{

printf("--Pattern is found at: %d\n",shift);

shift+= (shift+m<n) ?m-arr[str[shift+m]] :1;

}else {

shift+=max(1,j-arr[str[shift+j]]);

}

}

}

intmain()

{

charstr[]="AABCAB12AFAABCABFFEGABCAB";

charpat1[]="ABCAB";

charpat2[]="FFF";/* not found */

charpat3[]="CAB";

printf("String test: %s\n",str);

printf("Test1: search pattern %s\n",pat1);

boyer_moore_search(str,pat1);

printf("Test2: search pattern %s\n",pat2);

boyer_moore_search(str,pat2);

printf("Test3: search pattern %s\n",pat3);

boyer_moore_search(str,pat3);

return0;

}