A motif conserved across many species is almost certainly functional — purifying selection is
what preserved it. Finding the longest substring shared by a whole collection of sequences is
therefore a direct route to conserved regulatory elements and protein domains, and it's the
standard motivating example for suffix-structure algorithms.
Statement
Given a collection of DNA strings, find the longest substring that appears in every one of
them.
The first line holds n, the number of sequences; the next n lines hold the sequences.
Print the longest shared substring on one line. If several share the maximum length, print the
lexicographically smallest one, so the answer is unique. If the only shared substring is
empty, print an empty line.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
n
line 1
|
int |
How many sequences follow
2 <= n <= 10
|
sequences
line 2
|
list[str] |
The DNA sequences, one per line
each 1 <= length <= 200, uppercase A, C, G, T only
|
These variables are already read for you in the starter code on the right.
Output
str the longest substring common to all sequences; ties broken lexicographically
Sample Cases
3
GATTACA
TAGACCA
ATACA
AC2
ACGTACGT
ACGTACGT
ACGTACGTSubmit 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
2 <= n <= 10- Each sequence is between 1 and 200 characters
- Among equally-long answers, the lexicographically smallest is required
Further Reading
- The answer can be no longer than the shortest sequence, which bounds the search.
- Binary-search the length, or enumerate every substring of the shortest sequence from longest
to shortest and stop at the first one present in all others.