Approximate circular pattern matching under edit distance

DOI10.4230/LIPICS.STACS.2024.24MaRDI QIDQ6902700zbMATH OpenFDO

Authors Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.24

zbMATH Keywords

edit distanceapproximate pattern matchingcircular pattern matching

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 6850408 (Why is no real title available?)
• Approximate String Matching: A Simpler Faster Algorithm
• Approximate circular pattern matching
• Approximating text-to-pattern Hamming distances
• Circular pattern matching with \(k\) mismatches
• Complexity measures and decision tree complexity: a survey.
• Deterministic sorting in O(nloglogn) time and linear space
• Differentially private approximate pattern matching
• Dynamic suffix array with polylogarithmic queries and updates
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching
• Fast string matching with k differences
• Faster algorithms for string matching with k mismatches
• Faster algorithms for text-to-pattern Hamming distances
• Faster approximate pattern matching: a unified approach
• Faster pattern matching under edit distance: a reduction to dynamic puzzle matching and the seaweed monoid of permutation matrices
• Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts
• Internal pattern matching queries in a text and applications
• On a cyclic string-to-string correction problem
• On hidden Markov models and cyclic strings for shape recognition
• Quantum speed-ups for string synchronizing sets, longest common substring, and \(k\)-mismatch matching
• Small-space algorithms for the online language distance problem for palindromes and squares
• Small-space and streaming pattern matching with k edits
• String matching in O( n+ m) quantum time
• The \(k\)-mismatch problem revisited
• The dynamic k-mismatch problem
• The theory and computation of evolutionary distances: Pattern recognition
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance

Cited in

(2)

• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• Internal pattern matching in small space and applications

This page was built for publication: Approximate circular pattern matching under edit distance

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