Circular pattern matching with \(k\) mismatches

DOI10.1016/j.jcss.2020.07.003zbMath1467.68236OpenAlexW2964971186MaRDI QIDQ5918999

Tomasz Walen, Wojciech Rytter, Tomasz Kociumaka, Wiktor Zuba, Jakub Radoszewski, Solon P. Pissis, Panagiotis Charalampopoulos, Juliusz Straszyński

Publication date: 23 October 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2020.07.003

zbMATH Keywords

approximate pattern matching\(k\)-mismatch problemcircular pattern matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Order-preserving pattern matching with \(k\) mismatches
• Efficient string matching with k mismatches
• Parallel string matching with k mismatches
• On hidden Markov models and cyclic strings for shape recognition
• Average-Case Optimal Approximate Circular String Matching
• Beating $\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching
• Improved approximate string matching and regular expression matching on Ziv-Lempel compressed texts
• Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment
• Unifying the Landscape of Cell-Probe Lower Bounds
• Searching and Indexing Circular Patterns
• Constructing Efficient Dictionaries in Close to Sorting Time
• Approximate parameterized matching
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Generalized String Matching
• The k-mismatch problem revisited
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Faster algorithms for string matching with k mismatches
• Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
• Approximating text-to-pattern Hamming distances
• Exact and Approximate Pattern Matching in the Streaming Model
• The streaming k-mismatch problem
• Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts
• Uniqueness Theorems for Periodic Functions
• Internal Pattern Matching Queries in a Text and Applications
• Algorithms on Strings
• Average-optimal single and multiple approximate string matching
• Efficient representation and counting of antipower factors in words
• Circular pattern matching with \(k\) mismatches