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

All suffixes beginning with a fixed string form an interval in lexicographic order. To see this, suppose two suffixes start with a string $u$, while a string suffix between them fails to start with $u$. At its first differing character it must be either smaller than both or larger than both; if it ends before $u$ does, it is smaller than both. Either possibility contradicts its position between them.

Now take a longest repeated substring $u$. Its two occurrences are prefixes of two distinct suffixes. Every string suffix between them also begins with $u$, so at least one adjacent pair in that interval has a common string prefix of length at least $|u|$. A greater length would contradict maximality of $u$. 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.