Bit-Parallel Approximate Matching of Circular Strings with k Mismatches

DOI10.1145/3129536MaRDI QIDQ4577948zbMATHOpenAlexFDO

Authors Tommi Hirvola, Jorma Tarhio

Publication date 6 August 2018

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3129536

zbMATH Keywords

approximate matchingcircular stringsbit-parallel automata

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches
• Bit-parallel witnesses and their applications to approximate string matching
• Bit-parallel approximate string matching algorithms with transposition
• Average-case optimal approximate circular string matching
• scientific article; zbMATH DE number 710402
• scientific article; zbMATH DE number 2087055
• Bit-parallel approximate string matching algorithms with transposition.
• Parallel string matching with k mismatches
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time

Cites work

• scientific article; zbMATH DE number 140453 (Why is no real title available?)
• A compact representation of nondeterministic (suffix) automata for the bit-parallel approach
• A fast suffix automata based algorithm for exact online string matching
• Algorithms on Strings, Trees and Sequences
• Alternative algorithms for bit-parallel string matching.
• Approximate Boyer–Moore String Matching
• Average-case optimal approximate circular string matching
• Average-optimal single and multiple approximate string matching
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Maximum Statistics of N Random Variables Distributed by the Negative Binomial Distribution
• NR-grep: A fast and flexible pattern-matching tool
• Nested Counters in Bit-Parallel String Matching
• The wide window string matching algorithm

Cited in

(10)

• Circular pattern matching with \(k\) mismatches
• Circular pattern matching with \(k\) mismatches
• Average-case optimal approximate circular string matching
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• Fast circular dictionary-matching algorithm
• A simple, fast, filter-based algorithm for circular sequence comparison
• Bit-parallel witnesses and their applications to approximate string matching
• A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches
• An encoding for order-preserving matching

This page was built for publication: Bit-Parallel Approximate Matching of Circular Strings with k Mismatches

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