Compare every unordered pair of distinct starting positions:
def longestRepeated(): (Int, Int, Int) = {
require(N >= 2)
var besti = 0
var bestj = 1
var bestk = 0
var i = 0
while (i < N - 1) {
var j = i + 1
while (j < N) {
val k = longestFrom(i, j)
if (k > bestk) {
besti = i; bestj = j; bestk = k
}
j += 1
}
i += 1
}
(besti, bestj, bestk)
}After each comparison, the stored triple attains the largest common-prefix length among pairs processed so far; its positions remain distinct. The nested while loops enumerate exactly pairs. Reversing the two positions does not change their common-prefix length, so no omitted ordered pair could improve the answer. Initialization also supplies a valid length-zero answer if no character repeats.
Write for the final maximal length. Each comparison takes time, including a possible first mismatch. Hence time is , at worst , and auxiliary space is . Writing merely would miss the case. The explicit precondition excludes arrays with fewer than two valid starting positions; the requested distinct-position triple has no answer there under this domain convention.
Articles by others on the same topic
There are currently no matching articles.