The repeat unit
At the ends of human chromosomes the unit TTAGGG repeats thousands of times in a row; in other places of the genome the units CA, CCCCCTCTA and hundreds of others repeat. A sequencer reads DNA in pieces, reads, and a read from such a repeat almost never begins at the start of a unit or ends at its end: GGGTTAGGGTTAGGGTT is a telomere read from the fourth letter of a unit and broken off at the second.
From a read s of length n, find the shortest unit: the smallest p at which each letter of the read repeats the letter p places to the left, that is, s[i] = s[i + p] for all 0 ≤ i < n − p. The unit is the beginning of the read of length p. If at least two full copies of the unit fit in the read (2p ≤ n), the read counts as a repeat. For a read with no repeats p = n.
Among the tests are real repeats of the human mitochondrion and pieces of the genome of phage lambda.
Input
The first line holds the number of reads t (1 ≤ t ≤ 1000). Each of the following t lines holds a read over the letters A, C, G, T and N. The total length of the reads is at most 300,000.
Output
For each read, a line of three parts separated by spaces: the unit length p, the unit itself (the first p letters of the read) and the word repeat if 2p ≤ n, or no if not.
Examples
Example 1
3 GGGTTAGGGTTAGGGTT CACACACA ACGT
6 GGGTTA repeat 2 CA repeat 4 ACGT no
Example 2
2 AAAA ACAACAAC
1 A repeat 3 ACA repeat
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 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 length of a read need not be divisible by the unit length. GGGTTAGGGTTAGGGTT has 17 letters, and the unit is 6. Checking only the divisors of n will not do.
2Hint 2
What does “each letter repeats the one p places to the left” mean? Compare the first n − p letters of the read with the last n − p.
3Hint 3
p is a period exactly when the beginning of length n − p coincides with the end of the same length, that is, when the read has a border of length n − p. The shortest period corresponds to the longest border.
4The idea
The smallest period equals n − π[n − 1], where π is the prefix function of the read. This is the theorem from the article on KMP: the condition s[i] = s[i + p] for all i < n − p literally means that s[0..n − p − 1] = s[p..n − 1].
5Walkthrough
For each read compute the prefix function, take p = n − π[n − 1] and print p, the first p letters and repeat if 2p ≤ n.
Look at the real repeats of the mitochondrion in the third test. The unit CA near position 514 is repeated five times. The unit CCCCCTCTA near position 8272 is repeated twice: this is the very nine-letter repeat one copy of which is missing in some people. But the run CCCCCCCTCCCCC near position 303 with period 8 is not a repeat at all: two copies of the unit CCCCCCCT do not fit in 13 letters. Every string has a period; what makes it a repeat is only that the unit fits at least twice.
5+Solution
6Complexity
The prefix function of a read of length n is O(n), O(Σn) = 300,000 steps in all. Checking all candidates p in a row with a full comparison would cost O(n²): on a read of 300,000 letters, tens of billions of comparisons.
7Common mistakes
- Only divisors of the length. Looking for p at which the read is exactly n/p copies of the unit. A read broken off in the middle of a unit fails such a check, and the telomere comes out “not a repeat” (the first example).
- The longest border instead of the period. π[n − 1] is the length of a border, not of a unit: GGGTTAGGGTTAGGGTT has a border of 11 and a unit of 6.
- The unit “as in the reference”. The unit is printed from the first letter of the read: GGGTTA, not TTAGGG. Rotations of a unit are units of the same repeat too, but the statement asks for the beginning of the read.