= Solution
Sort <string suffix> starting positions, then examine only adjacent entries:
``
def longestRepeated(): (Int, Int, Int) = {
require(N >= 2)
val suffixes = (0 until N).toArray.sortWith(before)
var besti = suffixes(0)
var bestj = suffixes(1)
var bestk = 0
var t = 1
while (t < N) {
val i = suffixes(t - 1)
val j = suffixes(t)
val k = longestFrom(i, j)
if (k > bestk) {
besti = i; bestj = j; bestk = k
}
t += 1
}
(besti, bestj, bestk)
}
``
The <while loop> retains a best triple among adjacent pairs already visited. All <string suffix> starting positions are distinct, and the adjacent-suffix characterization proves that considering these $N-1$ pairs suffices. The two definitions named `longestRepeated` in parts b and e are alternatives, not duplicate members of one <software class>.
Assuming a comparison sort using $O(N\log N)$ comparator calls, sorting takes $O(N\log N(K+1))$ time, because each comparison scans characters. The final pass takes $O(N(K+1))$. Thus \b[overall time is $O(N\log N(K+1))$, at worst $O(N^2\log N)$], with $O(N)$ auxiliary storage for indices and ordinary sorting workspace. Merely storing indices does not make <string suffix> comparisons constant-time; claiming $O(N\log N)$ here would omit their cost. Faster suffix-array constructions require additional machinery beyond this comparator-based solution.
Back to article page
