Define Qi(S) as the length of the longest substring that starts at position i and matches a suffix of S starting at some position not equal to i. For example, in the string S = rzbaaaxpdqbaaax, Q3 = 5. Show how to compute all the Q values (that is for all the i) in O(|S|) time. This is not as obvious as it looks. It is not true that you just reverse S and compute the Z values. But if you try that idea and see why it fails, you will probably next see the right idea.