We represent an array of length , whose elements are alphabet characters. We call a pattern. An element of can be accessed by , where is an index. denotes a contiguous subarray of starting from index to inclusively, where . denotes the -character prefix of , while is the empty string and . The prefix function for a pattern returns an array of length , such that each element with an index is computed by
where denotes that is a suffix of . That is, is the length of the longest prefix of that is also a proper suffix of . Note that a proper suffix cannot be the whole string.
(1) Compute the results of the prefix function for the pattern aabaacaabaa.
(2) Algorithm 1 is a pseudo-code of an algorithm for computing the results of the prefix function for a pattern . Fill the blanks (a), (b), and (c).
Algorithm 1 COMPUTE-PREFIX-FUNCTION()
let be a new array for keeping the results of the prefix function
for to dowhile and doend whileifthenend ifend forreturn
We represent an array of length and an array of length . The elements of both and are alphabet characters. We call a text and a pattern. We say that a pattern occurs with a shift in a text if and (that is, if , for ). The string-matching problem is the problem of finding all shifts with which a given pattern occurs in a given text .
(3) Algorithm 2 is a pseudo-code of an algorithm for the string-matching problem utilizing the results of the prefix function computed with Algorithm 1. Fill the blanks (d), (e), and (f).
Algorithm 2 STRING-MATCHING()
for to dowhile and doend whileifthenend ififthen print "Pattern occurs with shift" end ifend for
(4) Show the time complexity of Algorithm 2 with reasons.