A phrase k times
In the third volume of War and Peace, Tolstoy quotes Napoleon’s battle disposition and then takes it apart item by item: this could not be done, and that was not and could not be carried out. Which phrases the author repeats most often is a question for a student of style, and a program should answer it quickly for any k.
Given a text and a number k, find the longest piece of the text that occurs in it at least k times. Occurrences may overlap: in “aaaa” the piece “aa” occurs three times. Spaces and punctuation marks are ordinary characters. If there are several longest pieces, the lexicographically smallest one is needed (characters are compared by their Unicode code points).
Input
The first line holds the number k. The second holds the text in UTF-8 without line breaks, from k to 100,000 characters; 2 ≤ k. Length is counted in characters, not bytes.
Output
On the first line, the length of the piece found; on the second, the piece itself. If no character occurs k times, print 0 and an empty line.
Examples
Example 1
2 abracadabra
4 abra
Example 2
3 abracadabra
1 a
Limits
- Time · Python
- 6000 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
A piece occurs k times, so k suffixes of the text begin with it. Where do these suffixes stand in the suffix array?
2Hint 2
Suffixes with a common beginning stand together in the array. For k consecutive suffixes, numbered j − k + 1 to j, what is their longest common beginning?
3Hint 3
The common beginning of several consecutive suffixes is the minimum of lcp between neighbours within that group: k − 1 numbers. What is needed is the maximum of such minimums over all windows.
4The idea
The answer is the maximum, over windows of k − 1 adjacent lcp values, of the minimum in the window. The minimum of a sliding window is computed with a queue of increasing values: a new value pushes out from the end everything not less than it, and the front of the queue leaves when it drops out of the window. As in the article on the sliding window.
5Walkthrough
The suffix array and lcp as in the article. Then one pass over lcp with a queue: at each step the front of the queue holds the minimum of the last k − 1 values. The best minimum and the suffix where it was reached give the answer. The windows go in the order of the array, so the first window with the largest minimum gives the lexicographically smallest piece.
In the third test, the chapter with the disposition (in the Russian original), at k = 2 the answer is 78 characters: «и перейдет по своим трем мостам, следуя на одной высоте с дивизиями Морана и» (“and will cross by its three bridges, keeping level with the divisions of Morand and”), first in the text of the disposition, then in its analysis. At k = 3, «не было и не могло быть» (“was not and could not be”): that is the chapter’s refrain. In the first part of the novel «, — сказала Анна Павловна, » (“, said Anna Pavlovna, ”) occurs five times.
5+Solution
6Complexity
The array is O(n log n), lcp O(n), the pass with the queue O(n): each index enters the queue and leaves it once. Binary search on the length with hashes is also a workable route, O(n log n), but it requires counting the occurrences of each hash and keeping collisions in mind.
7Common mistakes
- Neighbours only. The largest lcp of two neighbours is the answer for k = 2. For k = 3 in “abracadabra” it gives “abra”, but “abra” occurs only twice; the correct answer is “a”.
- A window of k lcp values. k suffixes have k − 1 gaps between them, not k.
- No overlaps. In a telomere a piece of 94,006 characters occurs a thousand times, shifting by one unit: the occurrences overlap, and that is allowed.
Algorithms behind it
O(n log n)
2 problems
TEC
Technique
Sliding window
A window of width w crawls along the data: the answer is corrected by the entering and leaving element in O(1) instead of O(w).
O(n)
2 problems