Suffix Array
Sort all suffixes of a string once, then answer many substring questions by binary searching the sorted order.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
Selected suffix
[0] abracadabra
Sorted suffix order
Sort every suffix once
Binary searching this sorted suffix list turns substring existence queries into prefix comparisons against ranks rather than scanning the whole text.
Family
Strings
Prefix-aware structures and text-centric search strategies.
Builds on
1 topic
Read these first if you want the surrounding context.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
You want fast substring search, lexicographic suffix ordering, or range-style questions over all suffixes of one string.
Core idea
Build an array of suffix starting positions and sort them by the suffix text.
If the suffixes are in lexicographic order, then all occurrences of a pattern correspond to a contiguous binary-search range in that order.
That is the big win: expensive substring reasoning becomes order queries over integers.
Why it matters
Suffix arrays are one of the canonical advanced string structures because they turn one string into an indexed search space.
They pair naturally with:
- binary search for pattern lookup
- LCP arrays for common-prefix structure
- offline substring ordering tasks
Complexity
Construction depends on the method used, but the high-level query story is:
| Operation | Time |
|---|---|
| Pattern existence query | without extra LCP acceleration |
Key takeaways
- A suffix array is just the sorted order of all suffixes
- Binary search over that order solves many substring existence queries
- LCP information is what upgrades suffix arrays from good to extremely powerful
- This is rare advanced string material, but it is one of the major classic structures
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Substring Order references | 🔴 Hard | Sorting suffixes plus LCP |
| String Matching | 🔴 Hard | Query patterns against suffix structure |
| Repeated Substring references | 🔴 Hard | LCP-driven reasoning |
Relation to other topics
- Binary Search is the query mechanism over suffix ranks
- Rabin-Karp offers a hashing-based alternative for substring comparison tasks
- Suffix Automaton is another advanced structure for substring-heavy problems, with a very different shape
Build on these first
These topics supply the mental model or underlying structure that this page assumes.
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
KMP (Knuth-Morris-Pratt)
Search for a pattern in linear time by reusing information about its own prefixes instead of restarting after mismatches.
Rabin-Karp
Search with rolling hashes so most windows can be rejected with arithmetic instead of full character comparisons.
Z-Algorithm
Compute how much of the global prefix matches at every position, then reuse the active Z-box to stay linear.
Suffix Automaton
Compress all substrings of a string into a linear-size automaton with suffix links.
More from Strings
Stay in the same family when you want parallel variations of the same mental model.
KMP (Knuth-Morris-Pratt)
Search for a pattern in linear time by reusing information about its own prefixes instead of restarting after mismatches.
Rabin-Karp
Search with rolling hashes so most windows can be rejected with arithmetic instead of full character comparisons.
Trie (Prefix Tree)
A tree-like data structure for efficient string storage and prefix-based retrieval. Essential for autocomplete, spell checking, and word search problems.
Z-Algorithm
Compute how much of the global prefix matches at every position, then reuse the active Z-box to stay linear.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
String matching
Move from prefix reuse and rolling hashes to suffix-based indexing and automata.
Substring toolkit
Compare rolling hashes, sorted suffixes, automata, and palindrome-specific structure.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.