Skip to content

Strings -> Suffix Array And LCP

Sorted suffix views and LCP arrays for substring order, uniqueness, and offline pattern search.

  • Topic slug: strings/suffix-array-lcp
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 2
  • Repo companion pages: 0
  • Curated external problems: 9

Microtopics

  • doubling
  • radix-sort
  • kasai
  • lcp-array
  • substring-order
  • pattern-search

Learning Sources

Source Type
cp-algorithms suffix array Reference
Princeton suffix arrays Course
USACO Guide suffix array Reference

Practice Sources

Source Type
Library Checker Suffix Array Practice
Library Checker LCP Array Practice
CSES Distinct Substrings Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Distinct Substrings CSES Medium Suffix-Array Counting; Suffix Processing LCP Array Distinct Substrings; Counting; Suffix-Structure One of the standard suffix-array + LCP counting problems.
Repeating Substring CSES Medium Suffix-Array Maximization; Substring Search LCP Array Repetition; Longest-Repeat; Binary-Search; Suffix-Structure Longest repeated substring is a canonical LCP application.
lcp_array Library Checker Medium Suffix-Array - - Kasai; Adjacent-Suffixes Natural companion to suffix array construction.
longest_common_substring Library Checker Medium Suffix-Array - - Two-Strings; Common-Substring A very standard SA+LCP application problem.
suffix_array Library Checker Medium Suffix-Array, String-Indexing - - Lexicographic-Order; Core Direct suffix-array construction benchmark from the official judge.

Challenge

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Inverse Suffix Array CSES Hard - Construction; Consistency Checking Suffix Array Semantics Suffix Array; Construction; Inverse Problems A reverse-engineering task that deepens suffix-array understanding.
String Transform CSES Hard - Construction; Inverse Transform Suffix Array; Sorted Rotations Suffix Array; Burrows-Wheeler Transform; Reconstruction This is a direct BWT-style inverse transform problem.
Substring Order I CSES Hard Suffix-Array, Lexicographic-Order K-Th Selection; Suffix Processing LCP Array Order Statistics; Kth-Substring; Ranking Selecting the k-th substring is a strong suffix-array/LCP exercise.
Substring Order II CSES Hard - K-Th Selection; Suffix Processing Suffix Array; LCP Array Suffix Array; Order Statistics Same core machinery as Substring Order I, but on all substrings.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
DISTINCTSUBSTRINGS Distinct Substrings secondary medium suffix automaton construction; clone states; state contribution counting Note Code
REPEATINGSUBSTRING Repeating Substring primary medium suffix array doubling; kasai lcp; maximum adjacent lcp Note Code

Regeneration

python3 scripts/generate_problem_catalog.py