# Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

Preprint · Dominik Kempa, Tomasz Kociumaka

- Archive id: arxiv:2608.19123
- Published: 2026-08-19
- arXiv: https://arxiv.org/abs/2608.19123
- Source URL: https://arxiv.org/abs/2608.19123
- PDF: https://arxiv.org/pdf/2608.19123
- Provenance: arxiv

## Abstract

For a text $T\\in\[0..σ)^n$ with $2\\leqσ\\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\\logσ)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\\log\\log n/\\log\\logσ)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\\logσ)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $Θ(\\log n)$-bit cells has worst-case query time $Ω(\\log\\log n/\\log\\log\\log n)$. Construction is a second challenge: linear time can take $Θ(\\log\_σ n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $Θ(\\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\\min(1,\\logσ/\\sqrt{\\log n}))$ time. For $B\\geq2$, the first family uses $O(n\\logσ(1+\\log\_B\\log\_σn))$ bits and has query time $O(B(1+\\log\_B\\log\_σn))$, whereas the second uses $O(Bn\\logσ(1+\\log\_B\\log\_σn))$ bits and has query time $O(1+\\log\_B\\log\_σn)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\\geq(\\log\\log n)^{Ω(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\\sqrt{\\log n})$ would yield an equally fast Dictionary Matching algorithm.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.