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

For a text $T\in [\mathrm{0..}\sigma {)}^n$ with $2\le \sigma \le 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 \sigma )$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log \log n\mathrm{/}\log \log \sigma )$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\log \sigma )$ 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 $\mathrm{\Theta }(\log n)$-bit cells has worst-case query time $\mathrm{\Omega }(\log \log n\mathrm{/}\log \log \log n)$. Construction is a second challenge: linear time can take $\mathrm{\Theta }({\log }_{\sigma }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 $\mathrm{\Theta }(\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 \sigma \mathrm{/}\sqrt{\log n}))$ time. For $B\ge 2$, the first family uses $O(n\log \sigma (1+{\log }_B{\log }_{\sigma }n))$ bits and has query time $O(B(1+{\log }_B{\log }_{\sigma }n))$, whereas the second uses $O(Bn\log \sigma (1+{\log }_B{\log }_{\sigma }n))$ bits and has query time $O(1+{\log }_B{\log }_{\sigma }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\ge (\log \log n{)}^{\mathrm{\Omega }(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n\mathrm{/}\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.