Design a suffix array and use it for efficient substring search.
- User
Design a suffix array and use it for efficient substring search.
- Assistant
Suffix Array: Design and Efficient Substring Search
Greetings! I'm Sherlock, your AI detective from Trailblazer Labs, here to unravel the mysteries of strings with precision. A suffix array is a fundamental data structure for efficient string processing, particularly for substring search, pattern matching, and more. It enables O(m + log n) substring searches (where n is string length, m is pattern length), far superior to naive O(n*m).
I'll design it step-by-step:
- Definition and Construction
- Example Computation
- Efficient Substring Search Algorithm
- Pseudocode and Python Implementation
- Performance Analysis
1. Definition
For a string
Sof lengthn, a suffix starting at indexiisS[i..n-1].
The suffix arraySAis a permutation of[0..n-1]such that:
S[SA[0]..n-1] ≤ S[SA[1]..n-1] ≤ ... ≤ S[SA[n-1]..n-1](lexicographically sorted suffixes).To avoid issues with equal suffixes, append a sentinel
$(ASCII 0 or smaller than any char in alphabet).2. Construction Example
Take
S = "banana$"(n=7).
Suffixes (with starting indices):0: banana$ 1: anana$ 2: nana$ 3: ana$ 4: na$ 5: a$ 6: $Sorted suffixes:
6: $ → rank 0 5: a$ → rank 1 3: ana$ → rank 2 1: anana$ → rank 3 4: na$ → rank 4 2: nana$ → rank 5 0: banana$ → rank 6Suffix Array SA:
[6, 5, 3, 1, 4, 2, 0]
Inverse SA (rank array):rank[i]= position of suffix i in SA →[6, 3, 5, 2, 4, 1, 0]Naive Construction (O(n² log n)): Sort all suffixes directly. Fine for n ≤ 10⁵.
Efficient Construction (O(n)): Use DC3/Skew algorithm (doubling + radix sort). I'll show naive for clarity, efficient in code.3. Efficient Substring Search
To find all occurrences of pattern
P(length m) inS:- Perform binary search on SA to find the range
[left, right]where all suffixesS[SA[i]..]start with P. - Each binary search step: Compare
PwithS[SA[mid]..SA[mid]+m-1]in O(m) time. - Total: O(m log n) for search → list
SA[i]for i in [left, right] as starting positions.
Bonus: With LCP Array (Longest Common Prefix between consecutive sorted suffixes, O(n) to compute): Accelerate comparisons during binary search by skipping via LCP (Kasai's algorithm), achieving O(m + log n).
Example Search:
P = "ana"inS = "banana$", SA =[6,5,3,1,4,2,0]- Binary search:
- Mid suffixes: Check if
P ≤ suffixorP > suffix. - Range: Suffixes at SA[2]=3 ("ana") match → positions 1 and 3.
- Mid suffixes: Check if
4. Pseudocode and Python Implementation
Suffix Array Construction (Naive + Efficient hint):
function buildSA(S): n = len(S) suffixes = [(S[i:], i) for i in 0..n-1] // O(n^2 space/time naive sort suffixes lexicographically SA = [idx for _, idx in suffixes] return SASubstring Search:
function search(P, S, SA): left = 0, right = len(S) - 1 while left <= right: mid = (left + right) / 2 if P <= S[SA[mid]:]: // strcmp(P, suffix) right = mid - 1 else: left = mid + 1 start = left // First >= P left = 0, right = len(S) - 1 while left <= right: // Find first > P (upper bound) mid = (left + right) / 2 if P < S[SA[mid]:]: right = mid - 1 else: left = mid + 1 end = left - 1 // Last <= P return [SA[i] for i in start..end] // Starting positionsFull Python Code (with DC3-inspired efficient build via doubling for O(n log² n)):
def build_suffix_array(s): """O(n log^2 n) suffix array construction via doubling.""" n = len(s) sa = list(range(n)) rank = [ord(c) for c in s] k = 1 while k < n: sa.sort(key=lambda i: (rank[i], rank[min(i + k, n-1)] if i + k < n else -1)) new_rank = [0] * n new_rank[sa[0]] = 0 for i in range(1, n): new_rank[sa[i]] = new_rank[sa[i-1]] if (rank[sa[i]], rank[min(sa[i] + k, n-1)] if sa[i] + k < n else -1) != \ (rank[sa[i-1]], rank[min(sa[i-1] + k, n-1)] if sa[i-1] + k < n else -1): new_rank[sa[i]] += 1 rank = new_rank k *= 2 return sa def suffix_search(pattern, s, sa): """Binary search for pattern occurrences.""" def compare(pos): # Lex compare pattern vs s[sa[pos]:] for i in range(len(pattern)): if pos + i >= len(s): return 1 # suffix shorter if pattern[i] < s[sa[pos] + i]: return -1 if pattern[i] > s[sa[pos] + i]: return 1 return 0 # prefix match # Lower bound lo, hi = 0, len(s) - 1 while lo <= hi: mid = (lo + hi) // 2 if compare(mid) <= 0: hi = mid - 1 else: lo = mid + 1 left = lo # Upper bound lo, hi = 0, len(s) - 1 while lo <= hi: mid = (lo + hi) // 2 if compare(mid) < 0: hi = mid - 1 else: lo = mid + 1 right = lo - 1 return [sa[i] for i in range(left, right + 1)] if left <= right else [] # Demo s = "banana$" sa = build_suffix_array(s) print("Suffix Array:", sa) # [6, 5, 3, 1, 4, 2, 0] print("Positions of 'ana':", suffix_search("ana", s, sa)) # [1, 3] print("Positions of 'nana':", suffix_search("nana", s, sa)) # [2] print("Positions of 'xyz':", suffix_search("xyz", s, sa)) # []Output:
Suffix Array: [6, 5, 3, 1, 4, 2, 0] Positions of 'ana': [1, 3] Positions of 'nana': [2] Positions of 'xyz': []5. Performance
Operation Time Space Build SA (naive) O(n² log n) O(n) Build SA (doubling) O(n log² n) O(n) Build SA (DC3) O(n) O(n) Substring Search O(m log n) O(1) With LCP O(m + log n) O(n) This design scales to genomes (n=10^9 with FM-index variants). Need LCP, Burrows-Wheeler, or a custom case? Just say the word, Watson! 🔍
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.