CS Paper Radar

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
theory similarity 0.72
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.

0.44

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

cs.DS ·2026-08-19 ·Dominik Kempa, Tomasz Kociumaka
publishedtheory similarity 0.71
Abstract · Full version of a SODA 2027 paper

For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $Θ(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $Ω(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.

0.48

The Inverse Lyndon Array

cs.DS cs.FL ·2026-09-20 ·Clelia De Felice, Pietro Negri, Manuel Sica, Rocco Zaccagnino, Rosalba Zizza
theory similarity 0.67
Abstract · 21 pages, no figures, SOFSEM conference

The Lyndon array stores, at each position of a word, the length of the longest Lyndon factor starting at that position and plays an important role in combinatorics on words, for example, in the construction of fundamental data structures such as the suffix array. In this paper, we introduce the Inverse Lyndon array, the analogous structure for inverse Lyndon words, namely words that are lexicographically greater than all their proper nonempty suffixes. Unlike standard Lyndon words, inverse Lyndon words may have non-trivial borders, which introduces a genuine theoretical difficulty. We show that the Inverse Lyndon array can be characterized in terms of the next greater suffix array together with a border-correction term, and we prove that this correction coincides with a longest common extension (LCE) value. Building on this characterization, we adapt the nearest-suffix framework underlying Ellert's linear-time construction of the Lyndon array to the inverse setting, obtaining an O(n)-time algorithm for general ordered alphabets. Finally, we show that the Inverse Lyndon array can also be used to reconstruct the canonical inverse Lyndon factorization in linear time.

0.27

Internal Queries for Maximal Closed Substrings

cs.DS ·2026-11-08 ·Simone Faro, Francesco Pio Marino, Arianna Pavone
theory similarity 0.60
Abstract

Searching for repetitions inside a selected part of a text raises a subtle boundary problem: removing neighbouring characters can create new maximal answers. We study this effect for maximal closed substrings (MCSs). A string is closed if it is a single letter or has a nonempty proper prefix occurring exactly twice, as its prefix and suffix; a closed occurrence is maximal if neither available one-character extension is closed. Previous work established $O(n\log n)$ bounds on the global MCS families of a length-$n$ text and developed enumeration algorithms. Internal queries instead ask for the MCSs of a chosen substring, with maximality evaluated inside that substring. Separating boundary occurrences from interior ones gives an $O(n\log n)$-word index that reports the $c$ answers in $O(\log n+c)$ time and supports counting and longest queries in $O(\log n)$ time. Our main result reduces reporting space to $O(n)$ words, with $O((c+1)\log^{1+\varepsilon} n)$ query time and $O(n\log^{1+\varepsilon} n)$ construction time for any fixed $\varepsilon>0$. Thus, after preprocessing, reporting requires no additive scan of the queried substring, which is particularly useful for long queries with few answers. Independently, we prove that at most $3(s-1)$ MCS occurrences of any length-$s$ substring cross a fixed gap between consecutive characters, with maximality evaluated inside that substring. The same bound holds for global MCSs contained in a length-$s$ block. A family over two letters attains $\lfloor(s-1)/2\rfloor$ crossings for every $s\ge3$, showing that the linear order of this local density bound is optimal.

0.10

Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation

cs.DS ·2026-11-03 ·Nick Fischer, Yael Kirkpatrick, Vasileios Nakos
similarity 0.60
Abstract

\emph{Text-to-Pattern Hamming Distances} is one of the most studied problems in string algorithms: given a text $T$ of length~$n$ and a pattern~$P$, the task is to compute the Hamming distance between~$P$ and every length-$|P|$ substring of~$T$. As exact algorithms have been stuck at time~$\tilde O(n^{3/2})$ for decades, a long line of work has turned to the $(1+ε)$-approximate version of the problem. Milestones include Karloff's $\tilde O(ε^{-2} n)$-time algorithm [IPL '93], followed by randomized improvements to $\tilde O(ε^{-1} n)$ by Kopelowitz and Porat [FOCS '15] and recently to $\tilde O(ε^{-0.915} n)$ by Chan, Jin, Vassilevska W., and Xu [FOCS '23]. In this work, we significantly improve this bound to $\tilde O(ε^{-2/3} n)$, using a considerably simpler algorithm. Our algorithm follows the framework of Chan, Jin, Vassilevska W., and Xu, which reduces the problem to a variant of 3SUM that we call \emph{Sumset Estimation}. We solve Sumset Estimation optimally (up to logarithmic factors) by replacing their matrix multiplication techniques with ideas from sparse recovery. Specifically, we adapt the classic Count Sketch by replacing its random signs with random complex roots of unity---a simple idea that may find further applications for other additive problems. Finally, we give evidence that our running time might in fact be optimal: we show that the $ε^{-2/3}$ dependence is \emph{best possible} for a certain natural class of algorithms, including ours and all previous algorithms.

0.50

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.59
Abstract

We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

0.53

An $n^{8/5+o(1)}$-Time $Ω(λ^3)$-Approximation for Longest Common Subsequence

cs.DS ·2026-09-25 ·Zhao Song
similarity 0.59
Abstract

Let $λ$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω(λ^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω(λ^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.

0.15

Longest Unbordered Factors in Linear Time

cs.DS ·2026-11-09 ·Takuya Mieno
similarity 0.57
Abstract

A border of a string is a nonempty proper prefix that is also a suffix. A string is unbordered if it has no border. The length of a longest unbordered factor is closely related to the smallest period of the string. While the smallest period can be computed in linear time, the best previously known algorithm for computing a longest unbordered factor takes $O(n \log n)$ worst-case time for a string of length $n$. Whether this computational problem can be solved in worst-case linear time has remained open. In this paper, we resolve this open problem for integer alphabets of size $n^{O(1)}$ by presenting an algorithm that computes all occurrences of longest unbordered factors in $O(n)$ worst-case time. Our algorithm uses a combinatorial property of longest unbordered factors and scans the input string in both directions to capture all occurrences achieving the global maximum without computing the local maximum at every starting position.

0.28