Faangprep Logo
Log inStart free
Browse curriculum

Suffix Array

A Suffix Array is a sorted array of all suffixes of a string, used for efficient string matching and analysis.

A suffix array is every suffix of a text in sorted order; the LCP array is how much each neighbouring pair shares. Kasai's finds all of it in one pass over the text by carrying a single number, k, from each suffix to the next. Switch to NAIVE to see what finding each pair from scratch costs.

SUFFIXES

r

SA

lcp

suffix

0

banana

1

anana

2

nana

3

ana

4

na

5

a

k

0

Compares

0

With carry

5

 

The 6 suffixes of "banana", in the order they start. Every substring of the text is the prefix of one of them — which is why putting these in order answers so many questions about the text.

Next

Sorted. Row r now holds SA[r], the start of the r-th smallest suffix, and that array is the suffix array. What is left is lcp[r]: how many characters row r shares with the row directly below it.

Text

Match length

Intuition

The Problem: Finding patterns in a huge text (like the human genome) is slow if we scan linearly.

The Solution: If we create all possible suffixes of the text and sort them lexicographically, we can use Binary Search to find any substring in O(M log N) time.

Combined with the LCP (Longest Common Prefix) array, it solves complex problems like finding the longest repeated substring.

Concept

Structure:

  • Suffixes: Substrings starting from index i to the end.
  • Array: An array of integers representing the starting indices of these suffixes, sorted alphabetically.

Example: for "banana"

  • Suffixes: banana, anana, nana, ana, na, a
  • Sorted: a, ana, anana, banana, na, nana
  • Suffix Array: [5, 3, 1, 0, 4, 2]

How it Works

  1. Generate: List all suffixes of string S.
  2. Sort: Sort them lexicographically. The indices of the sorted suffixes form the Suffix Array SA.
  3. LCP Construction: (Optional) Compute the Longest Common Prefix between adjacent suffixes in the sorted array to enable advanced queries.
  4. Search: Use binary search on the suffix array to locate pattern P.

Step-by-Step Breakdown

1. Naive Construction: Create array of objects (index, string), sort strings, iterate to extract indices. O(N^2 log N).
2. Optimized Construction: Use prefix doubling (sorting by 1 char, then 2, 4, 8...). O(N log^2 N) or O(N log N).
3. Building LCP:
    - Use Kasai's Algorithm O(N).
    - Maintains an invariant relation between LCP of suffix[i] and suffix[i+1].

When to Use

  • Finding longest repeated substring.
  • Finding longest common substring of two strings.
  • Counting unique substrings.
  • Fast substring search in static text.

When NOT to Use

  • Dynamic text (insertions/deletions) -- Suffix Trees or Arrays are expensive to rebuild.
  • Simple pattern matching where KMP/Z-Algo suffices.

How to Identify

"Multiple pattern queries on static text", "Longest repeated substring", "Lexicographically kth substring".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Z-Algorithm

Next

Bitmask DP

Frequently Asked Questions

What does the suffix array store?

The starting indices of every suffix of the string, ordered lexicographically. For banana it is [5, 3, 1, 0, 4, 2], which is the sorted order a, ana, anana, banana, na, nana.

Why not just sort the suffixes directly?

Comparing two suffixes can cost O(N) characters, making a naive sort O(N² log N). Doubling constructions sort by the first 2^k characters using the previous round of ranks, which compares in O(1) and reaches O(N log N).

How does it answer pattern queries?

Every occurrence of a pattern is a prefix of some suffix, and those suffixes sit contiguously in sorted order. Two binary searches locate that range in O(M log N), and its size is the number of occurrences.