{"ID":6267246,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-13T01:02:08.706470581Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08566","arxiv_id":"2607.08566","title":"Algorithms and Indexing Lower Bounds for Variable String Matching","abstract":"A \\emph{generalized degenerate string} (GD) is a sequence $T=T_1\\dots T_n$ of nonempty finite sets of strings, called \\emph{segments}, such that all strings in a segment have the same length. Given a solid pattern $P$, GD string matching asks whether $P$ occurs in $T$. Ascone et al. (WABI 2024) identified this as the main remaining boundary case in the fine-grained complexity of pattern matching on variable strings, between variants with near-linear algorithms and those with SETH-based quadratic lower bounds. We give a $\\tilde{\\mathcal O}(N\\sqrt m)$-time algorithm, where $N$ is the total size of $T$ and $m=|P|$, placing GD matching on the subquadratic side of this boundary. We also study indexing. For elastic-degenerate strings (ED), which drop the equal-width restriction, Gibney (SPIRE 2020) obtained $\\mathcal O(nm^2)$ query time after linear preprocessing. We adapt this index to GD strings, obtaining $\\mathcal O(nm)$ query time. Conversely, under SETH, we rule out GD indices with polynomial preprocessing and query time $\\mathcal O(n^{1-\\varepsilon}m^{\\mathcal O(1)}+m)$. Under the $k$-Clique conjecture, we further rule out combinatorial GD indices with query time $\\mathcal O(n^{\\mathcal O(1)}m^{1-\\varepsilon}+m)$, and combinatorial ED indices with query time $\\mathcal O(n^{\\mathcal O(1)}m^{2-\\varepsilon})$, matching the quadratic dependence on $m$ in Gibney's upper bound. Finally, under the OMv conjecture, we show that, after polynomial preprocessing of a string set and a pattern, active-prefix queries on a bit vector of length $m$ cannot be answered in $\\mathcal O(m^{2-\\varepsilon})$ time. Since these queries are the standard bottleneck in ED matching, improving indexed ED queries below $\\mathcal O(n^{\\mathcal O(1)}m^2)$ would require both non-combinatorial techniques and an approach that avoids using active-prefix queries as the main bottleneck.","short_abstract":"A \\emph{generalized degenerate string} (GD) is a sequence $T=T_1\\dots T_n$ of nonempty finite sets of strings, called \\emph{segments}, such that all strings in a segment have the same length. Given a solid pattern $P$, GD string matching asks whether $P$ occurs in $T$. Ascone et al. (WABI 2024) identified this as the m...","url_abs":"https://arxiv.org/abs/2607.08566","url_pdf":"https://arxiv.org/pdf/2607.08566v1","authors":"[\"Estéban Gabory\"]","published":"2026-07-09T14:56:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}