Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts

DOI10.1137/1.9781611975482.69MaRDI QIDQ5236253zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Marvin Künnemann, Philip Wellnitz

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Approximate pattern matching with \(k\)-mismatches in packed text
• Faster algorithms for string matching with k mismatches
• scientific article; zbMATH DE number 1445379
• Approximate string matching on Ziv--Lempel compressed text
• Beating \(O(nm)\) in approximate LZW-compressed pattern matching

Cited in

(7)

• Approximate pattern matching with \(k\)-mismatches in packed text
• Faster approximate pattern matching in compressed repetitive texts
• Circular pattern matching with \(k\) mismatches
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Approximate circular pattern matching under edit distance
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Pattern matching with mismatches and wildcards

This page was built for publication: Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts

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