Describe using pseudocode the Boyer$-$Moore string pattern matching

algorithm.

$(12$ marks$)$

b$)$ Compute the prefix function $($partial matching table$)$ for the pattern

abababca. This is related to Knuth$-$Morris$-$Pratt string matching

algorithm.

$(8$ marks$)$

c$)$ Based on your knowledge on the Knuth$-$Morris$-$Pratt string matching

algorithm explain how the Rabin$-$Karp algorithm improves the Na$$ve

Pattern$-$matching algorithm.

$(5$ marks$)$