Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching

DOI10.1137/1.9781611977554.CH186MaRDI QIDQ6538717zbMATH OpenFDO

Authors Ce Jin, Jakob Nogler

Publication date 14 May 2024

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH186

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Near-optimal quantum algorithms for string problems
• Near-optimal quantum algorithms for string problems
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• String matching in O( n+ m) quantum time

Cited in

(11)

• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Quantum string matching unfolded and extended
• Near-optimal quantum algorithms for string problems
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Near-optimal quantum algorithms for string problems
• Internal pattern matching queries in a text and applications
• Quantum data structure for range minimum query
• Approximate circular pattern matching under edit distance
• Approximation algorithms for LCS and LIS with truly improved running times
• Computing string covers in sublinear time
• Pattern matching with mismatches and wildcards

This page was built for publication: Quantum speed-ups for string synchronizing sets, longest common substring, and \(k\)-mismatch matching

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