DSA Notes
Efficient string indexing and pattern matching with suffix arrays.
What is a Suffix Array?
A suffix array is a sorted array of all suffixes of a given string. It is one of the most powerful data structures for string processing, enabling efficient pattern matching, longest common prefix computation, and substring searching. Think of it as an index for a book — it tells you exactly where to find any pattern within the text.
Given the string "banana", its suffixes are:
| Index 0 | "banana" |
| Index 1 | "anana" |
| Index 2 | "nana" |
| Index 3 | "ana" |
| Index 4 | "na" |
| Index 5 | "a" |
The suffix array is obtained by sorting these suffixes alphabetically and storing their starting indices:
Building a Suffix Array
Naive Approach: O(n² log n)
Sort all suffixes directly. Each comparison takes O(n) and sorting takes O(n log n) comparisons:
Efficient Approach: O(n log n) with Prefix Doubling
The prefix doubling algorithm sorts suffixes by comparing progressively longer prefixes (length 1, 2, 4, 8, ..., until we cover the full string):
How it works: In each iteration, we sort suffixes by their first 2^k characters. After log(n) iterations, we have sorted by the full string. The key insight is that comparing by 2k characters reuses the ranking from the previous iteration (which sorted by k characters).
Pattern Matching with Suffix Arrays
To find all occurrences of a pattern, binary search on the suffix array:
LCP Array (Longest Common Prefix)
The LCP array stores the length of the longest common prefix between consecutive suffixes in the sorted suffix array. This is essential for many advanced applications:
Applications Using Suffix Array + LCP
Longest Repeated Substring
The longest repeated substring is the maximum value in the LCP array:
Number of Distinct Substrings
Total substrings minus duplicates (identified by LCP values):
def count_distinct_substrings(text):
n = len(text)
sa = build_suffix_array(text)
lcp = build_lcp_array(text, sa)
total = n * (n + 1) // 2 # Total possible substrings
duplicates = sum(lcp) # Shared prefixes = duplicates
return total - duplicates
print(count_distinct_substrings("banana")) # 15Complexity Analysis
| Operation | Time | Space |
|---|---|---|
| Build Suffix Array (naive) | O(n² log n) | O(n) |
| Build Suffix Array (prefix doubling) | O(n log n) | O(n) |
| Build Suffix Array (SA-IS) | O(n) | O(n) |
| Build LCP Array (Kasai) | O(n) | O(n) |
| Pattern Search | O(m log n) | O(1) |
| Longest Repeated Substring | O(n) after SA+LCP | O(n) |
Suffix Array vs Suffix Tree
| Feature | Suffix Array | Suffix Tree |
|---|---|---|
| Space | O(n) integers | O(n) but large constant |
| Construction | O(n log n) or O(n) | O(n) |
| Pattern match | O(m log n) | O(m) |
| Implementation | Simpler | Complex |
| Cache performance | Better (array) | Worse (pointers) |
| Practical choice | Most applications | When O(m) search needed |
Real-World Applications
- Bioinformatics — genome sequence alignment, finding repeated DNA patterns
- Text editors — fast find-and-replace across large documents
- Search engines — full-text indexing for document retrieval
- Data compression — BWT (Burrows-Wheeler Transform) uses suffix arrays
- Plagiarism detection — finding common substrings between documents
- Log analysis — searching patterns across massive log files
Interview Questions
Q1: What is the advantage of suffix arrays over suffix trees? A: Suffix arrays use significantly less memory (4-8 bytes per character vs 20-40 bytes for suffix trees) and have better cache performance due to array-based storage. They solve most of the same problems.
Q2: How do you find all occurrences of a pattern using a suffix array? A: Binary search for the pattern in the suffix array. All occurrences will be in a contiguous range. Two binary searches find the left and right boundaries of this range. Time: O(m log n).
Q3: What is the LCP array and why is it useful? A: The LCP array stores the length of the longest common prefix between adjacent suffixes in the sorted order. It enables O(1) queries for longest repeated substrings, counting distinct substrings, and building suffix trees from suffix arrays.
Q4: Can you build a suffix array in O(n) time? A: Yes. The SA-IS (Suffix Array by Induced Sorting) algorithm achieves O(n) time. The DC3/skew algorithm also achieves linear time. For competitive programming, O(n log n) prefix doubling is usually sufficient.
Q5: How are suffix arrays used in data compression? A: The Burrows-Wheeler Transform (BWT) used in bzip2 compression is efficiently computed using suffix arrays. The BWT rearranges characters to cluster similar characters together, enabling better compression.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Suffix Array - String Indexing.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, advanced, topics, suffix
Related Data Structures & Algorithms Topics