How do you construct a Suffix Array efficiently?
A Suffix Array can be constructed by sorting all suffixes and then selecting the smallest lexicographical order.
Thatâ€™s partially correct. While suffixes are sorted in lexicographical order, efficient construction methods do not require sorting all suffixes individually.
Can you explain why direct sorting of all suffixes is not efficient and what optimizations can be used instead?