ExtendedSource checked

Suffix Array Search

Finds substrings by binary searching a sorted array of suffixes.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pattern Matching
Difficulty: Advanced
Family: Suffix Index Search
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready

Overview

Suffix Array Search indexes every suffix of a text in sorted order, then searches patterns by comparing against suffix prefixes.

Core Concepts

pattern comparisonstring sequencesuffix orderingsorted search spacesuffix index searchsequence scanpattern statematch verification

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 Suffix Array Search when you need to store sorted suffix positions.
Use it for full-text search with inputs like text.
Use it when exact, fuzzy, or structured patterns must be found in sequences.
Use it when the Suffix Index Search tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the input cannot be kept sorted cheaply.
Avoid it when preprocessing cost is larger than a one-off simple scan.
Avoid it when the required output is not match range or positions.

What It Does

Stores sorted suffix positions
Binary searches suffix prefixes for a pattern

Use Cases

Full-text search
Substring queries
Genome sequence search

Inputs

Text
Pattern
Suffix array

Outputs

Match range or positions

Key Formulas (1)

Binary search comparison

compare(pattern, text starting at suffix_array_[mid])

compare(pattern, text starting at suffix_array[mid])

Uses sorted suffix positions to decide which half of the suffix array to keep searching.

Pseudocode

1.Build or load the suffix array
2.Binary search for the first suffix with the pattern prefix
3.Binary search for the end of the matching range
4.Return suffix positions in that range

Canonical Example

Input: text = 'abracadabra', pattern = 'abra'
Output: matches at positions [0, 7]
Explanation: Suffix Array Search: The algorithm scans the sequence and reports where the pattern appears.

Implementation Notes

Keep the input contract explicit: Text; Pattern; Suffix array.
Use this step as the implementation spine: Build or load the suffix array.
Then preserve the next state change: Binary search for the first suffix with the pattern prefix.
Decide whether indexes mean bytes, code units, characters, or tokens.
Test overlapping matches, empty patterns, repeated characters, and no-match inputs.

Common Pitfalls

Extra longest-common-prefix data can speed repeated suffix-array searches.
Indexing by bytes instead of characters can break text with multibyte characters.
Reporting a match before verifying collisions, boundaries, or full-pattern alignment.
Returning match range or positions without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Array Partition & Ordering Trace

Show a pattern narrowing a range in sorted suffixes.

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Step 1 of 4: Build or load the suffix array

sorted-suffixes

Notes

Suffix Array Search operates in O(m log n) time and O(n) space within the Suffix Index Search family. Key governing relation: compare(pattern, text starting at suffix_array[mid]). Often compared with Suffix Array and Suffix Tree.