Senior LevelData Structures & Algorithms
What is a Suffix Array and how is it used for pattern matching?
❓ Interview Prompt: Explain Suffix Arrays, O(N log N) construction (prefix doubling), LCP array, and O(log N) pattern search.
A Suffix Array is a sorted array of all suffixes of a string, storing their starting indices.
Why Suffix Arrays?
•
$O(N \log N)$ construction (prefix doubling / SA-IS $O(N)$).
•
Pattern search: Binary search on sorted suffixes → $O(P \log N)$ vs Suffix Trie's $O(P)$.
•
Space: $O(N)$ integers vs $O(N^2)$ for suffix trie.
Coupled with LCP (Longest Common Prefix) Array:
•
Enables many string queries in $O(N)$ post-preprocessing: count distinct substrings, longest repeated substring.
Code Implementation Example
typescript
// Simple O(N log²N) suffix array construction
function buildSuffixArray(s: string): number[] {
const n = s.length;
const sa = Array.from({ length: n }, (_, i) => i);
const rank = Array.from({ length: n }, (_, i) => s.charCodeAt(i));
const tmp = new Array(n);
for (let gap = 1; gap < n; gap <<= 1) {
const compare = (a: number, b: number) => {
if (rank[a] !== rank[b]) return rank[a] - rank[b];
const ra = a + gap < n ? rank[a + gap] : -1;
const rb = b + gap < n ? rank[b + gap] : -1;
return ra - rb;
};
sa.sort(compare);
tmp[sa[0]] = 0;
for (let i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i], sa[i - 1]) !== 0 ? 1 : 0);
for (let i = 0; i < n; i++) rank[i] = tmp[i];
}
return sa;
}💡O(N log²N) suffix array via prefix doubling sort.
🎯 Interview Key Takeaway
Suffix Arrays power competitive-programming string problems and real-world systems like full-text search indexes (Lucene), genome aligners, and file diff tools.
#DSA#Suffix Array#Strings#Advanced#Senior
Back to all Data Structures & Algorithms Questions→