= Solution
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 \b[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.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2021/imperative-programming-suffix-interval.png]
{title=Original suffix-array example for banana: an interval of suffixes shares the repeated prefix ana}
Back to article page
