Faster approximate string matching for short patterns

DOI10.1007/S00224-011-9322-YzbMath1280.68304arXiv0811.3490OpenAlexW1821184416MaRDI QIDQ692899

Philip Bille

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.3490

zbMATH Keywords

approximate string matchingword-level parallelism

Mathematics Subject Classification ID

Combinatorics on words (68R15) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate string matching with suffix automata
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• An \(O(ND)\) difference algorithm and its variations
• Data structures and algorithms for approximate string matching
• A faster algorithm computing string edit distances
• Sorting in linear time?
• Improved parallel integer sorting without concurrent writing
• Bit-parallel witnesses and their applications to approximate string matching
• Fast and compact regular expression matching
• Approximate String Matching: A Simpler Faster Algorithm
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Fast Algorithms for Finding Nearest Common Ancestors
• An Improved Algorithm For Approximate String Matching
• Algorithms for approximate string matching
• The theory and computation of evolutionary distances: Pattern recognition
• Fast parallel and serial approximate string matching
• Algorithms on Strings, Trees and Sequences
• Approximate string matching using withinword parallelism
• The String-to-String Correction Problem
• New and faster filters for multiple approximate string matching
• On the sorting-complexity of suffix tree construction

This page was built for publication: Faster approximate string matching for short patterns