Scan the two suffixes until a mismatch or an endpoint:
def longestFrom(i: Int, j: Int): Int = {
require(0 <= i && i <= N && 0 <= j && j <= N)
var k = 0
while (k < N - i && k < N - j && a(i + k) == a(j + k)) {
k += 1
}
k
}The loop invariant is and equality of the two array segments of length . The loop variant is , which decreases whenever the while loop runs. Short-circuit evaluation checks both bounds before indexing. On exit either a string suffix has ended or the next characters differ, so no longer common string prefix is possible. Thus the returned value is the longest common prefix length. Overlap is allowed: the code only reads the array, so the two matching segments need not occupy disjoint storage.
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.
All suffixes beginning with a fixed string form an interval in lexicographic order. To see this, suppose two suffixes start with a string , while a string suffix between them fails to start with . At its first differing character it must be either smaller than both or larger than both; if it ends before does, it is smaller than both. Either possibility contradicts its position between them.
Now take a longest repeated substring . Its two occurrences are prefixes of two distinct suffixes. Every string suffix between them also begins with , so at least one adjacent pair in that interval has a common string prefix of length at least . A greater length would contradict maximality of . Therefore the maximum common-prefix length over adjacent sorted suffixes equals the longest repeated-substring length. If the maximum is zero, any adjacent pair still attains it. The argument does not assume nonoverlapping occurrences.
Original suffix-array example for banana: an interval of suffixes shares the repeated prefix ana
. Details. 
Reuse the verified longest-common-prefix scan, handling equality before scanning:
def before(i: Int, j: Int): Boolean = {
require(0 <= i && i < N && 0 <= j && j < N)
if (i == j) false
else {
val k = longestFrom(i, j)
if (j + k == N) false
else if (i + k == N) true
else a(i + k) < a(j + k)
}
}There is no additional while loop: the helper's loop invariant is that the first
k characters agree and both indices remain in bounds. If the second string suffix ends first, the first cannot precede it; if the first ends first, it is a proper string prefix and precedes the second. Otherwise the first mismatching characters decide lexicographic order. Distinct suffixes cannot both end after the same number of characters, since their lengths differ.The
i == j case ensures a strict comparator, returning false for a string suffix compared with itself, in constant time. For distinct suffixes its running time is , where is the longest repeated-substring length of the full array.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 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 comparator calls, sorting takes time, because each comparison scans characters. The final pass takes . Thus overall time is , at worst , with auxiliary storage for indices and ordinary sorting workspace. Merely storing indices does not make string suffix comparisons constant-time; claiming here would omit their cost. Faster suffix-array constructions require additional machinery beyond this comparator-based solution.
Articles by others on the same topic
There are currently no matching articles.