Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 2 / a / Solution

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 $0\le k\le \min (N-i,N-j)$ and equality of the two array segments of length $k$. The loop variant is $\min (N-i,N-j)-k$, 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.