Papers › Longest Common Extensions with Wildcards: Trade-off and Applications
Longest Common Extensions with Wildcards: Trade-off and Applications
Gabriel Bathie, Itai Boneh, Panagiotis Charalampopoulos, Jonas Ellert, Tatiana Starikovskaya
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We study the Longest Common Extension (LCE) problem in a string containing wildcards. Wildcards (also called "don't cares" or "holes") are special characters that match any other character in the alphabet, similar to the character "?" in Unix commands or "." in regular expression engines. We consider the problem parametrized by G, the number of maximal contiguous groups of wildcards in the input string. Our main contribution is a simple data structure for this problem that can be built in O(n (G/t) logn) time, occupies O(nG/t) space, and answers queries in O(t) time, for any t ∈[1, G]. Up to the O(logn) factor, this interpolates smoothly between the data structure of Crochemore et al. [JDA 2015], which has O(nG) preprocessing time and space, and O(1) query time, and a simple solution based on the "kangaroo jumping" technique [Landau and Vishkin, STOC 1986], which has O(n) preprocessing time and space, and O(G) query time. By establishing a connection between this problem and Boolean matrix multiplication, we show that our solution is optimal, up to subpolynomial factors, among combinatorial data structures when G = Ω(n^ϵ) under a widely believed hypothesis. In addition, we develop a simple deterministic combinatorial algorithm for sparse Boolean matrix multiplication. We further establish a conditional lower bound for non-combinatorial data structures, stating that O(nG/t⁴) preprocessing time (resp. space) is optimal, up to subpolynomial factors, for any data structure with query time t for a wide range of t and G, assuming the well-established $\textsf{3SUM}$ (resp. $\textsf{Set-Disjointness}$) conjecture. Finally, we show that our data structure can be used to obtain efficient algorithms for approximate pattern matching and structural analysis of strings with wildcards.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections