Algorithms and Indexing Lower Bounds for Variable String Matching

Est\'eban Gabory

REVIEW 2 major objections 4 minor 24 references

Algorithms and Indexing Lower Bounds for Variable String Matching

T0 review · 2 major / 4 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Generalized-degenerate string matching admits a classical Õ(N√m)-time algorithm, placing it on the subquadratic side of the variable-string complexity boundary.

desk verdict Clean classical Õ(N√m) algorithm that settles the last open GD case in the Ascone taxonomy, plus solid combinatorial indexing barriers. read the letter →

arxiv 2607.08566 v1 pith:LJ3SMSNQ submitted 2026-07-09 cs.DS

Estéban Gabory This is my paper · ORCID

classification cs.DS MSC 68W3268Q25

keywords generalizeddegeneratestringselastic-degeneratepatternmatchingfine-grainedcomplexitytextindexingk-cliqueconjectureOMv

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Variable strings range from simple degenerate strings to fully elastic-degenerate texts; Ascone et al. left generalized-degenerate (GD) strings—the intermediate case in which every segment contains equal-length strings whose common length may vary—as the last open boundary between near-linear algorithms and SETH-hard quadratic lower bounds. This paper supplies a classical algorithm that decides whether a solid pattern of length m occurs in a GD text of total size N in Õ(N√m) time, settling the question on the subquadratic side. The same techniques yield a linear-preprocessing index answering GD queries in O(nm) time. Matching combinatorial lower bounds under the k-clique conjecture show that the linear dependence on m for GD and the quadratic dependence for elastic-degenerate strings are essentially optimal for combinatorial methods, while an OMv reduction proves that the active-prefix primitive used by existing elastic-degenerate algorithms cannot be improved below quadratic time.

What carries the argument

Heavy-light decomposition of the strings of each fixed width according to their frequency in the pattern: heavy strings are handled by FFT convolution of binary indicator arrays; light strings are handled by direct reporting of their few occurrences into the candidate array.

What would settle it

A combinatorial algorithm answering GD queries in O(n^{O(1)} m^{1-ε}+m) time after polynomial preprocessing, or an explicit counter-example showing that the adapted Bringmann-style gadgets fail to preserve k-clique structure when all strings inside a segment must have identical length.

Watch

Extended reading notes

Core claim

A solid pattern of length m can be matched against a generalized-degenerate text of total size N in Õ(N√m) time by computing, for every candidate starting column, the exact number of fully covered segments that the pattern matches and comparing that count with the number of segments the alignment spans.

Load-bearing premise

The combinatorial lower bounds stand only if the k-clique conjecture is true and if the string gadgets correctly encode clique extensions under the equal-width constraints of GD strings.

Editorial extensions

If this is right

GD pattern matching now belongs with the subquadratic family of variable-string problems rather than the SETH-hard family.
GD texts admit an index with linear preprocessing and O(nm) query time.
No combinatorial GD index can improve the pattern-length dependence below linear under the k-clique conjecture.
No combinatorial ED index can improve the pattern-length dependence below quadratic under the same conjecture.
Active-prefix queries require essentially quadratic time after polynomial preprocessing under OMv, blocking straightforward improvements to existing ED indexes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The heavy-light-plus-convolution technique may adapt directly to founder graphs, the still-open graph analogue of GD strings.
Matching the quantum Õ(√(Nmn)) bound classically would likely need algebraic rather than purely combinatorial methods.
Beating the ED quadratic barrier without abandoning active-prefix queries would require genuinely non-combinatorial techniques.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main result is the first classical subquadratic algorithm for generalized-degenerate pattern matching: Õ(N√m) via heavy/light classification of equal-width strings, FFT convolution on the heavy ones, direct occurrence counting on the light ones, and a Cauchy–Schwarz sum over widths. That places GD firmly on the subquadratic side of the Ascone et al. dichotomy and answers the open classical question they left. The four-case decomposition (easy/suffix/prefix/anchor) is standard, but the anchor handling is new and carefully written.

The indexing side is also useful. Adapting Gibney’s ED index to GD gives O(nm) queries after linear preprocessing; the equal-width restriction makes the Aho–Corasick and suffix-tree work clean. The combinatorial lower bounds under k-clique (m^{1-ε} for GD, m^{2-ε} for ED) reuse Bringmann-style gadgets and look correct; they match the known upper bounds in the combinatorial regime. The OMv lower bound for indexed active-prefix queries is a clean re-reading of Bernardini et al. and explains why beating O(n^{O(1)}m^{2}) for ED indexing will need both algebraic techniques and a different bottleneck.

Soft spots are minor. No code or experiments, but this is pure theory and the proofs are self-contained. The paper itself flags a possible gap in Gibney’s earlier SETH claim for the m^{1-ε} ED barrier and does not overclaim there. The gadgets assume the usual clique-conjecture setting; if those fail the barriers fall, but that is the standard risk for this style of result.

This is for people working on fine-grained string algorithms or pangenomics indexes. The math checks out, the citations are honest, and the central claim is solid. I would send it to peer review without hesitation and would cite the upper bound and the active-prefix barrier myself.

Referee Report

2 major / 4 minor

Summary. The paper studies pattern matching and indexing for generalized degenerate (GD) strings, the remaining boundary case in the Ascone et al. taxonomy of variable-string matching. For offline matching it gives a classical algorithm running in O(N + √(N L m log L log m)) = Õ(N √m) time (Theorem 3), obtained by a heavy/light decomposition of width-k strings, FFT convolution for heavy strings, direct occurrence counting for light strings, and Cauchy–Schwarz aggregation over widths (Lemma 2). For indexing it adapts Gibney’s ED index to obtain O(nm) query time after linear preprocessing of a GD text (Theorem 4). On the lower-bound side it shows, under OVH/SETH, that no polynomial-preprocessing GD index can achieve O(n^{1-ε} m^{O(1)} + m) query time; under the k-clique conjecture it rules out combinatorial GD indices with O(n^{O(1)} m^{1-ε} + m) queries and combinatorial ED indices with O(n^{O(1)} m^{2-ε}) queries; and under OMv it shows that active-prefix queries cannot be answered in O(m^{2-ε}) time after polynomial preprocessing of the string set and pattern.

Significance. The offline algorithm closes the main open case left by Ascone et al. (WABI 2024) and places GD matching firmly on the subquadratic side of the fine-grained dichotomy for variable strings, complementing the earlier quantum Õ(√(m n N)) result of Equi et al. The indexing upper and lower bounds give a coherent picture: the O(nm) GD index is essentially optimal for combinatorial algorithms under k-clique, while the O(nm^{2}) ED index of Gibney is likewise tight for combinatorial algorithms and for any approach whose bottleneck is active-prefix queries. The reductions are from standard hypotheses (OVH, k-clique, OMv) and the string gadgets are explicit adaptations of Bringmann et al., so the conditional claims rest on well-studied foundations. The work therefore both settles a concrete open problem and sharpens the landscape of what further improvements would require.

major comments (2)

The combinatorial lower bounds (Theorems 11 and 14) rest on the correctness of the string gadgets adapted from Bringmann et al. (Lemmas 9/12 and Corollaries 10/13). While the constructions are written carefully, the manuscript never supplies an independent verification that the equal-width (GD) or variable-length (ED) concatenation rules preserve clique structure exactly as claimed. A short self-contained correctness argument, or an explicit reference to the precise lemma in Bringmann et al. that is being reused, would make the load-bearing reductions fully checkable without external consultation.
Section 4.1 correctly identifies a potential flaw in Gibney’s claimed β < 1 lower bound (the additive +m term already solves OV). The paper leaves open whether a corrected SETH-based lower bound forbidding O(n^{O(1)} m^{1-ε} + m) ED queries exists. Because the subsequent k-clique and OMv results are presented as partial substitutes, a clearer statement of what remains open under SETH alone would help the reader assess the strength of the overall indexing picture.

minor comments (4)

In the proof of Lemma 2 the heavy/light threshold is set to τ_k = √(L m log m / B_k). The subsequent Cauchy–Schwarz step in Theorem 3 uses √(1/k) N_k; a one-line remark that the log factors can be absorbed into the Õ notation would improve readability.
Figure 2 and Figure 3 are helpful but the caption of Figure 2 is dense. Expanding the definition of the four bit-vectors V_easy, V_suf, V_pref, V_anchor in the caption (or moving a short paragraph into the main text) would make the case analysis easier to follow.
The notation N_ε for the number of empty strings appears only in the size definition of ED strings and is never used again; it can be dropped or briefly justified.
A few typographical issues: “Ageneralized” (missing space) in the abstract, “Ts(p)” versus T_s(p) inconsistency in Figure 2, and occasional missing spaces after periods in the arXiv source.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained algorithmic upper bound and reductions from external fine-grained hypotheses

full rationale

This is a pure algorithms/fine-grained-complexity paper. The central claim (Theorem 3, Õ(N√m) GDSM) is derived from first principles via heavy/light classification of width-k strings (using the suffix tree of P), FFT convolution for heavy strings, direct occurrence counting for light strings, and Cauchy–Schwarz aggregation over widths; every step is explicit and uses only standard tools (suffix trees, FFT, KMP). The indexing upper bound (Theorem 4) is a direct adaptation of Gibney’s ED index that exploits equal widths. All lower bounds are reductions from external, standard conjectures (OVH/SETH, k-clique, OMv) via explicitly constructed string gadgets (adapted from Bringmann et al. [6] and Bernardini et al. [5]); no quantity is defined in terms of a later “prediction,” no parameter is fitted to data, and no uniqueness theorem or ansatz is imported from the author’s own prior work as a load-bearing premise. The single self-citation ([13]) is background only. Consequently the derivation chain is non-circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The paper is pure fine-grained algorithms. It relies only on standard mathematical tools (FFT, suffix trees, Cauchy-Schwarz) and three widely-used conditional hypotheses. No free parameters are fitted; the heavy/light threshold au_k is set analytically. The only invented objects are the concrete string gadgets used in the reductions, which are explicit constructions rather than postulated physical entities.

assumptions (5)

domain assumption Orthogonal Vectors Hypothesis (OVH) / SETH
Used for the n^{1-ε} indexing lower bound (Theorem 6) via the existing reduction of Gibney that already produces GD strings.
domain assumption k-clique conjecture (no combinatorial O(n^{k-ε}) algorithm)
Conjecture 8; load-bearing for Theorems 11 and 14 that rule out combinatorial m^{1-ε} (GD) and m^{2-ε} (ED) query times.
domain assumption Online Matrix-Vector multiplication (OMv) conjecture
Conjecture 15; used for the active-prefix lower bound (Theorem 16).
standard math FFT multiplies two length-L binary vectors in O(L log m) time
Invoked in the heavy-string contribution of Lemma 2.
standard math Suffix tree of P can be built in O(m) time and answers occurrence counts
Used throughout Section 3 and for the light-string case.

invented entities (2)

Heavy/light classification of width-k strings by occurrence count au_k = √(L m log m / B_k) inside P independent evidence
purpose: Balances FFT cost of heavy strings against enumeration cost of light strings to obtain the √m factor.
Standard heavy-light technique specialized to the GD setting; the threshold is derived analytically, not fitted.
String gadgets S(G), T(G), E(G), ˜S, ˜T, Γ for encoding k-clique into GD/ED pattern matching independent evidence
purpose: Reduce combinatorial k-clique to GD/ED indexing queries so that an improved index would yield a faster combinatorial clique algorithm.
Adapted from Bringmann et al.; correctness is claimed via Lemmas 9 and 12. Independent of the target complexity result once the gadgets are fixed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Algorithms and Indexing Lower Bounds for Variable String Matching." pith.science (2026). https://pith.science/paper/LJ3SMSNQ

@misc{pith2026260708566,
  author       = {Pith},
  title        = {Pith review of: Algorithms and Indexing Lower Bounds for Variable String Matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LJ3SMSNQ}},
  note         = {Machine review of arXiv:2607.08566}
}

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.

Figures

Figures reproduced from arXiv: 2607.08566 by the authors.

**Figure 2.** Alignment of a candidate occurrence of P[1 . . . m] starting at position p with the segments of T. If Ti has width k, then it contributes 1 to A[p] if there exists a string t ∈ Ti such that t = P[Li − p + 1 . . . Ri − p + 1]. After processing all widths, A[p] equals the number of fully covered segments matched by this alignment. Given a GD string T, the span L of T is defined as L = Pn i=1 ki , where ki is the width… view at source ↗

**Figure 3.** For the light strings, when reading a string [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Degenerate String Comparison and Applications

Mai Alzamel et al. “Degenerate String Comparison and Applications.” In:LIPIcs, Volume 113, WABI 2018113 (2018). Ed. by Laxmi Parida and Esko Ukkonen, 21:1–21:14.issn: 1868-8969.doi:10.4230/LIPICS.WABI.2018.21.url:https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.WABI.2018.21

work page doi:10.4230/lipics.wabi.2018.21.url:https://drops.dagstuhl.de/ 2018
[2]

Faster Online Elastic Degenerate String Matching

Kotaro Aoyama et al. “Faster Online Elastic Degenerate String Matching.” In:CPM. Vol. 105. May 1, 2018.doi:10.4230/lipics.cpm.2018.9

work page doi:10.4230/lipics.cpm.2018.9 2018
[3]

A Unifying Taxonomy of Pattern Matching in Degenerate Strings and Founder Graphs

Rocco Ascone et al. “A Unifying Taxonomy of Pattern Matching in Degenerate Strings and Founder Graphs.” In:LIPIcs, Volume 312, WABI 2024312 (2024). Ed. by Solon P. Pissis and Wing-Kin Sung, 14:1–14:21.issn: 1868-8969.doi:10.4230/LIPICS.WABI.2024.14. url:https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024. 14

work page doi:10.4230/lipics.wabi.2024.14 2024
[4]

Which Regular Expression Patterns Are Hard to Match?

A. Backurs and P. Indyk. “Which Regular Expression Patterns Are Hard to Match?” In: 57th IEEE Symposium on Foundations Of Computer Science (FOCS). 2016, pp. 457–466. 11

work page 2016
[5]

Even Faster Elastic-Degenerate String Matching via Fast Ma- trix Multiplication

Giulia Bernardini et al. “Even Faster Elastic-Degenerate String Matching via Fast Ma- trix Multiplication.” In:46th International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2019, July 9-12, 2019, Patras, Greece. 2019, 21:1–21:15.doi:10.4230/ LIPIcs.ICALP.2019.21.url:https://doi.org/10.4230/LIPIcs.ICALP.2019.21

work page doi:10.4230/lipics.icalp.2019.21 2019
[6]

Karl Bringmann, Allan Grønlund, and Kasper Green Larsen.A Dichotomy for Regular Expression Membership Testing. Nov. 7, 2016.doi:10.48550/arXiv.1611.00918. arXiv: 1611.00918 [cs].url:http://arxiv.org/abs/1611.00918

work page Pith review arXiv doi:10.48550/arxiv.1611.00918 2016
[7]

Roberson , editor =

Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. “Faster Approxi- mate Pattern Matching: A Unified Approach.” In:61st IEEE Annual Symposium on Foun- dations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. Ed. by Sandy Irani. IEEE, 2020, pp. 978–989.doi:10.1109/FOCS46700.2020.00095.url: https://doi.org/10.1109/FOCS...

work page doi:10.1109/focs46700.2020.00095.url: 2020
[8]

Dictionary Matching and In- dexing with Errors and Don’t Cares

Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. “Dictionary Matching and In- dexing with Errors and Don’t Cares.” In:Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing - STOC ’04. The Thirty-Sixth Annual ACM Sym- posium. Chicago, IL, USA: ACM Press, 2004, p. 91.isbn: 978-1-58113-852-8.doi:10. 1145/1007352.1007374.url:http://p...

work page arXiv 2004

Show all 24 references

[9]

Cambridge University Press, 2007.isbn: 978-0-521-84899-2

Maxime Crochemore, Christophe Hancart, and Thierry Lecroq.Algorithms on Strings. Cambridge University Press, 2007.isbn: 978-0-521-84899-2

2007
[10]

Massimo Equi, Md Rabiul Islam Khan, and Veli Mäkinen.Quantum Pattern Matching in Generalised Degenerate Strings. Mar. 17, 2026.doi:10.48550/arXiv.2603.16297. arXiv: 2603.16297 [quant-ph].url:http://arxiv.org/abs/2603.16297

2026 doi arXiv
[11]

Tomescu.Graphs Cannot Be Indexed in Polynomial Time for Sub-Quadratic Time String Matching, Unless SETH Fails

Massimo Equi, Veli Mäkinen, and Alexandru I. Tomescu.Graphs Cannot Be Indexed in Polynomial Time for Sub-Quadratic Time String Matching, Unless SETH Fails. Mar. 4, 2020.doi:10.48550/arXiv.2002.00629. arXiv:2002.00629 [cs].url:http://arxiv. org/abs/2002.00629

2020 doi arXiv
[12]

Graphs Cannot Be Indexed in Polynomial Time for Sub-Quadratic Time String Matching, Unless SETH Fails

Massimo Equi, Veli Mäkinen, and Alexandru I. Tomescu. “Graphs Cannot Be Indexed in Polynomial Time for Sub-Quadratic Time String Matching, Unless SETH Fails.” In:The- oretical Computer Science975 (Oct. 2023), p. 114128.issn: 03043975.doi:10 . 1016 / j . tcs . 2023 . 114128.url...

2023
[13]

Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications

Estéban Gabory et al. “Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications.” In:34th Annual Symposium on Combinatorial Pattern Matching, CPM. Ed. by Laurent Bulteau and Zsuzsanna Lipták. Vol. 259. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Info...

2023 doi
[14]

Towards Unified Approximate Pattern Matching for Hamming andL1 Distance

Paweł Gawrychowski and Przemysław Uznański. “Towards Unified Approximate Pattern Matching for Hamming andL1 Distance.” In:45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. Ed. by Ioannis Chatzigiannakis ...

2018 doi
[15]

An Efficient Elastic-Degenerate Text Index? Not Likely

Daniel Gibney. “An Efficient Elastic-Degenerate Text Index? Not Likely.” In:String Pro- cessing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings. 2020, pp. 76–88.doi:10.1007/978-3-030- 59212-7_6.url:https:...

2020 doi
[16]

On-Line Pattern Matching on Similar Texts

Roberto Grossi et al. “On-Line Pattern Matching on Similar Texts.” In:CPM. Vol. 78. July 1, 2017.doi:10.4230/lipics.cpm.2017.9

2017 doi
[17]

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Monika Henzinger et al. “Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture.” In:Proceedings of the Forty- Seventh Annual ACM Symposium on Theory of Computing. June 14, 2015, pp. 21–30. doi:10.1145/2746539.2746609. a...

2015 doi
[18]

Efficient pattern matching in elastic-degenerate strings

Costas S. Iliopoulos, Ritu Kundu, and Solon P. Pissis. “Efficient pattern matching in elastic-degenerate strings.” In:Information and Computation279 (2021). Selected Papers of the 11th International Conference on Language and Automata Theory and Applications, LATA 2017, p. 104...

2021 doi
[19]

Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties

Costas S. Iliopoulos and Jakub Radoszewski. “Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.” In:27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Ed. by Roberto Grossi and Moshe Lewen- stein. Vol. 54. Leibni...

2016 doi
[20]

Fast Pattern Matching in Strings

Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. “Fast Pattern Matching in Strings.” In:SIAM Journal on Computing6.2 (June 1977), pp. 323–350.issn: 0097- 5397, 1095-7111.doi:10.1137/0206024.url:http://epubs.siam.org/doi/10.1137/ 0206024

1977 doi
[21]

An Efficient String Matching Algorithm with k Differences for Nucleotide and Amino Acid Sequences

G M Landau, U Vishkin, and R Nussinov. “An Efficient String Matching Algorithm with k Differences for Nucleotide and Amino Acid Sequences.” In:Nucleic Acids Research14.1 (Jan. 10, 1986), pp. 31–46.issn: 0305-1048. PMID:3753770.url:https://www.ncbi. nlm.nih.gov/pmc/articles/PMC339353/

1986
[22]

FastStringMatchingwithkDifferences

GadM.LandauandUziVishkin.“FastStringMatchingwithkDifferences.” In:J. Comput. Syst. Sci.37.1 (1988), pp. 63–78.doi:10.1016/0022- 0000(88)90045- 1.url:https: //doi.org/10.1016/0022-0000(88)90045-1

1988 doi
[23]

Set Intersection and Sequence Matching with Mismatch Counting

Ariel Shiftan and Ely Porat. “Set Intersection and Sequence Matching with Mismatch Counting.” In:Theoretical Computer Science638 (July 2016), pp. 3–10.issn: 03043975. doi:10 . 1016 / j . tcs . 2016 . 01 . 003.url:https : / / linkinghub . elsevier . com / retrieve/pii/S0304397516000049

2016
[24]

A New Algorithm for Optimal 2-Constraint Satisfaction and Its Im- plications

Ryan Williams. “A New Algorithm for Optimal 2-Constraint Satisfaction and Its Im- plications.” In:Theoretical Computer Science348.2–3 (Dec. 2005), pp. 357–365.issn: 03043975.doi:10.1016/j.tcs.2005.09.023.url:https://linkinghub.elsevier. com/retrieve/pii/S0304397505005438. 13

2005 doi

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.

[1] [1]

Degenerate String Comparison and Applications

Mai Alzamel et al. “Degenerate String Comparison and Applications.” In:LIPIcs, Volume 113, WABI 2018113 (2018). Ed. by Laxmi Parida and Esko Ukkonen, 21:1–21:14.issn: 1868-8969.doi:10.4230/LIPICS.WABI.2018.21.url:https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.WABI.2018.21

work page doi:10.4230/lipics.wabi.2018.21.url:https://drops.dagstuhl.de/ 2018

[2] [2]

Faster Online Elastic Degenerate String Matching

Kotaro Aoyama et al. “Faster Online Elastic Degenerate String Matching.” In:CPM. Vol. 105. May 1, 2018.doi:10.4230/lipics.cpm.2018.9

work page doi:10.4230/lipics.cpm.2018.9 2018

[3] [3]

A Unifying Taxonomy of Pattern Matching in Degenerate Strings and Founder Graphs

Rocco Ascone et al. “A Unifying Taxonomy of Pattern Matching in Degenerate Strings and Founder Graphs.” In:LIPIcs, Volume 312, WABI 2024312 (2024). Ed. by Solon P. Pissis and Wing-Kin Sung, 14:1–14:21.issn: 1868-8969.doi:10.4230/LIPICS.WABI.2024.14. url:https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024. 14

work page doi:10.4230/lipics.wabi.2024.14 2024

[4] [4]

Which Regular Expression Patterns Are Hard to Match?

A. Backurs and P. Indyk. “Which Regular Expression Patterns Are Hard to Match?” In: 57th IEEE Symposium on Foundations Of Computer Science (FOCS). 2016, pp. 457–466. 11

work page 2016

[5] [5]

Even Faster Elastic-Degenerate String Matching via Fast Ma- trix Multiplication

Giulia Bernardini et al. “Even Faster Elastic-Degenerate String Matching via Fast Ma- trix Multiplication.” In:46th International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2019, July 9-12, 2019, Patras, Greece. 2019, 21:1–21:15.doi:10.4230/ LIPIcs.ICALP.2019.21.url:https://doi.org/10.4230/LIPIcs.ICALP.2019.21

work page doi:10.4230/lipics.icalp.2019.21 2019

[6] [6]

Karl Bringmann, Allan Grønlund, and Kasper Green Larsen.A Dichotomy for Regular Expression Membership Testing. Nov. 7, 2016.doi:10.48550/arXiv.1611.00918. arXiv: 1611.00918 [cs].url:http://arxiv.org/abs/1611.00918

work page Pith review arXiv doi:10.48550/arxiv.1611.00918 2016

[7] [7]

Roberson , editor =

Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. “Faster Approxi- mate Pattern Matching: A Unified Approach.” In:61st IEEE Annual Symposium on Foun- dations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. Ed. by Sandy Irani. IEEE, 2020, pp. 978–989.doi:10.1109/FOCS46700.2020.00095.url: https://doi.org/10.1109/FOCS...

work page doi:10.1109/focs46700.2020.00095.url: 2020

[8] [8]

Dictionary Matching and In- dexing with Errors and Don’t Cares

Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. “Dictionary Matching and In- dexing with Errors and Don’t Cares.” In:Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing - STOC ’04. The Thirty-Sixth Annual ACM Sym- posium. Chicago, IL, USA: ACM Press, 2004, p. 91.isbn: 978-1-58113-852-8.doi:10. 1145/1007352.1007374.url:http://p...

work page arXiv 2004