Nested Counters in Bit-Parallel String Matching

DOI10.1007/978-3-642-00982-2_29MaRDI QIDQ3618593zbMATH OpenOpenAlexFDO

Authors Kimmo Fredriksson, Szymon Grabowski

Publication date 2 April 2009

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00982-2_29

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Algorithms on strings (68W32)

Recommendations

• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Efficient Bit-Parallel Algorithms for (δ,α)-Matching
• Increased bit-parallelism for approximate and multiple string matching
• Alternative algorithms for bit-parallel string matching.
• Fast and flexible string matching by combining bit-parallelism and suffix automata

Cites work

• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Bit-parallel witnesses and their applications to approximate string matching
• Efficient Bit-Parallel Algorithms for (δ,α)-Matching
• Efficient string matching with k mismatches
• scientific article; zbMATH DE number 1998336 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• Surpassing the information theoretic bound with fusion trees

Cited in

(4)

• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Motif matching using gapped patterns
• String matching with variable length gaps
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches

This page was built for publication: Nested Counters in Bit-Parallel String Matching

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