DSA DSA In Depth
0%
From-Scratch Build

Suffix Array (Prefix-Doubling), Kasai LCP & RMQ Substring Index

A full-text Suffix Array index built via prefix-doubling, paired with Kasai linear-time LCP array construction, O(1) Sparse Table RMQ queries, binary-search pattern matching, and distinct substring counting.

~50 min Advanced Lessons: Suffix Arrays: Manber-Myers O(N log N) Prefix Doubling & SA-IS O(N) Overview, Suffix Arrays: Manber-Myers O(N log N) Prefix Doubling & SA-IS O(N) Overview, Suffix Automaton (SAM / DAWG): endpos Equivalence Classes & State Transitions, Disjoint & Standard Sparse Tables: O(1) Idempotent Range Minimum Query (RMQ), The Z-Algorithm: Linear-Time [L, R] Z-Box Maintenance & Pattern Matching, Aho-Corasick Automaton: Trie + BFS Failure Links + Dictionary Suffix Links
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Prefix-Doubling Construction

A Suffix Array $\text{SA}[0..n-1]$ is the lexicographically sorted permutation of all starting indices of suffixes of $T$. Rather than comparing suffixes character-by-character ($O(n^2 \log n)$), Manber & Myers prefix doubling sorts suffixes by their $2^k$-length prefixes using two $2^{k-1}$-length ranks computed in the previous round:

$$\text{key}_k(i) = (\text{rank}_{k-1}[i],\; \text{rank}_{k-1}[i + 2^{k-1}])$$

Kasai's $O(n)$ LCP Theorem

Let $\text{LCP}[r]$ be the length of the longest common prefix between adjacent sorted suffixes $\text{SA}[r]$ and $\text{SA}[r+1]$. Kasai et al. (2001) proved that if suffix $T[i..]$ has common prefix $h$ with its successor in $\text{SA}$, then the next suffix in text order $T[i+1..]$ has common prefix at least $h - 1$ with its own successor in $\text{SA}$. Since $h$ is decremented at most $n$ times and incremented at most $n$ times, the entire LCP array is built in $O(n)$ time.

Curriculum Connections

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Prefix-Doubling Suffix Array Construction

  • Core Mechanical Concept: Prefix-Doubling Suffix Array Construction
  • Target Module: index.js (Step1)
  • Engineering Specification: Implement _buildSuffixArray() by sorting suffix indices $0..n-1$ in rounds $k = 1, 2, 4, \dots$ using the 2-tuple key (rank[i], rank[i + k]) and terminating early once all ranks are distinct.
  • Verification Invariant: verifies Step 1: Prefix-Doubling Suffix Array Construction

Step 2: Kasai Linear-Time O(n) LCP Construction

  • Core Mechanical Concept: Kasai Linear-Time O(n) LCP Construction
  • Target Module: index.js (Step2)
  • Engineering Specification: Implement _buildKasaiLCP() in text order $i = 0..n-1$. Because stripping the leading character from two suffixes reduces their common prefix by at most 1 (h = Math.max(0, h - 1)), total character comparisons are bounded by $2n$.
  • Verification Invariant: verifies Step 2: Kasai Linear-Time O(n) LCP Construction

Step 3: Sparse Table RMQ for O(1) Arbitrary Suffix LCP

  • Core Mechanical Concept: Sparse Table RMQ for O(1) Arbitrary Suffix LCP
  • Target Module: index.js (Step3)
  • Engineering Specification: Build a Sparse Table over this.lcp so lcpOfSuffixes(i, j) answers $\min_{r=\text{rank}[i]}^{\text{rank}[j]-1} \text{LCP}[r]$ in $O(1)$ time.
  • Verification Invariant: verifies Step 3: Sparse Table RMQ for O(1) Arbitrary Suffix LCP

Step 4: Pattern Binary Search & Distinct Substrings

  • Core Mechanical Concept: Pattern Binary Search & Distinct Substrings
  • Target Module: index.js (Step4)
  • Engineering Specification: Implement search(pattern) via lower/upper-bound binary search on this.sa, and countDistinctSubstrings() via $\frac{n(n+1)}{2} - \sum \text{LCP}[i]$.
  • Verification Invariant: verifies Step 4: Pattern Binary Search & Distinct Substrings

Asymptotic & Memory Layout Guarantees

  • Category: Strings & Automata
  • Difficulty: Advanced (~50 minutes)
  • Key Architectural Highlights:
    • Prefix-doubling O(n log n) suffix array construction with rank pair comparison
    • Kasai linear-time O(n) LCP array construction exploiting h[i] >= h[i-1] - 1
    • O(1) Longest Common Prefix of arbitrary suffixes via Sparse Table RMQ and distinct-substring counting
  • Tags & Primitives: Suffix Array, Prefix Doubling, Kasai LCP Array, Sparse Table RMQ, Substring Search

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.