Suffix Array | DrawCode

1. One-Liner

A suffix array SA is the list of indices sorting all suffixes of S lexicographically; with LCP it powers fast substring and repetition queries.

2. The Problem It Solves

Answer “how do suffixes relate?” in sorted order — used for substring search, longest repeated substring, number of distinct substrings, and BWT-adjacent structures.

3. The Core Idea

Doubling: sort suffixes by their first 2^k characters using ranks from the previous 2^{k-1} sort — like radix sort on pairs (rank[i], rank[i+2^{k-1}]).

4. How It Works (Table)

Step	What Happens
1	Pad with sentinel `$` smaller than alphabet if needed.
2	Initial ranks = character codes.
3	Repeat: sort `SA` by pairs `(rank[i], rank[i+k])` until ranks unique.
4	Result `SA` is lexicographic suffix order.

5. Dry Run Example

"aba

quot; → suffixes aba$, ba$, a$, $ → sorted order indices give SA.

6. Key Properties

Property	Value
Build	O(`n log n`) typical (doubling); O(`n`) advanced (SA-IS)
Space	O(`n`)
With LCP	Enables linear-space substring stats

7. Where It Is Used

Domain	Use
Bioinformatics	FM-index / BWT pipelines
Compression	Burrows–Wheeler transform
Text indexing	Competitive programming, research

8. Interview Tips

Know doubling intuition; mention LCP with Kasai as follow-up. For interviews, O(n log² n) acceptable if clean.

9. Comparison with Other Algorithms

Structure	Tradeoff
Suffix trie/tree	More memory, easier incremental
Suffix array	Compact, needs LCP for some queries

10. Complexity

Metric	Value
Doubling build	O(`n log n`) time, O(`n`) space
SA-IS	O(`n`) time (advanced)

Implementation Example (PYTHON)

def suffix_array(s):
    s = s + '


    
  


    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    k = 1
    while k < n:
        sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
        tmp[sa[0]] = 0
        for i in range(1, n):
            a, b = sa[i - 1], sa[i]
            prev = (rank[a], rank[a + k] if a + k < n else -1)
            cur = (rank[b], rank[b + k] if b + k < n else -1)
            tmp[b] = tmp[a] + (prev != cur)
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1
    return sa