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