Q3:

You are given a string X of length n and another string Y of length m ≤ n. Say, the indexes P1, P2, P3, P4 and q1, q2, q3, q4 form two sub-sequences, i.e., 0 ≤ p1 < P2 <P3 < P4 <n and 0 ≤ q1 < q2 < q3< q4 < n; then, they are non-overlapping if p4 < q1.

The task is to count the maximum number of non-overlapping sub-sequences of X that are the same as Y. Thus, if X = GAXTYAWBGTAUGBTABGRGTAXB and Y = GTAB, then the answer is 3 as shown by the red fonts. We cannot select the underlined GTAB as it overlaps with a red GTAE (i.e., among overlapping sub-sequences, you can select only one of them).

Describe an O(m+n) time algorithm to obtain the count. Write a pseudo-code.