Counting in the transform
A genome is stored not as text but as its Burrows–Wheeler transform. A character $, smaller than all letters, is appended to a text T of the letters A, C, G, T, all cyclic rotations of T$ are sorted alphabetically, and the last letters of the rotations are written out from top to bottom. This is the string L, and you have nothing else.
For each word in a list, count how many times it occurs in T. Occurrences may overlap: in AAAA the word AA occurs three times.
The tests include the genomes of phages λ, HK97, HK022 and φX174, human mitochondria, a million random letters and pieces of a genome repeated many times; among the words are restriction enzyme sites, as in the article.
Input
The first line is L: a string of the letters A, C, G, T and one character $, of length 2 to 106 + 1. The second is the number of words q (1 ≤ q ≤ 105). Then q lines, words of the letters A, C, G, T of length 1 to 100; their total length is at most 4·105.
Output
q numbers, one per line: how many times each word occurs in T.
Examples
Example 1
GC$AAAC 6 A AC CA G T ACAACG
3 2 1 1 0 1
Example 2
T$AAAAA 6 A AA AAA AAAAAA AT TA
5 4 3 0 1 0
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 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
The text can be restored from L in n steps and then each word searched for. But there are up to a hundred thousand words and a text of a million letters: a pass over the text for each word is 1011 operations. You need something that does not depend on the length of the text.
2Hint 2
Rows of the sorted table that begin with the same word stand together. Suppose the range of rows beginning with the tail Q of a word is known. How do you find from it and from L the range of rows beginning with cQ?
3The idea
Backward search from the article. Let C[c] be how many letters of L are smaller than c (L has the same letters as T$), and rankc(i) how many times c occurs in L[0..i). If the rows beginning with Q are [lo, hi), the rows beginning with cQ are [C[c] + rankc(lo), C[c] + rankc(hi)). Start with [0, n) and read the word from its last letter; the length of the final range is the answer. Each row of the table is a cyclic rotation, but since $ occurs once, a row begins with the word exactly when the word occurs in T from that place, so overlapping occurrences are counted too.
4Walkthrough
For the five characters $, A, C, G, T compute rank in advance for all i from 0 to n: five arrays of n + 1 numbers. Then each search step is two array lookups. In Python it is convenient to make a mask “1 where the letter is c” with bytes.translate and accumulate it with itertools.accumulate into an array: the arrays build fast and take 8 bytes per number, not 36 as a list of integers would.
In the first sample L = GC$AAAC and the text is ACAACG: A occurs 3 times, AC 2, CA 1, G 1, T never, and the whole word once.
4+Solution
5Complexity
Preparation is O(n) for each of the five characters, the answers O(total length of the words). Memory is five arrays of n + 1 numbers. If memory is dearer than time, the counters are kept every 64 rows and the rest is counted from L, as in the article.
6Common mistakes
- Restoring the text and searching with find. The restoration is correct and fast, but then each word is found by a pass over a million letters: in test 7 a hundred thousand words do not fit in the time.
- str.count instead of counting overlaps.
"AAAAAA".count("AA")is 3, while there are 5 occurrences. Backward search counts overlaps by itself. - Reading the word from the start. The range extends only to the left: letters must be added from right to left.
- An empty range. When lo ≥ hi, there is no need to go on: the answer is 0.