Suffix Trees & Arrays

## The problem, stated without a puzzle A sequencing pipeline hands you one long read — a single string of tens or hundreds of millions of symbols — and you want the longest segment that appears in it at least twice, plus where it appears. The brute-force framing is horrible: comparing all pairs of starting positions is quadratic in the read length before you even account for comparison cost. The suffix-array-plus-LCP framing turns it into two linear-ish passes. ## Why repeats are prefixes Every occurrence of a segment `S` at position `j` means `S` is a prefix of the suffix that starts at `j`. So "`S` occurs at least twice" is the same statement as "`S` is a common prefix of at least two distinct suffixes". The longest repeated segment is therefore the longest common prefix over all pairs of suffixes. This reframing is the whole idea; everything else is bookkeeping. ## The LCP array With the suffixes sorted (that is the suffix array), define `lcp[i]` = the number of leading characters shared by the suffix at rank `i-1` and the suffix at rank `i`. There are `n-1` meaningful entries, indexed from 1 in the convention used here; `lcp[0]` has no predecessor and is left undefined or zero. The key lemma is that for ranks `i < j`, > LCP(suffix at rank i, suffix at rank j) = min( lcp[i+1], lcp[i+2], ..., lcp[j] ). Intuitively: lexicographic order is agreement-then-divergence, and as you walk down the sorted list the shared prefix with a fixed earlier suffix can only shrink or hold. The consequence is immediate and is what makes the algorithm linear: any pairwise LCP is a minimum over adjacent LCPs, and a minimum is never larger than any element it ranges over. So the maximum pairwise LCP equals the maximum adjacent LCP. Scanning neighbours is not a heuristic — it is exhaustive. ## The scan One pass over `lcp[1..n-1]` tracks the largest value seen and the suffix offset that produced it. The answer's length is that maximum; the answer's text is the first `best` characters of the suffix at that rank. If the maximum is zero, no segment repeats — every position starts a distinct-from-the-first-character suffix. ## Cost, stated precisely - Suffix array: O(n) with a linear construction, O(n log n) with prefix doubling. - LCP array: **O(n)** by Kasai's algorithm, given the suffix array and its inverse. The amortised argument is neat — you compute LCPs in order of text position rather than rank, and the running match length drops by at most one per step, so the total work over all steps is linear. - The scan: O(n). Total: linear or `n log n`, dominated entirely by construction. Compare that with the naive pairwise comparison, which is quadratic in the number of positions and worse once comparison cost is counted. That gap is the entire reason the structure exists. ## Three sharp edges **Overlap.** The two occurrences behind the winning LCP value can overlap. A read containing a long homopolymer run — the same symbol repeated 5,000 times — yields an LCP near 5,000 from two suffixes one position apart. If the biological question demands two *disjoint* copies, you need the extra condition `|i - j| >= L` on the pair of offsets. The standard route is a binary search on the candidate length `L`: for a given `L`, split the sorted order into maximal blocks whose adjacent LCPs are all at least `L`, and check whether any block contains two offsets at least `L` apart. Monotonicity in `L` makes the binary search valid. **Multiplicity.** "Occurs at least `k` times" generalises just as cleanly: instead of the maximum single adjacent LCP, take the maximum over windows of `k` consecutive ranks of the minimum LCP inside the window — a sliding-window minimum, still linear. **Position reporting.** Report the offset, not only the length. An answer that produces a number without being able to point into the read has not solved the problem the pipeline actually has. ## The wrong answers this question aims at The first is "you have to compare all pairs of suffixes" — no, sorting already did the pairwise work implicitly, and the adjacent-minimum lemma is why. The second is "the LCP array must itself be built by re-comparing characters, so it's quadratic" — no, linear-time construction exists and its amortised argument is worth being able to sketch. The third is quietly reporting overlapping occurrences as if the question had not asked for two copies.