= 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\leq k\leq\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 \b[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.
Back to article page
