Faster approximate pattern matching: a unified approach

DOI10.1109/FOCS46700.2020.00095MaRDI QIDQ6943960zbMATH OpenFDO

Authors Tomasz Kociumaka, Philip Wellnitz, Panagiotis Charalampopoulos

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00095

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(13)

• Shortest cover after edit
• Internal pattern matching in small space and applications
• Approximate circular pattern matching under edit distance
• Differentially private approximate pattern matching
• Small-space algorithms for the online language distance problem for palindromes and squares
• Approximate circular pattern matching
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Computing string covers in sublinear time
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• An almost optimal edit distance oracle
• Longest common extensions with wildcards: trade-off and applications
• Pattern matching with mismatches and wildcards
• Bounded weighted edit distance: dynamic algorithms and matching lower bounds

This page was built for publication: Faster approximate pattern matching: a unified approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943960)