Suffix Array

A suffix array stores the starting positions of every suffix in lexicographic order. It pays off when one text stays fixed and many patterns must be queried: build the index once, then use binary search for each lookup. The construction shown here uses prefix doubling and runs in O(n log^2 n) time.

Think of it as a card catalog. The catalog stores page numbers, not photocopies of every page from that point onward. For BANANA, the entry 3 means the suffix ANA; the array keeps the six start positions while the original text supplies the characters. That is the difference between O(n) index storage and O(n^2) copied suffix text.

How Suffix Arrays Work

For a text of length n, suffix i is text[i:]. Sorting all suffixes gives an array of their start indices. BANANA has this final order:

The obvious construction compares whole suffix strings. It is easy to write and expensive to scale because the compared strings can be O(n) characters long. Prefix doubling avoids that bill.

Start by assigning a rank to each character. If two suffixes begin with the same character, they receive the same rank. Suppose ranks already describe the first k characters of every suffix. Then the first 2k characters of suffix i are described by one pair:

(rank[i], rank[i + k])

The first number identifies the first k-character block; the second identifies the next block. If the second block runs past the end of the text, use -1. That sentinel matters: a shorter suffix must sort before a longer suffix that starts with the same characters. A belongs before ANA, not in a philosophical tie with it.

Sort the integer pairs, assign equal pairs the same new rank, and increment the rank when an adjacent pair changes. The new ranks now describe 2k characters. Double k and repeat. Once every rank is unique, the suffix order is fixed.

The finished suffix array supports binary search. Compare the pattern with a pattern-length prefix of the middle suffix. A smaller prefix moves lo right; an equal or larger prefix moves hi left. Equality moves left because this implementation computes a lower bound. After the interval closes, one startswith check confirms the candidate.

Suffix Array Step by Step

The default run builds the suffix array for text = "BANANA", then searches for pattern = "ANA".

Before any rank appears, the opening beat names the bargain: sort this fixed text once, then use binary search for each pattern.

1. Rank one character. Sorted characters are A < B < N, so their ranks are 0, 1, 2. By text position, rank = [1, 0, 2, 0, 2, 0].
2. Round k = 1. Each suffix receives a two-rank key: start 0 gets (1, 0), starts 1 and 3 get (0, 2), starts 2 and 4 get (2, 0), and start 5 gets (0, -1) because it ends after A.
3. Sort the pairs. Their order is [5, 1, 3, 0, 2, 4]. Starts 1 and 3 still tie; starts 2 and 4 tie as well. The new rank array, written back by original start position, is [2, 1, 3, 1, 3, 0].
4. Double to k = 2. The first round certified two characters. The animation pauses on start 1: the raw blocks are AN | AN, and each AN already has rank 1, so (1, 1) names the same four-character prefix. The round then forms every key: start 5 gets (0, -1), start 1 gets (1, 1), start 3 gets (1, 0), start 0 gets (2, 3), start 2 gets (3, 3), and start 4 gets (3, -1).
5. Sort again. The order becomes [5, 3, 1, 0, 4, 2]. Every new rank is unique, so construction stops. The catalog now says A, ANA, ANANA, BANANA, NA, NANA without storing any of those strings separately.
6. Start lower bound. The search window is [0, 6). mid = 3 points to start 0, whose pattern-length prefix is BAN. Since BAN > ANA, set hi = 3.
7. Probe the left half. mid = 1 points to start 3, and the prefix is ANA. Equality sets hi = 1; lower bound keeps looking left instead of accepting the first equal probe.
8. Close the interval. mid = 0 points to start 5, whose prefix is only A. Since A < ANA, set lo = 1. Now lo == hi.
9. Verify once. SA[1] = 3, and BANANA starts with ANA at index 3, so find_one returns 3.

ANA also occurs at text index 1. Returning 3 is still correct: find_one returns one occurrence, specifically the first matching suffix in suffix-array order. To list every occurrence, run a second bound for the end of the matching prefix range and collect the start indices inside that interval.

Time and Space Complexity of a Suffix Array

Let n be the text length and m the pattern length.

There are O(log n) doubling rounds. Each round builds n constant-size rank pairs and comparison-sorts them in O(n log n), giving O(n log^2 n) construction time. A radix or counting sort over the integer ranks can reduce construction to O(n log n), but that is a different implementation from the one displayed here. Claiming its bound would be borrowing someone else's homework.

Each binary-search probe compares at most m characters, and there are O(log n) probes. The teaching code uses slices for those prefixes, so it may hold O(m) transient characters. A direct indexed comparison can avoid that allocation without changing the search bound.

Build this index when one text will answer many pattern queries; the construction cost is then spread across searches. For one lookup, text.find(pattern) is usually the honest tool. If one pattern is reused across many incoming texts, KMP preprocesses the other side of the problem.

Edge Cases

• One-character text. The initial character rank already determines the only suffix, so the doubling loop does not run.
• All characters equal. AAAAAAAA keeps large tied groups through k = 1, 2, and 4. This is the longest construction trace at the lesson's eight-character canvas limit.
• A suffix ends inside the second block. The -1 sentinel makes the shorter suffix sort first. Using rank 0 instead can merge two states that are not equal.
• Pattern longer than text. Binary search still closes normally; the final startswith check returns -1.
• Several occurrences. find_one returns one suffix-array-order occurrence, not necessarily the smallest text index.
• Empty text or pattern. The pure construction helper handles empty text as SA = []. The UI requires non-empty text and pattern because empty-pattern return conventions differ across APIs.

Common Mistakes

• Storing every suffix string. A suffix array stores starts. Copying text[i:] for every i spends O(n^2) space before the interesting work has begun.
• Using 0 as the end sentinel. Rank 0 belongs to a real character class. The end marker must be smaller than every real rank.
• Updating rank during the pair scan. Every key in one round must read the same previous rank array. Write into next_rank, then commit after all adjacent pairs are classified.
• Comparing only rank[i]. That repeats the one-character sort forever. The second rank is what doubles the certified prefix length.
• Stopping at the first equal binary-search probe. That finds an occurrence but not a lower bound. Keep hi = mid on equality if you need the left edge of the matching suffix range.
• Calling this implementation O(n log n). The displayed code uses comparison sort for each round, so its construction time is O(n log^2 n). The faster bound needs a different sorting subroutine.