How many different pieces
How diverse is a DNA sequence? One way to answer is to count how many different pieces it contains: in ACGT all ten pieces are different, while in AAAA there are only four: A, AA, AAA and AAAA. Repeats lower this number, and the longer and more frequent the repeats, the more so. Biologists call this measure the linguistic complexity of a sequence; it was proposed by Edward Trifonov in 1990.
For each string, find the number of its distinct non-empty substrings, contiguous pieces. Equal pieces in different places count once.
Among the tests are the genome of phage lambda (48,502 letters), human mitochondrial DNA, phage φX174, a telomere made of one repeated unit, and a Fibonacci word.
Input
The first line holds the number of strings t (1 ≤ t ≤ 1000). Each of the next t lines holds a non-empty string of Latin letters. The total length of the strings is at most 100,000.
Output
For each string, the number of its distinct substrings. The answer may not fit in 32 bits.
Examples
Example 1
3 abracadabra ACGT AAAA
54 10 4
Example 2
2 TTAGGGTTAGGG GATTACA
53 25
Limits
- Time · Python
- 7000 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
There are n(n + 1)/2 substrings in all, and putting them all into a set takes memory of order n²: five billion pieces for a hundred thousand letters. Repeats have to be counted without writing out the pieces.
2Hint 2
Every substring is the beginning of some suffix. Sort the suffixes. How many new substrings does the next suffix contribute, if the beginnings it shares with the previous one in sorted order have already been counted?
3The idea
In a suffix array, suffix number j contributes as many new substrings as it has beginnings that the suffixes above it did not have: its length minus lcp[j], its common beginning with the neighbour above. A beginning shared with any suffix above is also shared with the nearest neighbour: in a sorted list the common beginning of two suffixes is no longer than the common beginning of each of them with any suffix standing between them. So the answer is n(n + 1)/2 − Σ lcp[j].
4Walkthrough
A suffix array by doubling, the lcp array by Kasai’s algorithm, one formula. These are the same functions as in the article’s listing.
Look at the answers. The lambda genome has 1,175,898,383 distinct pieces out of 1,176,246,253 possible: it has almost no repeats, and only 0.03% is missing. A telomere of a hundred thousand letters has slightly fewer than six hundred thousand distinct pieces: each piece is determined by its length and its offset within the unit. A hundred thousand letters A have exactly a hundred thousand.
4+Solution
5Complexity
Doubling is O(n log n), Kasai O(n). Comparing neighbours from the first letter is O(n) on ordinary DNA, but on a telomere each neighbour coincides with the previous one almost entirely, and that is about n²/2 comparisons.
6Common mistakes
- Naive lcp. The sum of the common beginnings of neighbours, computed by comparing from scratch, is quadratic on repeats. Kasai starts each comparison from h − 1, where h is the common beginning of the suffix preceding it in the text.
- 32 bits. Already for lambda the answer exceeds a billion, and in the ninth test it is more than four billion.
- A set of substrings. Works on short strings and eats memory on long ones.