Skip to content
Algorithm Atlas
Data StructuresAll categories
CoreSource checked

Suffix Array

Stores suffix starting positions in lexicographic order for compact string indexing.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Advanced
Family
String Index
Tier
Core
Status
Verified
Review
Source Checked
Sources
3
Formulas
1
Relationships
9
Code example
Ready
Visualization
Ready

Overview

A suffix array supports binary search over suffixes and often pairs with LCP arrays for efficient string queries.

Core Concepts

lexicographic suffixbinary searchlcp arraystring index

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(m log n)

Average

O(m log n)

Worst

O(m log n)

Space

O(n)

When to Use

  • Use when fast lookup needs lexicographic suffix.
  • Use when the input matches the assumptions behind string Index.

When Not to Use

  • Avoid when the operation mix does not benefit from the structure's maintenance cost.
  • Avoid when a simpler algorithm gives the required result with less setup.

What It Does

  • Stores suffix starting positions in lexicographic order for compact string indexing
  • Uses lexicographic suffix and binary search to guide the work.
  • Produces stored structure.

Use Cases

  • Fast lookup
  • Maintaining ordered data
  • Representing graphs or spatial data

Inputs

  • Items
  • Keys or indexes
  • Operations to support

Outputs

  • Stored structure
  • Query results
  • Updated state

Key Formulas (1)

Suffix order

text[suffixarray[i]…] ≤ text[suffixarray[i+1]…]
text[suffix_array[i]..] <= text[suffix_array[i+1]..]

Defines the sorted order stored by the suffix array.

Pseudocode

  1. 1.Prepare the inputs and state needed for Suffix Array.
  2. 2.Apply the lexicographic suffix step while the stopping condition has not been met.
  3. 3.Update intermediate state and discard invalid candidates.
  4. 4.Return stored structure.

Canonical Example

Input
text = "banana"
Output
suffix starts sorted as [5, 3, 1, 0, 4, 2]
Explanation
The suffixes "a", "ana", "anana", "banana", "na", and "nana" are ordered lexicographically by start index.

Implementation Notes

  • Store start indexes, not copied suffix strings, in the final array.
  • Define sentinel ordering if the construction algorithm requires one.
  • Pair with an LCP array for many substring-query workflows.

Common Pitfalls

  • Forgetting whether a sentinel character is included.
  • Mixing suffix start positions with ranks.
  • Using suffix arrays without an LCP structure for repeated range queries that need prefix lengths.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show the structure layout and how operations move through or update it.

Suffix Array mechanism walkthrough step 1 of 4suvwxt
Step 1 of 4: Prepare the inputs and state needed for Suffix Array.
data-structures-mechanism

Notes

Suffix Array should be used with the assumptions and tradeoffs of string Index in mind.

Sources (3)

What each reference supports for this entry.

Algorithms on Strings, Trees, and Sequences

Book

String algorithms reference for Suffix Array's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.

Open source

Introduction to Algorithms (CLRS)

Book

Textbook support for Suffix Array's algorithm family, complexity framing, and standard implementation concepts.

Open source

Manber-Myers Suffix Arrays

Paper

Original reference introducing suffix arrays as a space-efficient string index.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
AlternativesSuffix Automaton LCS

Pattern Matching · Core

A suffix array with LCP values can also find longest common substrings after combining the strings.

Compare with this
Alternative toSuffix Tree

Data Structures · Core

Suffix arrays are more compact than suffix trees for many workloads.

Compare with this
AlternativesFM-Index Search

Pattern Matching · Specialized

FM-Index Search offers a different exact, approximate, or indexed matching strategy than Suffix Array.

Compare with this
Used bySuffix Array Search

Pattern Matching · Extended

Suffix array search uses the sorted suffix array as its index.

Compare with this
Approximated byShortest Common Superstring Greedy

Pattern Matching · Core

Shortest Common Superstring Greedy gives an approximate or heuristic answer for the problem family associated with Suffix Array.

Compare with this
Conceptual neighborsKarp-Miller-Rosenberg String Matching

Pattern Matching · Specialized

KMR naming is related to ranking substrings in suffix-array construction.

Compare with this

Relationships

View full relationship page
Used bySuffix Array Search

Suffix array search uses the sorted suffix array as its index.

Alternative toSuffix Tree

Suffix arrays are more compact than suffix trees for many workloads.

Related Algorithms

Suffix Array SearchSuffix TreeSuffix AutomatonBurrows-Wheeler Transform

Tags

Data StructureStringsSuffix IndexSorting