A subquadratic algorithm for approximate limited expression matching

DOI10.1007/BF01942606zbMath0960.68592MaRDI QIDQ1907030

Sun Wu, Udi Manber, Gene Myers

Publication date: 9 May 1996

Published in: Algorithmica (Search for Journal in Brave)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

New and faster filters for multiple approximate string matching, On-Line Approximate String Searching Algorithms: Survey and Experimental Results, Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching, A sublinear algorithm for approximate keyword searching, Improved approximate pattern matching on hypertext, A fast and practical bit-vector algorithm for the longest common subsequence problem, Fast and practical approximate string matching, Approximate Boyer-Moore string matching for small alphabets, Fast distance multiplication of unit-Monge matrices, BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS

Uses Software

• Agrep

Cites Work

• Unnamed Item
• Approximate string matching with suffix automata
• Fast string matching with k differences
• A faster algorithm computing string edit distances
• Approximate string-matching with \(q\)-grams and maximal matches
• A sublinear algorithm for approximate keyword searching
• A fast string searching algorithm
• An Improved Algorithm For Approximate String Matching
• Finding approximate patterns in strings
• Generalized String Matching
• The theory and computation of evolutionary distances: Pattern recognition
• Approximate Boyer–Moore String Matching
• Efficient string matching
• Fast Pattern Matching in Strings
• A Four Russians algorithm for regular expression pattern matching
• The String-to-String Correction Problem
• A Subquadratic Algorithm for Approximate Regular Expression Matching