Consider the host string H and a sample pattern string P below. (a) Using the Naive-String-Matcher, the (brute-force) string matching algorithm discussed in class, give all the pairs of characters from the host and pattern strings that are compared when finding the first occurrence of P in H. List the pairs in the order that the comparisons are made and in the form (P[i], H[j]), where/and j are zero-based indices, beginning with (P[0], H[0]). (b) Give 7r(P), the longest-prefix-proper-suffix array of P.] (c) Repeat exercise 3.(a) using the KMP-String-Matcher algorithm discussed in class. (d) Consider the alphabet E = {0, 1} and sigma*, the set of all bit strings. Also, consider the set of all (5, T) pairs, where 5 is a 4-bit substring of a 10-bit string T such that the brute-force string matching algorithm compares the most pairs of bits when finding the first occurrence of S in T. Of all such (S, T) pairs, give an example of 5 and T for which the KMP string matching algorithms compares the fewest pairs of bits when searching for the first occurrence of 5 in T. How many pairs of bits will each algorithm compare