Finding a Motif in DNA

Intermediate Bioinformatics Motif Substring Pattern Matching

Significance:

Locating a short pattern inside a long sequence is the operation behind finding transcription
factor binding sites, restriction sites and primer landing spots. Note that motif occurrences may
overlap — a detail that trips up naive implementations and matters biologically, because
overlapping binding sites really do compete.

Statement

Given two DNA strings s and t, find every location where t occurs as a substring of s.
Occurrences may overlap.

Print all starting positions using 1-based numbering, separated by single spaces, in
increasing order, on one line. If t never occurs, print an empty line.

Input — read from standard input

Variable	Type	Description
`s` line 1	str	The sequence to search in 1 <= len(s) <= 1000
`t` line 2	str	The motif to search for 1 <= len(t) <= len(s)

These variables are already read for you in the starter code on the right.

Output

str space-separated 1-based start positions in increasing order, on one line

Sample Cases

Sample 1

Input

GATATATGCATATACTT
ATAT

Expected Output

2 4 10

ATAT starts at positions 2, 4 and 10 — note that 2 and 4 overlap.

Sample 2

Input

AAAAA
AA

Expected Output

1 2 3 4

Four overlapping occurrences in a run of five A's.

Submit also runs your code against 4 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints

1 <= length(t) <= length(s) <= 1000
Uppercase A, C, G, T only
Occurrences may overlap, so advance one position at a time