A genome's suffixes by digits
To find any fragment of a genome quickly, biologists build a suffix array: write out all suffixes of the genome, the tails starting at each position, and sort them alphabetically. Then all occurrences of a fragment end up together in the array, and binary search finds them. Build the suffix array: print the starts of the suffixes in increasing order of the suffixes.
For the string GATTACA the suffixes in alphabetical order are A, ACA, ATTACA, CA, GATTACA, TACA, TTACA, and their starts are 6, 4, 1, 5, 0, 3, 2. The hidden tests are real genomes from the NCBI database, phage φX174 (5386 letters), human mitochondria (16,569) and phage lambda (48,502), plus strings of one letter and with a short period, where neighbouring suffixes agree on tens of thousands of characters.
Input
One string of length 1 to 50,000 of the capital letters A, C, G, T.
Output
One line: n numbers separated by spaces, the start positions of the suffixes (from zero) in increasing order of the suffixes. A suffix that is a prefix of another is smaller than it.
Examples
Example 1
GATTACA
6 4 1 5 0 3 2
Example 2
GAGTTTTATCGCTTCCATGACGCAGAAGTTAACACTTTCGGATATTTCTGATGAGTCGAA
59 58 30 25 31 19 33 23 53 26 1 41 7 16 50 43 32 22 15 14 56 20 9 38 47 11 34 57 24 18 52 0 40 49 21 10 39 54 27 2 29 6 42 13 55 8 37 46 17 51 48 28 5 12 36 45 4 35 44 3
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 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
Comparing two suffixes directly means reading them until a difference appears. For the string AAAA…A neighbouring suffixes agree almost entirely, and one comparison costs tens of thousands of steps. You need to compare something shorter than characters.
2Hint 2
Suppose the suffixes are already ordered by their first k characters, and each has been given a rank, the number of its group in this order. How can the ranks order the suffixes by their first 2k characters? The first 2k characters of suffix i are its first k characters and the first k characters of suffix i + k.
3Hint 3
The order by 2k characters is the order of the pairs (rank of i, rank of i + k). A pair of two numbers below n is a two-digit number in base n, and radix sort sorts it: two counting passes.
4The idea
This is prefix doubling. Start with ranks by the first character. At each step suffix i gets the pair (rank of i, rank of i + k); if the suffix is shorter, the second rank is taken as smaller than all, since an empty tail comes before any character. Sort the pairs, hand out new ranks (equal pairs, equal rank) and double k. When all ranks are distinct, the order is final; this happens no later than when k reaches n, that is, within ⌈log₂ n⌉ steps.
5Walkthrough
Correctness rests on one observation: strings of length 2k compare as pairs of their halves, first by the first half and on a tie by the second, and the ranks of the halves compare the same way as the halves themselves. So after the step with length k the ranks order the suffixes by their first 2k characters.
The pairs are sorted by radix: first with a stable counting sort by the second rank, then, also stably, by the first. That is how the Go solution works: two passes of n + 1 counters per step. In Python it is handier to fold the pair into one number r1·(n + 2) + r2 and sort with the built-in sort: it is written in C and on 50 thousand integers is faster than counting in Python, although asymptotically it is O(n log n) per step rather than O(n). The first step's ranks are the letters' numbers in the string's sorted alphabet, so that they are smaller than the multiplier.
Doubling was described by Udi Manber and Gene Myers in 1990, in the same work that introduced suffix arrays. There are linear construction algorithms now, but doubling is the easiest to write without mistakes, and for genomes of tens of thousands of letters it is more than enough.
5+Solution
6Complexity
There are at most ⌈log₂ n⌉ + 1 steps, each with a radix sort of pairs, O(n), so O(n log n) in all; with a built-in sort per step, O(n log² n). On random strings and real genomes the ranks become distinct after a few steps: long repeats are rare in them. The worst case is a string of one letter, which needs all the steps. Memory is a few arrays of length n.
7Common mistakes
- Sorting the suffixes themselves. The key
s[i:]copies the tail of the string, and all keys together take n²/2 characters: more than a gigabyte for the phage lambda genome. The solution runs out of memory. - A multiplier smaller than the ranks. If a pair is folded into the number r1·M + r2, the multiplier M must be greater than any second rank. Letter codes (up to 84 for
T) are larger than the length of short strings, which is why the first ranks are taken by the string's alphabet, not by codes. - An empty tail as the largest. A suffix that ran out of characters must come before, not after:
Ais smaller thanAC.