Question $6$

Not yet answered Marked out of $8\mathrm{.}00$

Given a string of $n$ characters called the text and a string of $kk.$ characters called the pattern $($where $kn).$ The following Brute Force algorithm returns the index of the first character in the text that starts a matching substring or $-1$ if the search is unsuccessful $($assuming the start index is $1)$

$(8$ marks$)$

ALGORITHM BF$-$SM $(T[1$dotsn$],P[1$dotsk$])$

$//$ Input: An array $1$dots..$n$ of $n$ characters representing a text

An array $P[1$dotsk$]$ of $k$ characters representing a pattern

$//$ Output: The index of the first character in the text that starts a matching substring or $-1$ if the search is unsuccessful

for $i=1ton-k+1do$

$j=1$

while $jk$ and $P[j]=T[i+j-1]$

a$)(3$ marks$)$ What is the best$-$case scenario for the given BF$-$SM algorithm when searching for a pattern within a text? provide an example to illustrate this?

b$)(2$ marks$)$ What is the time complexity of the algorithm in its best$-$case scenario? $($explain and use Big$-$O notation$)$

c$)(3$ marks$)$ What is the time complexity of the algorithm when the length of the pattern $($k$)$ equals the length of the text $($n$)$ in the best$-$case scenario? $($Explain why$)$