Lab 11 — Suffix Array & Kasai LCP

Goal

Build a suffix array in O(n log n) via prefix doubling, compute the LCP array in O(n) with Kasai’s algorithm, and apply the pair to the standard problems: longest repeated substring, distinct-substring counting, and pattern search.

Background

The suffix array sa is the array of starting indices of all suffixes of s, sorted lexicographically. It is the flat, cache-friendly cousin of the suffix tree.

Prefix doubling: sort suffixes by their first 2^k characters using rank pairs. If rank[i] orders suffixes by their first k characters, then the pair (rank[i], rank[i+k]) orders them by their first 2k. After ≤ log n rounds every rank is distinct and the sort is total.

Kasai’s insight: let lcp[r] = longest common prefix of suffixes sa[r-1] and sa[r]. If suffix starting at i shares h characters with its lexicographic predecessor, then suffix i+1 (drop one char) shares at least h−1 with its predecessor. So process suffixes in text order, never resetting h below h−1: total work O(n).

What the pair buys you:

  • Longest repeated substring = max(lcp)
  • Distinct substrings = n(n+1)/2 − Σlcp (each suffix contributes its length minus the overlap already counted)
  • Pattern matching: binary search the SA in O(m log n)
  • Longest common substring of two strings: concatenate with a separator, take max lcp across suffixes from different halves

SA + LCP is equivalent in power to a suffix tree — an in-order traversal of the suffix tree visits leaves in SA order, and internal-node string depths are exactly the LCP values. The suffix automaton (lab-05) is the third member of the family: same problems, different traversal idioms.

Interview Context

  • Codeforces / ICPC: core string tool, expected at Div 1 level
  • Bioinformatics roles: fundamental (genome alignment, FM-index)
  • LC 1044 (Longest Duplicate Substring, Hard): SA+LCP is the clean deterministic answer; most solutions use binary search + rolling hash and pray about collisions
  • Systems/search-infra roles: occasionally, as a design discussion (log-structured text indexes)
  • Standard FAANG: near zero — rolling hash (phase-03 lab-06) covers the rare string-Hard

When to Skip This Topic

Skip if any of these are true:

  • You haven’t mastered KMP (phase-03 lab-05) and rolling hash (phase-03 lab-06) — those cover 95% of interview string questions
  • You’re not targeting competitive programming or bioinformatics
  • You can’t state what a suffix even is without hesitating

One LC Hard justifies this lab. If LC 1044 isn’t on your target list, skim the Background and move on.

Problem Statement

Longest Duplicate Substring (LC 1044).

Given a string s, return any duplicated substring of maximum length — a contiguous substring that occurs two or more times (occurrences may overlap). Return "" if none exists.

Along the way, implement the general toolkit: suffix_array(s), kasai(s, sa), distinct_substrings(s).

Constraints

  • 2 ≤ |s| ≤ 3×10^4 (LC); toolkit should handle 10^5+
  • Lowercase English letters
  • Wall-clock: < 2 sec in Python

Clarifying Questions

  1. Can occurrences overlap? (Yes — “aaaa” → “aaa”.)
  2. Any answer of maximum length, or all of them? (Any one.)
  3. Alphabet size — does it matter? (Only for radix-sort variants; comparison sort doesn’t care.)
  4. Empty answer possible? (Yes, when all characters are distinct.)

Examples

s = "banana"
sa  = [5, 3, 1, 0, 4, 2]        (a, ana, anana, banana, na, nana)
lcp = [0, 1, 3, 0, 0, 2]
longest duplicate = "ana" (lcp = 3)
distinct substrings = 6·7/2 − 6 = 15

s = "abcd"  → ""  (all lcp = 0)
s = "aaaaa" → "aaaa"

Brute Force

For each length L from n−1 down: put all substrings of length L in a set; if one repeats, return it. O(n²) substrings × O(n) hashing = O(n³) worst case. For n = 3×10^4: hopeless.

Brute Force Complexity

  • Time: O(n³) (O(n²) with rolling hash per length, still too slow without the binary search)
  • Space: O(n²) for the substring set

Optimization Path

  1. Binary search on length + rolling hash: O(n log n) expected, but collision-correct only if you verify matches — most posted solutions don’t. (Cross-ref phase-03 lab-06.)
  2. Suffix array + LCP: two suffixes share a prefix of length L iff some adjacent SA pair has lcp ≥ L (sorted order puts the most similar suffixes next to each other). So the answer is simply max(lcp) — deterministic, no hashing.
  3. Build SA by doubling (log n rounds of sorting rank pairs), LCP by Kasai in O(n).

Final Expected Approach

def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i]) > key(sa[i - 1]))
        rank = tmp
        if rank[sa[-1]] == n - 1:      # all ranks distinct: done
            return sa
        k <<= 1

def kasai(s, sa):
    n = len(s)
    rank = [0] * n
    for pos, suf in enumerate(sa):
        rank[suf] = pos
    lcp = [0] * n          # lcp[r] = LCP(sa[r-1], sa[r]); lcp[0] = 0
    h = 0
    for i in range(n):     # suffixes in TEXT order
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h:
                h -= 1     # next suffix loses at most one char of overlap
        else:
            h = 0
    return lcp

def distinct_substrings(s):
    if not s:
        return 0
    return len(s) * (len(s) + 1) // 2 - sum(kasai(s, suffix_array(s)))

def longest_dup_substring(s):
    if len(s) < 2:
        return ""
    sa = suffix_array(s)
    lcp = kasai(s, sa)
    r = max(range(len(s)), key=lambda r: lcp[r])
    return s[sa[r]: sa[r] + lcp[r]]

Honesty note: Python’s Timsort makes each doubling round O(n log n), so this is O(n log² n) total. Replacing the sort with two-pass radix sort on the rank pairs gives true O(n log n). In Python the sort version is usually faster anyway (C-level sort vs interpreted radix loops).

Data Structures

  • sa: int array, suffix start indices in sorted order
  • rank: inverse-ish array, rank of each suffix among first-2^k-char prefixes
  • lcp: int array aligned to SA positions

Correctness Argument

  • Doubling invariant: after round k, rank orders suffixes by their first 2^k characters; the pair sort extends this to 2^(k+1). Missing tail = rank −1 sorts shorter suffixes first, matching lexicographic order.
  • Termination: ranks strictly refine each round; all distinct within log n rounds.
  • Kasai bound: if lcp(suffix i, predecessor) = h, then suffix i+1 and some suffix (the predecessor minus its first char) share h−1 chars; its true predecessor in SA order shares ≥ h−1. h increases ≤ n total and decreases ≤ n total → O(n).
  • Max-lcp = longest repeat: any two suffixes sharing prefix length L sandwich adjacent pairs each with lcp ≥ L (LCP of a range = min of adjacent lcps in it).

Complexity

  • SA: O(n log² n) with comparison sort, O(n log n) with radix
  • Kasai: O(n)
  • Space: O(n)

Implementation Requirements

  • Handle i + k ≥ n: shorter suffix ranks first (use −1 sentinel)
  • Early exit once all ranks distinct (big win on random strings)
  • lcp[0] is 0 by definition — don’t read it as a real pair
  • Kasai must iterate suffixes in text order, not SA order
  • Return indices, not substring copies, until the final answer (avoid O(n²) slicing)

Tests

  • suffix_array("banana") == [5, 3, 1, 0, 4, 2]; kasai == [0, 1, 3, 0, 0, 2]
  • LC 1044: “banana” → “ana”; “abcd” → “”; “aaaaa” → “aaaa”
  • distinct_substrings("banana") == 15; “aaa” → 3
  • Stress: random strings over {a,b} and {a,b,c}, n ≤ 40, vs sorted(range(n), key=lambda i: s[i:]) and a set-based distinct count — 500 trials
  • Performance: n = 5×10^4 random binary string, SA+LCP < 1 sec (measured ~0.15 s)

Follow-up Questions

  • Can you build the SA in O(n)? → Yes: SA-IS (induced sorting) and DC3/skew. Name them, don’t implement in an interview — doubling is the expected answer, linear constructions are a library job.
  • SA vs suffix automaton vs suffix tree — which do you reach for? → SA+LCP for offline, index-shaped questions (k-th substring, counting, binary search). Suffix automaton (lab-05) for online/DP-over-states questions (distinct substrings incrementally, longest common substring streaming). Suffix tree almost never by hand — SA+LCP simulates it.
  • LCP of two arbitrary suffixes, many queries? → LCP(sa[i..j]) = min of adjacent lcp values in the range → sparse-table RMQ, O(1) per query after O(n log n) build (phase-03 lab-04).
  • Count occurrences of pattern p? → Two binary searches over SA for the range of suffixes prefixed by p: O(m log n), then range length. Beats KMP when the text is fixed and patterns stream in.
  • Burrows-Wheeler transform connection? → BWT[i] = s[sa[i] − 1]: the character before each sorted suffix — the SA’s “last column”. bzip2 compresses it; the FM-index inverts it for O(m) pattern counting in compressed space. This is why read aligners (BWA, Bowtie) are SA machinery underneath.
  • Longest common substring of two strings? → Build SA of s1 + '#' + s2, answer = max lcp over adjacent pairs whose suffixes start in different halves.

Product Extension

  • Genome aligners: BWA/Bowtie build FM-indexes from suffix arrays of reference genomes
  • Plagiarism / clone detection: longest common substring across document pairs
  • Log deduplication: longest repeated substring flags templated spam
  • Full-text search indexes over static corpora (SA is simpler than an inverted index for substring — not word — queries)

Language/Runtime Follow-ups

  • Python: the key=lambda sort is fine to n ≈ 10^5; beyond that, precompute key tuples or use the two-array radix formulation.
  • C++: classic contest snippet ~30 lines; std::sort version handles 10^6 easily.
  • Java: beware substring pre-Java-7u6 O(1) myths — always compare via indices.
  • Rust: suffix crate implements SA-IS; hand-rolled doubling with sort_unstable_by_key is idiomatic.

Common Bugs

  1. Sorting by single rank instead of the pair: converges to first-character order and loops forever or returns garbage.
  2. Rank assignment off-by-one: tmp[sa[i]] must compare keys, not old ranks alone — two suffixes with equal pairs must get equal new ranks.
  3. Kasai iterated in SA order: the h ≥ h−1 amortization only holds in text order; wrong order gives O(n²).
  4. Forgot h -= 1: silently correct output but O(n²) worst case (“aaaa…”).
  5. Missing tail sentinel: treating rank[i+k] as 0 instead of −1 misorders “aa” vs “aab” suffixes.
  6. Separator collision in two-string concat: the separator must sort below every real character and appear nowhere in either string.

Debugging Strategy

  • Print all suffixes next to sa for a 6-char string; eyeball the sort
  • Assert sorted(sa) == range(n) (it’s a permutation) after every doubling round
  • Check lcp by direct prefix comparison on small inputs
  • Binary alphabet stress first — repeats are dense, off-by-ones surface immediately
  • If distinct-substring count is wrong, the bug is almost always in lcp, not sa

Mastery Criteria

  • Implement doubling SA from memory in ≤ 25 min
  • Implement Kasai in ≤ 15 min and explain the h−1 amortization without notes
  • Derive the distinct-substring formula on a whiteboard
  • Solve LC 1044 end-to-end in ≤ 40 min
  • State when you’d use SA vs suffix automaton vs rolling hash, with one problem each