Real binding sites are degenerate: a transcription factor tolerates a mismatch or two, so exact
matching misses most genuine occurrences. Approximate matching with a mismatch budget is
therefore what motif finders actually do, and it's the reason a naive exact search under-reports
regulatory elements.
Statement
Given a DNA string s, a motif t, and a non-negative integer d, find every position where t
occurs in s with at most d mismatches. Occurrences may overlap.
The three values arrive on three separate lines.
Print all starting positions using 1-based numbering, separated by single spaces, in
increasing order, on one line. If there are none, 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, uppercase A, C, G, T only
|
t
line 2
|
str |
The motif to search for
1 <= len(t) <= len(s)
|
d
line 3
|
int |
The maximum number of mismatches allowed
0 <= d <= len(t)
|
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
GATATATGCATATACTTATA
ATAT
1
2 4 10 12 16ACGT
ACGT
0
1Submit 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) <= 10000 <= d <= length(t)- With
d = 0this reduces to exact matching - Occurrences may overlap
Further Reading
- Reuse your Hamming distance routine on each window
s[i:i+len(t)]. - You can stop counting mismatches for a window as soon as the count exceeds
d.