Sites on a ring
The DNA of the human mitochondrion and of phage φX174 is closed into a ring. A ring can be written to a file only by cutting it somewhere: databases have agreed on which letter to start from and write the genome from it to the end, and the last letter of the file is actually next to the first. Phage lambda is a linear molecule, but in the cell it closes into the same kind of ring with its sticky ends.
A biologist wants to know how many times each motif occurs on the ring. An occurrence is a position from which m consecutive letters, going round the ring, read as the motif. Occurrences may overlap: in the ring AAAA the motif AA occurs four times. An occurrence may pass through the cut: start at the end of the file and continue from its beginning.
One of the tests is the genome of the human mitochondrion (NC_012920.1), others are phages φX174 and lambda.
Input
The first line holds the ring: a string s over the letters A, C, G, T and N of length n (1 ≤ n ≤ 100,000), as it is written in the file. The second holds the number of motifs q (1 ≤ q ≤ 10). Then come q lines, each with a motif over the same letters of length m, 1 ≤ m ≤ n. The total length of the motifs is at most 100,000.
Output
q lines: for each motif, the number of positions of the ring at which it starts.
Examples
Example 1
GAATTCAGG 3 GAATTC GGGAA A
1 1 3
Example 2
AAAA 2 AA AAA
4 4
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
An occurrence passing through the cut begins in one of the last m − 1 letters of the file. What should be appended to the string to make such occurrences ordinary?
2Hint 2
Append to s its first m − 1 letters. Each start 0 … n − 1 gets its m consecutive letters, and no extra starts appear: positions ≥ n in the new string give no complete occurrence, they lack letters. What remains is to count all occurrences, including overlapping ones.
3Hint 3
How many times does AA occur in the ring AAAA? And what will "AAAAA".count("AA") answer?
4The idea
The ring unfolds into the string t = s + s[0..m − 2] of length n + m − 1. The starts of occurrences in t are exactly the positions 0 … n − 1, and each corresponds to one position of the ring. Search t for all occurrences with KMP: after each one found k becomes π[m − 1], so overlapping occurrences are not lost.
5Walkthrough
For each motif build the prefix function, go through t and count how many times k reached m. Gluing t together is not necessary: you can go through s and then once more through its first m − 1 letters without resetting k, since the KMP search reads the text as a stream.
The case m = n stands apart. A motif as long as the whole ring occurs as many times as the ring has rotations that read as the motif: in ACGACGACG the motif GACGACGAC occurs three times, because the ring maps onto itself on a rotation by three letters. The solution that appends m − 1 letters takes this into account by itself.
5+Solution
6Complexity
Per motif O(n + m): the prefix function in O(m) and a search over n + m − 1 letters. O(q · n + Σm) in all, about a million steps in the worst test. A naive search on a ring of nothing but A with a motif of 50,000 A would make 5·10⁹ comparisons.
7Common mistakes
- Searching without appending. Occurrences through the cut are lost: in the ring AAAA a linear search finds AA three times, not four, and a motif of length n once, even if the ring is symmetric.
- Appending the whole string, not m − 1 letters. In s + s, occurrences lying wholly in the second copy are counted twice.
str.countandstrings.Count. Both functions count occurrences without overlaps: having found an occurrence, they continue searching after its end. In the telomere TTAGGG… they find a two-unit motif half as often as it occurs.