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 do
while and do
end while
ifthen
end if
end for
return
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 do
while and do
end while
ifthen
end if
ifthen
print "Pattern occurs with shift"
end if
end for
(4) Show the time complexity of Algorithm 2 with reasons.