Lesson 275
Suffix Arrays
Sorted Suffixes • Binary Search • LCP
1:00Sort every suffix of a string and store their starting indices to enable fast substring search, longest-repeated-substring queries, and distinct-substring counting with a fraction of a suffix tree's memory.
By the end, you can
- Define a suffix array and explain what it stores and why it saves memory.
- Construct the suffix array for a small string by sorting its suffixes and reading off the start indices.
- Explain why binary search on a suffix array locates all pattern matches and state its O(m log n) cost.
- Compute the LCP array by hand for a small string.
- Trace through Kasai's algorithm and explain why it runs in O(n).
- Use the LCP array to find the longest repeated substring and count distinct substrings.
- Compare suffix arrays to suffix trees on memory, simplicity, and query power.
- Name three real-world domains where suffix arrays are a core tool.
Up next in String Algorithms, Advanced DP & Competitive Techniques
