Horspool$$s algorithm

$//$Fills the shift table used by Horspool$$s and Boyer$-$Moore algorithms

$//$Input: Pattern P$[0..$m $1]$ and an alphabet of possible characters

$//$ For your assignment the set of characters are the ASCII characters $0-127$

$//$Output: Table$[0..$size $1]$ indexed by the alphabet$$s characters and

$//$ filled with shift sizes computed by formula $(7\mathrm{.}1)$

ShiftTable$($needle $[0..$m $1])$

for i $0$ to size $1$ do Table$[$i$]$m

for j $0$ to m $2$ do Table$[$needle$[$j $]]$m $1$ j

printShiftTable

return Table

$//$Implements Horspool$$s algorithm for string matching

$//$Input: Pattern needle$[0..$m $1]$ and text haystack$[0..$n $1]$

$//$Output: The index of the left end of the first matching substring

$//$ or $1$ if there are no matches

HorspoolMatching$($needle$[0..$m $1],$ haystack$[0..$n $1])$

ShiftTable$($needle$[0..$m $1])//$generate Table of shifts

printf$("\%$s

$",$ haystack$)$;

i $$m $1//$position of the pattern$$s right end

while i n $1$ do

k$0//$number of matched characters

while k m $1$ and needle$[$m $1$ k$]=$ haystack$[$i $$ k$]$ do

k$$k $+1$

if k $=$ m

printf$("\%*$s$\%$s$---$found

$",$ i$-$m$+1,"",$ needle$)$;

return i $$ m $+1//$ Except for your code, do not return. Start looking for the next occurance from here.

else

printf$("\%*$s$\%$s

$",$ i$-$m$+1,"",$ needle$)$;

i $$i $+$ Table$[$haystack$[$i$]]$

printf$("$Matches found at locations:"$)$;

for$($i $=0$; i $$ matchNum; i$++)$

$\{$

printf$("\%$d$",$ matches$[$i$])$;

$\}$

printf$("$

$")$;

return $1$

#define MAX$\_$ALPHABET $128$

#define TABLE$\_$ROW$\_$LENGTH $16$

#define MIN$\_$WRITEABLE $32$

$//$Print out the shift table starting at the first writable character $($space$)$

void printShiftTable$($int table$[])$

$\{$

int i$,$ start;

for$($start $=$ MIN$\_$WRITEABLE; start $$ MAX$\_$ALPHABET; start$+=$TABLE$\_$ROW$\_$LENGTH$)$

$\{$

for$($i $=$ start; i $$ start$+$TABLE$\_$ROW$\_$LENGTH; i$++)$

$\{$

printf$("\%$c$\backslash$t$",$ i$)$;

$\}$

printf$("$

$")$;

for$($i $=$ start; i $$ start$+$TABLE$\_$ROW$\_$LENGTH; i$++)$

$\{$

printf$("\%$d$\backslash$t$",$ table$[$i$])$;

$\}$

printf$("$

$")$;

$\}$

Ouput:

abaabcbabcbabcbabbbabcbaabbcbabcabc

abc

abc

abc$---$found

abc

abc$---$found

abc

abc$---$found

abc

abc

abc

abc

abc$---$found

abc

abc

abc

abc

abc$---$found

abc$---$found

Matches found at locations: $3711192932$