Back to 20 Concepts
advanced-strings • Expert
Suffix Arrays & Kasai's Longest Common Prefix (LCP)
A Suffix Array contains sorted indices of all string suffixes. Paired with Kasai's LCP array in O(N) time, it enables instantaneous full-text substring search, counting, and repeat detection.
Intuitive Mental Model
The Sorted Index in the Back of the Encyclopedia: Sorting all sentence endings alphabetically allows binary searching any phrase in the entire book in O(M log N).
C / TypeScript ImplementationHardware & Algorithmic Standard
// For string "banana":
// Suffixes: [ "banana" (0), "anana" (1), "nana" (2), "ana" (3), "na" (4), "a" (5) ]
// Suffix Array (Sorted): [ 5 ("a"), 3 ("ana"), 1 ("anana"), 0 ("banana"), 4 ("na"), 2 ("nana") ]
// LCP Array: [ 0, 1, 3, 0, 0, 2 ]Key Architectural Takeaways
- •Memory Lightweight: Uses 4x less memory than Suffix Trees while offering identical algorithmic power.
- •Full-Text Search: Binary search on Suffix Array finds any substring pattern of length M in O(M log N).
Common Coding Mistake
Building Suffix Arrays naively with O(N^2 log N) string sorting.
Optimal Solution
Use SA-IS (Suffix Array by Induced Sorting) for strictly linear O(N) construction.