題組內容

5. KMP algorithm is a rapid method to perform pattern matching operation. First, we need to define a failure function for a pattern. The following definition is used to determine the failure function:

b. Suppose that the lengths of the string and pattern are m and n. Give the time complexity of performing the KMP algorithm to accomplish a pattern matching. (10%)