Suffix arrays are the modern replacement for suffix trees in most applications. They use O(n) space instead of O(n²), cache better, and are simpler to implement. Every genome search engine, deduplication system, and text indexer uses them.
The String Matching Problem
Given a text T of length n and a pattern P of length m, find all occurrences of P in T:
def naive_search(text: str, pattern: str) -> list:
"""O(n × m) brute force — scans every position."""
results = []
for i in range(len(text) - len(pattern) + 1):
if text[i:i+len(pattern)] == pattern:
results.append(i)
return results
# For genome search (n = 3 billion, m = 100):
# O(n × m) = 300 billion operations — too slowBuilding a Suffix Array
A suffix array is the sorted array of all suffixes of a string, stored as their starting indices:
def build_suffix_array_naive(text: str) -> list:
"""O(n² log n) naive construction — for understanding only."""
suffixes = list(range(len(text)))
suffixes.sort(key=lambda i: text[i:])
return suffixes
text = "banana"
sa = build_suffix_array_naive(text)
# sa = [5, 3, 1, 0, 4, 2]
# Suffixes: "a", "ana", "anana", "banana", "na", "nana"The naive approach is O(n² log n) due to string comparisons. The SA-IS algorithm achieves O(n):
def build_suffix_array_sais(text: str) -> list:
"""SA-IS linear time suffix array construction.
Implementation omitted for brevity — use a library."""
# Key idea: classify suffixes as S-type or L-type,
# induce sort from smaller suffixes to larger ones.
# O(n) time, O(n) space.
pass
# In practice: use libdivsufsort (C) or SA-IS (Python/C extension)
# 1 million characters: ~0.1 seconds
# 1 billion characters (genome): ~100 secondsLCP Array: The Hidden Power
The LCP (Longest Common Prefix) array stores the length of the longest common prefix between adjacent suffixes in the sorted order:
def build_lcp_array(text: str, sa: list) -> list:
"""Kasai's algorithm: O(n) LCP construction."""
n = len(text)
rank = [0] * n
lcp = [0] * n
for i in range(n):
rank[sa[i]] = i
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 text[i + h] == text[j + h]:
h += 1
lcp[rank[i]] = h
if h > 0:
h -= 1
return lcp
text = "banana"
sa = [5, 3, 1, 0, 4, 2]
lcp = build_lcp_array(text, sa)
# lcp = [0, 1, 3, 0, 0, 2]
# Between "a" and "ana": LCP = 1
# Between "ana" and "anana": LCP = 3Pattern Matching with Binary Search
Search for pattern P in suffix array using binary search:
def suffix_array_search(text: str, sa: list, pattern: str) -> int:
"""O(m log n) pattern search using suffix array binary search."""
n = len(text)
m = len(pattern)
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
suffix = text[sa[mid]:sa[mid] + m]
if suffix < pattern:
lo = mid + 1
elif suffix > pattern:
hi = mid - 1
else:
return sa[mid] # found at position sa[mid]
return -1 # not found
# Binary search: O(m log n) comparisons
# Each comparison: O(m) worst case
# Total: O(m log n) — much better than O(nm) naiveSuffix Array for All Occurrences
To find ALL occurrences, find the range of suffixes that start with P:
def find_all_occurrences(text: str, sa: list, pattern: str) -> list:
"""Find all occurrences of pattern in text using suffix array."""
n = len(text)
m = len(pattern)
# Find leftmost occurrence (lower bound)
lo, hi = 0, n
while lo < hi:
mid = (lo + hi) // 2
suffix = text[sa[mid]:sa[mid] + m]
if suffix < pattern:
lo = mid + 1
else:
hi = mid
if lo >= n or text[sa[lo]:sa[lo] + m] != pattern:
return []
# Find rightmost occurrence (upper bound)
lo2, hi2 = lo, n
while lo2 < hi2:
mid = (lo2 + hi2) // 2
suffix = text[sa[mid]:sa[mid] + m]
if suffix <= pattern:
lo2 = mid + 1
else:
hi2 = mid
return sorted(sa[lo:lo2])
# All occurrences found in O(m log n + k) where k is the counttradeoff / Suffix Array vs Suffix Tree vs Hash Table
For genome-scale search (3 billion characters), suffix arrays with SA-IS construction and FM-index query achieve O(n) construction and O(m) search — the fastest known approach for short read alignment.
Suffix arrays are the default choice for most string matching applications. Suffix trees are preferred when you need online construction or complex pattern queries (e.g., longest common substring). Hash tables are fastest for exact pattern matching but lose ordering information.
Synthesis
Suffix arrays sort all suffixes of a string, enabling O(m log n) pattern search with O(n) space. The LCP array adds efficient range queries and longest common substring detection. SA-IS construction achieves linear time. These structures are the backbone of genome search, text deduplication, and data compression.