Back to Study Material Data Structures and Algorithms

Suffix Array

A suffix array is an array of integers representing the starting positions of all suffixes of a string, sorted in lexicographic order. For string S of leng...

Suffix Array

All Suffixes Sorted in Linear Space

A suffix array is an array of integers representing the starting positions of all suffixes of a string, sorted in lexicographic order. For string S of length N, the suffix array SA has N entries where SA[i] equals the starting index in S of the i-th lexicographically smallest suffix. The suffix array provides many of the same capabilities as a suffix tree but uses less memory and is generally more cache-friendly.

For example, for S equals "banana", the six suffixes sorted lexicographically are: "a", "ana", "anana", "banana", "na", "nana". Their starting indices are 5, 3, 1, 0, 4, 2. So SA equals [5, 3, 1, 0, 4, 2]. Given SA, you can binary search for a pattern P in O(M log N) time (M is pattern length) by comparing P against suffixes at the midpoint of the binary search range.

The suffix array uses O(N) space (just an integer array). Combined with an LCP (Longest Common Prefix) array, it replicates virtually every capability of a suffix tree. Construction can be done in O(N log N) using a doubling algorithm (build order for length-1 substrings, then length-2, then length-4, etc.) or in O(N) using the SA-IS algorithm.

LCP Array and Its Uses

The LCP array stores, for each consecutive pair of suffixes in the sorted suffix array, the length of their longest common prefix. Formally, LCP[i] is the length of the longest common prefix between the suffix at SA[i] and the suffix at SA[i minus 1]. LCP[0] is undefined (or set to zero). The LCP array can be built in O(N) using Kasai's algorithm after the suffix array is constructed.

With SA and LCP, the longest repeated substring is the maximum value in the LCP array, and its location tells you which suffix it corresponds to. The number of distinct substrings of S equals N times (N plus one) divided by two minus the sum of all LCP values — derived from the observation that each suffix contributes (suffix length minus LCP with previous suffix) new substrings beyond those shared with the prior suffix.

Binary search for pattern P with the LCP array can be accelerated to O(M plus log N) by maintaining LCP information during the search to avoid re-comparing characters already known to match.

Worked Example and Practical Preference

Worked example: for S equals "aab", suffixes are "aab" (index 0), "ab" (index 1), "b" (index 2). Sorted: "aab" < "ab" < "b". So SA equals [0, 1, 2]. LCP[0] equals 0 (undefined), LCP[1] equals 1 (common prefix of "aab" and "ab" is "a"), LCP[2] equals 0 (common prefix of "ab" and "b" is empty). Number of distinct substrings: 3 times 4 divided by 2 minus (0 plus 1 plus 0) equals 6 minus 1 equals 5. The five distinct substrings of "aab" are: "a", "aa", "aab", "ab", "b". Correct.

Search for pattern "a" in "aab": binary search on SA using suffix comparisons. SA[1] points to "ab" which starts with "a"; SA[0] points to "aab" which starts with "a". Both are matches. All occurrences: starting indices 0 and 1.

Interview tip: for string problems in interviews, propose a suffix array with LCP array as the practical alternative to a suffix tree. Mention that the O(N log N) construction is implementable in a reasonable time during a longer interview, whereas O(N) Ukkonen's algorithm is too complex. Kasai's O(N) LCP construction is straightforward. The combination gives you O(N log N) preprocessing and O(M plus log N) pattern search, which handles most string algorithm problems efficiently.