Introduction to Suffix Arrays
A suffix array is a powerful data structure used in string processing and pattern matching. Conceptually, it is an array of integers that represents the starting indices of all suffixes of a given string, sorted in lexicographical order. Despite its simplicity, the suffix array enables efficient solutions to many classic string problems, including longest common prefix queries, substring search, and data compression.
For a string S of length n, there are exactly n suffixes. A naive approach would generate all suffixes, sort them, and store their starting positions. While this works, it is inefficient for large inputs. The real value of suffix arrays lies in the algorithms used to construct them and the operations they enable afterward.
Why Suffix Arrays Matter
Suffix arrays serve as a memory-efficient alternative to suffix trees. A suffix tree encodes the same information but uses significantly more memory due to its tree structure and pointer overhead. Suffix arrays, being plain integer arrays, are far more cache-friendly and easier to serialize, making them ideal for large-scale text processing applications.
- Pattern matching: Find all occurrences of a pattern in O(m log n) time using binary search.
- Longest repeated substring: Identify the longest substring that appears more than once.
- Data compression: Used in algorithms like the Burrows-Wheeler Transform.
- Bioinformatics: Useful in genome assembly and sequence alignment.
- Plagiarism detection: Compare documents by analyzing shared substrings.
Naive Construction
The simplest way to build a suffix array is to generate every suffix, pair it with its starting index, sort the suffixes lexicographically, and extract the indices. This approach is easy to understand but has a time complexity of O(n^2 log n) due to string comparisons during sorting.
def naive_suffix_array(s):
suffixes = [(s[i:], i) for i in range(len(s))]
suffixes.sort(key=lambda x: x[0])
return [idx for _, idx in suffixes]
# Example usage
text = "banana"
print(naive_suffix_array(text))
# Output: [5, 3, 1, 0, 4, 2]
The output represents the sorted suffixes of "banana": "a", "ana", "anana", "banana", "na", "nana". Each number is the starting index of that suffix in the original string.
Efficient Construction: The Prefix Doubling Algorithm
To improve on the naive approach, we use the prefix doubling algorithm, which runs in O(n log^2 n) time. The idea is to sort suffixes by their first k characters, then double k in each iteration until k exceeds n. At each step, we compare pairs of ranks rather than full substrings, which makes comparisons O(1).
How Prefix Doubling Works
Initially, each suffix is ranked by its first character. In each subsequent iteration, the rank of a suffix is determined by the pair (current rank, rank of the suffix starting k positions ahead). This allows us to compare suffixes based on 2k characters without examining them directly.
def build_suffix_array(s):
n = len(s)
# Initial ranking based on single characters
rank = [ord(c) for c in s]
sa = list(range(n))
k = 1
while k < n:
# Sort by (rank[i], rank[i+k] or -1)
sa.sort(key=lambda i: (rank[i], rank[i + k] if i + k < n else -1))
# Compute new ranks
new_rank = [0] * n
for i in range(1, n):
prev, curr = sa[i - 1], sa[i]
prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
curr_key = (rank[curr], rank[curr + k] if curr + k < n else -1)
new_rank[curr] = new_rank[prev] + (1 if curr_key != prev_key else 0)
rank = new_rank
if rank[sa[-1]] == n - 1:
break
k *= 2
return sa
text = "banana"
print(build_suffix_array(text))
# Output: [5, 3, 1, 0, 4, 2]
This implementation uses Python's built-in sort, which contributes a log n factor per iteration. Since we double k each time, there are O(log n) iterations, giving an overall time complexity of O(n log^2 n). Using radix sort instead of comparison sort reduces this to O(n log n).
Time Complexity Analysis
Understanding the time complexity of suffix array construction is essential for choosing the right algorithm for your use case.
Naive Approach
Generating all suffixes takes O(n^2) space if stored explicitly, and sorting them requires O(n log n) comparisons, each taking O(n) time in the worst case. This yields a total time complexity of O(n^2 log n). For strings longer than a few thousand characters, this becomes impractical.
Prefix Doubling with Comparison Sort
Each iteration sorts n elements in O(n log n) time, and there are O(log n) iterations because k doubles each round. The total time complexity is O(n log^2 n). Space complexity is O(n) for the rank and suffix arrays.
Prefix Doubling with Radix Sort
By replacing the comparison-based sort with a radix sort on pairs of integers, each iteration runs in O(n) time. With O(log n) iterations, the total time complexity becomes O(n log n). This is the most commonly used approach in competitive programming.
Linear Time Algorithms
Algorithms such as SA-IS (Suffix Array Induced Sorting) and the DC3 (Difference Cover modulo 3) algorithm can construct suffix arrays in O(n) time. These are more complex to implement but are necessary for very large inputs, such as genomic datasets containing millions of characters.
Pattern Matching with Suffix Arrays
Once the suffix array is built, we can perform efficient pattern matching using binary search. Since the suffixes are sorted, all occurrences of a pattern form a contiguous range in the suffix array. We can find the lower and upper bounds of this range in O(m log n) time, where m is the pattern length.
def binary_search_left(sa, s, pattern):
lo, hi = 0, len(sa)
while lo < hi:
mid = (lo + hi) // 2
if s[sa[mid]:sa[mid] + len(pattern)] < pattern:
lo = mid + 1
else:
hi = mid
return lo
def binary_search_right(sa, s, pattern):
lo, hi = 0, len(sa)
while lo < hi:
mid = (lo + hi) // 2
if s[sa[mid]:sa[mid] + len(pattern)] <= pattern:
lo = mid + 1
else:
hi = mid
return lo
def find_occurrences(sa, s, pattern):
left = binary_search_left(sa, s, pattern)
right = binary_search_right(sa, s, pattern)
return sorted(sa[left:right])
text = "banana"
sa = build_suffix_array(text)
print(find_occurrences(sa, text, "ana"))
# Output: [1, 3]
The two binary searches find the first suffix that is greater than or equal to the pattern, and the first suffix that is strictly greater than the pattern. The difference between these positions gives all matching suffixes, and their starting indices are the occurrences of the pattern in the original string.
Longest Common Prefix Array
The LCP array is a companion to the suffix array. For each adjacent pair of suffixes in the sorted suffix array, the LCP array stores the length of their longest common prefix. The LCP array can be constructed in O(n) time using Kasai's algorithm, which processes suffixes in their original order rather than sorted order.
def build_lcp_array(s, sa):
n = len(s)
rank = [0] * n
for i in range(n):
rank[sa[i]] = i
lcp = [0] * (n - 1)
h = 0
for i in range(n):
if rank[i] > 0:
j = sa[rank[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
lcp[rank[i] - 1] = h
if h > 0:
h -= 1
return lcp
text = "banana"
sa = build_suffix_array(text)
print(build_lcp_array(text, sa))
# Output: [1, 3, 0, 0, 2]
The LCP array is useful for finding the longest repeated substring, which corresponds to the maximum value in the LCP array. It also enables efficient computation of the number of distinct substrings, which equals n*(n+1)/2 - sum(lcp).
Best Practices
- Choose the right algorithm: For strings under 10,000 characters, the naive approach may suffice. For larger inputs, use prefix doubling or a linear-time algorithm.
- Append a sentinel character: Adding a unique character smaller than all others (such as '$') at the end of the string simplifies comparisons and prevents index out-of-bounds errors.
- Use integer ranks: Always work with integer ranks rather than substrings to keep comparisons O(1).
- Precompute the LCP array: Many advanced queries depend on the LCP array, so build it alongside the suffix array when possible.
- Consider memory usage: Suffix arrays and LCP arrays each require O(n) integers. For very large strings, use memory-efficient representations such as 32-bit integers.
- Leverage sparse tables for RMQ: To answer longest common prefix queries between arbitrary suffixes, combine the LCP array with a sparse table for range minimum queries in O(1) time after O(n log n) preprocessing.
Conclusion
Suffix arrays are a foundational data structure in string processing, offering a compact and efficient alternative to suffix trees. By understanding the trade-offs between naive, prefix doubling, and linear-time construction algorithms, developers can select the right approach for their specific performance and memory requirements. Combined with the LCP array and binary search, suffix arrays enable powerful operations such as fast pattern matching, longest repeated substring detection, and distinct substring counting. Whether you are building a search engine, a bioinformatics pipeline, or a compression tool, mastering suffix arrays will give you a robust toolset for tackling complex string problems efficiently.