A suffix array is the lexicographically sorted order of every suffix of a string. The LCP (longest common prefix) array sits alongside it and records, for every pair of adjacent suffixes in the sorted order, how many characters they share at the start.

Together they form one of the most useful preprocessing structures in string algorithms. With a suffix array and LCP array you can:

This chapter covers the definition, a practical O(n log^2 n) construction algorithm, Kasai's O(n) LCP construction, and the most common applications.

Given a string S of length n, the suffix array SA is an array of integers of length n such that SA[i] is the starting position of the i-th smallest suffix of S in lexicographic order.

Example: S = "banana"

The six suffixes are:

Sorting them lexicographically:

The suffix array is [5, 3, 1, 0, 4, 2]. Reading it: the smallest suffix starts at index 5, the next at index 3, then 1, 0, 4, 2.

Storing starting indices instead of the suffix strings themselves matters for two reasons. The suffixes overlap: storing them all explicitly takes O(n^2) memory, while storing only their starting indices takes O(n). And every algorithmic operation needed for substring problems (pattern matching, LCP computation, substring queries) works on starting indices, dipping into the original string by index only when a character comparison is required.

The companion structure is the rank array, the inverse of SA. Rank[i] is the rank of the suffix starting at position i. If SA[r] = i, then Rank[i] = r. For S = "banana":

Read Rank as "where does the suffix starting at position i land in sorted order?" The suffix starting at index 0 ("banana") is the 4th smallest (rank 3), the suffix at index 5 ("a") is the smallest (rank 0), and so on.

The most direct way to build the suffix array is to generate every suffix as a string and sort them.

Generating all suffixes is O(n^2) characters of total work. Sorting them with the default comparison-based sort costs O(n log n) comparisons, each comparing strings of up to n characters, for O(n^2 log n) overall. For n = 10^5, that is roughly 10^11 character comparisons. Hopeless.

The naive approach is correct, easy to write, and useful for unit testing the fast version on small inputs. For real workloads it is replaced by rank doubling.

The standard practical algorithm sorts suffixes by rank pairs instead of by their full strings, doubling the prefix length being compared on each iteration.

The idea in one paragraph:

Each iteration sorts n suffixes by a pair of integers. A comparison-based sort costs O(n log n) per iteration. With O(log n) iterations, the total cost is O(n log^2 n).

Why Rank Pairs Work

Suppose we already know the rank of every suffix based on its first k characters. To compare two suffixes by their first 2k characters, look at:

These two ranks describe the first k and second k characters of the suffix starting at i. Two suffixes can be compared by these two pairs of ranks in O(1), no character comparison needed.

The diagram below illustrates the doubling.

Suffixes that fall off the end of the string (when i + k >= n) are padded with rank -1, treated as smaller than any real character. This is the lexicographic convention: shorter strings come first when one is a prefix of the other.

Implementation

The implementation has two helper structures: a pair (rank[i], rank[i + k]) for each suffix, and a sort by that pair. After each pass we reassign ranks based on the sorted order, breaking ties only when the pair is identical.

Three implementation details worth pointing out:

Faster Variants

Several construction algorithms give better asymptotic complexity than O(n log^2 n). They are mentioned here for completeness; for interview-sized inputs (n up to about 10^6) the simpler rank-doubling above is fast enough.

A working SA-IS implementation is roughly 200 lines and is best learned from a clean reference (Yuta Mori's C implementation is the canonical one). For interview or competitive-programming inputs, rank doubling is sufficient.

The LCP array is what makes the suffix array genuinely powerful for substring problems. Given a suffix array SA of S, the LCP array LCP has length n - 1 (or n, with LCP[0] = 0 by convention), where:

LCP[i] = the length of the longest common prefix of the suffixes at SA[i - 1] and SA[i].

For S = "banana":

The maximum value in the LCP array is the length of the longest substring that appears at least twice in S. For "banana", that maximum is LCP[2] = 3, corresponding to "ana", which appears at indices 1 and 3.

Why Adjacent Suffixes Carry All the LCP Information

This is the key property: for any two suffixes (not just adjacent ones), the LCP equals the minimum of all LCP values between them in the sorted order.

LCP(SA[i], SA[j]) = min(LCP[i + 1], LCP[i + 2], ..., LCP[j]), for i < j.

So the LCP array between adjacent suffixes captures everything you need to answer LCP queries for any pair, by combining with a range-minimum structure (sparse table, segment tree, or even a sqrt decomposition).

Building the LCP array naively (comparing each pair of adjacent sorted suffixes character by character) costs O(n^2). Kasai's algorithm builds it in O(n) by walking through the suffixes in original-string order, not sorted order.

The insight: if the suffix starting at position i has LCP h with its neighbor in the sorted array, then the suffix starting at position i + 1 has LCP at least h - 1 with its own sorted neighbor.

Why? The suffix at i + 1 is the suffix at i with its first character removed. If positions i and its sorted-neighbor share h characters, dropping one character from the front still leaves h - 1 matching characters between i + 1 and its sorted-neighbor. The amortized argument is: across all positions, h decreases by at most 1 each iteration and increases by at most n total, so the total work is O(n).

Implementation

The trace of Kasai's on "banana" matches the example table above. The total number of character comparisons is bounded by 2n: each successful comparison increments h, which can grow at most n times total; each failure ends an inner loop iteration, of which there are at most n.

Pattern Matching: O(m log n) per Query

Given a sorted suffix array, finding all occurrences of a pattern P of length m is a binary search problem. Pattern P is a prefix of some suffix S[i..n-1] if and only if i is an occurrence of P in S. So:

Each binary-search step compares P (m characters) with one suffix, so the total per query is O(m log n). Multiple-pattern matching is the same cost per pattern.

For a single fixed text matched against many patterns, this is unbeatable. For matching one pattern in one text, KMP is simpler and faster because suffix array construction itself dominates the cost.

Longest Repeated Substring

The longest substring that appears at least twice in S is the substring corresponding to the maximum entry in the LCP array.

For "banana", the answer is "ana" (length 3, starts at index 1 or 3).

Number of Distinct Substrings

The total number of substrings of S is n * (n + 1) / 2. The number of duplicate substrings is the sum of the LCP array. So:

Number of distinct substrings = n * (n + 1) / 2 - sum(LCP)

For "banana": 6 * 7 / 2 - (1 + 3 + 0 + 0 + 2) = 21 - 6 = 15 distinct substrings.

Longest Common Substring of Two Strings

Concatenate S and T with a separator that does not appear in either: U = S + '#' + T. Build the suffix array and LCP array of U. The longest common substring of S and T is the maximum LCP[i] such that SA[i - 1] and SA[i] come from different sides of the separator.

The same trick extends to k strings, using k different separators or one separator plus a "source" tracking array.

Substring Comparison in O(1) After Preprocessing

With a sparse table built over the LCP array, the LCP between any two suffixes is min(LCP[i + 1..j]) in O(1) per query. Combined with rank lookup, comparing any two substrings of S takes O(1).

This speed-up applies to problems that need many substring comparisons: longest common substring in queries, palindrome substring queries, smallest cyclic rotation, and similar.

Practical guidance:

Time Complexity

Space Complexity

O(n) for the suffix array, rank array, and LCP array together. The constant factor is much smaller than a suffix tree, which is the main reason suffix arrays are preferred in production systems.