A strong answer
A suffix array is the list of a text's suffix starting positions, sorted by the suffixes. It uses one integer per character, and with the LCP array, the common-prefix length of each pair of neighbors, it answers many substring questions.
Pattern search: suffixes that start with the pattern form one contiguous block in sorted order, found by two binary searches in O(m log n), and the block's size counts the occurrences. Longest repeated substring: the largest LCP value. Distinct substrings: n(n + 1)/2 minus the sum of the LCPs. Longest common substring of two strings: build over a + separator + b and take the largest LCP between neighbors from different strings.
Building: sorting suffixes directly is O(n² log n). Prefix doubling sorts by the first 2k characters using the ranks for the first k, in O(n log n) with radix sort; SA-IS is linear. Kasai builds the LCP array in O(n), because the common prefix drops by at most one when moving from suffix i to i + 1.
I would build one when many queries run against one large, mostly static text: genome indexes, full-text search, duplicate-code detection. For a single search, KMP or the library's find is simpler. For one repeated-substring question, binary search with rolling hashes is less code. Suffix trees answer similar questions but need many times more memory, so suffix arrays usually replace them; the FM-index built on the Burrows-Wheeler transform compresses the idea further.
What the interviewer is listening for
- What is stored and why sorted order makes substring queries work.
- The LCP array's role.
- Realistic construction costs and when simpler tools suffice.
Common mistakes
- Storing the suffix strings themselves.
- Building with string comparisons on large inputs.
- Reaching for a suffix array when a single KMP search would do.