A subquadratic algorithm for approximate limited expression matching

DOI10.1007/BF01942606zbMath0960.68592OpenAlexW1980038595MaRDI QIDQ1907030

Sun Wu, Udi Manber, Gene Myers

Publication date: 9 May 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01942606

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

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

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

This page was built for publication: A subquadratic algorithm for approximate limited expression matching