Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 2 / d / 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 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.