For the following pattern and text:

$\backslash [$

$\backslash$begin$\{$array$\}\{$l$\}$

$\backslash$mathrm$\{$T$\}=\backslash$mathrm$\{$ababzabababaababab$\}\backslash \backslash$

$\backslash$mathrm$\{$P$\}=\backslash$mathrm$\{$ababa$\}$

$\backslash$end$\{$array$\}$

$\backslash ]$

The listing below illustrates how the brute force algorithm matches the pattern to the text. Here, comparisons are made from left to right starting at the first character in the pattern and the capital letter indicates where a mismatch was made and the comparison stops, shifting the pattern over by one.

$```$

T: ababzabababaababab

P: $1$ ababA mismatch at last A$,$

stop, shift P by $1$

$```$

a$)$ Create a prefix table for the pattern for the KMP algorithm.

b$)$ Use the same format as above to show how the KMP algorithm would match the pattern with the text.

c$)$ Create a shift table for the pattern for Horspool's algorithm.

d$)$ Use the same format to show how Horspool's algorithm matches the pattern with the text. You can shift by the amount for the rightmost character after a complete match.