Topic: String Matching

$[$Total: $25$ marks$]$

a$)$ Using the na$$ve string matching algorithm, how many character comparisons does NaiveStringMatch perform until all occurrences of pattern $P$ are found in $T?$

$T=$ kbkbkbkmkbkb

$P=kbkbm$

$[5$ marks$]$

b$)$ Given the Pattern $P=kbkbm,$ build an FSA that recognizes all occurrences of $P$ in a given string.

$[5$ marks$]$

c$)$ Provide a pattern and a string that represent the best$-$case scenario for the KMP algorithm, $($i$.$e$.,$ the algorithm runs in the fastest possible way for such a problem$).$

$[5$ marks$]$

d$)$ Provide a pattern and a string that represent the worst$-$case scenario for the KMP algorithm, $($i$.$e$.,$ the algorithm runs in the slowest possible way for such a problem$).$

marks$]$

e$)$ How many spurious hits does the Rabin$-$Karp string matching algorithm encounter in the text $T="3141512653849792"$ when looking for all occurrences of the pattern $P="26",$ working modulo $q=11$ and over the alphabet $=\{0,1,2,$dots,$9\}?$

$[5$ marks$]$