Sliding window 2 X99827

Recall that a string (genomic sequence) can be split in words of length 3 (codons) by sliding a window of size 3 over the string, with a step size of 3. More in general, a string can be split in overlapping words of length $x$ and overlap size $x-y$ by sliding a window of size $x$ and step size $y$ over the string. For example, sliding a window of size 3 and step size 2 over the string TATAAT gives the overlapping words TAT and TAA.

Write code for the sliding window problem. The program must implement and use the SLIDING-WINDOW function in the pseudocode discussed in class, which is recursive and is not allowed to perform input/output operations. Make one submission with Python code and another submission with C++ code.

Input

The input is a string $s$ (a genomic sequence) over the alphabet $\Sigma=\{A,C,G,T\}$, an integer $x$ (the window size), and an integer $y$ (the step size).

Output

The output is all substrings of $s$ of size $x$ starting at positions $1,1+y,1+2y,\ldots$

Hint

Notice that there are no “partial” substrings of $s$ (of size smaller than $x$) in the output.