Q2:

You are given a text T of length n and a pattern P of length p. We say that two occurrences x and y are non-overlapping if |y-x|≥ p. Design an O(n + p) time algorithm to report a maximal set of non-overlapping occurrences of P in T.

For example, say T = aabaabaabacdeaabaabac and P = aaba, then the occurrences of P in T are {0,3, 6, 13, 16}. We have to report the largest sized subset of the occurrences such that no two occurrences in the subset overlap. Notice that the occurrences 0 and 3 (also, 3 and 6, and 13 and 16) overlap. So, we have to report either {0,6, 13} or {0,6, 16).

Hint: Use KMP first. Then you need to do "something" greedily.