Let yⁱ denote the concatenation of string?y?with itself?i?times. For example,?(ab)³ =?ababab. We say that a string?x????^* has?repetition factor?r?if?x?=?y^r for some string?y????^* and some?r > 0. Let??(x)?denote the largest?r?such that?x?has repetition factor?r.

a.?Give an efficient algorithm that takes as input a pattern?P [1. . m]?and computes the value??(P_i)?for?i?=?1, 2, . . . ,m. What is the running time of your algorithm?

b.?For any pattern?P [1. .m], let??^*(P)?be defined as max_1???I???m ?(P_i). Prove that if the pattern?P?is chosen randomly from the set of all binary strings of length?m, then the expected value of??^*(P)?is?O(1).

c.?Argue that the following string-matching algorithm correctly finds all occurrences of pattern?P?in a text?T[1. . n]?in time?O(?(P)n?+?m):

REPETITION-MATCHER?(P, T)

This algorithm is due to Galil and Seiferas. By extending these ideas greatly, they obtained a linear-time string-matching algorithm that uses only O(1) storage beyond what is required for P and T.

Transcribed Image Text:

P.length n = T.length 3 k = 1+ p*(P) 4 q = 0 5 s = 0 6 while s < n – m 1 m = 2 п if T[s + q + 1] == P[q + 1] q = q + 1 if q == m print “Pattern occurs with shift" s if q == m or T[s + q + 1] # P[q + 1] s = s + max(1, [q/k]) q = 0 7 8 9 %3D 10 11 12 13