5. Use the Knuth-Morris-Pratt algorithm to solve the following problem. The Knuth-Morris-Pratt algorithm implements the following in O(m+n) time where n is the length of S and m is the length of P. PRE: S, P are both strings of characters from a given al- phabet set a; POST: Output the index 0 < i < length(S) such that P matches a prefix of the substring in S starting from index i. If there is no such matching of P then output length(S). 2 Given two texts T, T', determine whether one is a cyclic rotation of the other. What is the complexity of your solution? You may assume that the T is cyclic rotation of another string T if T'=Ti, N) T[0, i). Recall that Ti,j) indicates the substring of T that starts at index i and ends at index j-1. Also given two strings S and S' we use SS' to be the string made from concatenating the two strings together. For example arc are car are cyclic rotations of eachother.