= Solution
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 \b[a strict comparator], returning false for a <string suffix> compared with itself, in constant time. For distinct suffixes its running time is $O(K+1)$, where $K$ is the longest repeated-substring length of the full <array>.
Back to article page
