Approximate string matching with suffix automata

DOI10.1007/BF01769703zbMath0779.68038OpenAlexW1995303482MaRDI QIDQ689099

Derick Wood, Esko Ukkonen

Publication date: 19 January 1994

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximate occurrencespattern stringtext string

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Related Items (17)

Sublinear approximate string matching and biological applications ⋮ Boyer-Moore approach to approximate string matching ⋮ On-line construction of suffix trees ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ A dynamic edit distance table ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Extending alignments with \(k\)-mismatches and \(\ell\)-gaps ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Faster approximate string matching for short patterns ⋮ On-line construction of compact directed acyclic word graphs ⋮ Ternary directed acyclic word graphs ⋮ Special factors and the combinatorics of suffix and factor automata ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Efficient algorithms for approximate string matching with swaps ⋮ On minimizing pattern splitting in multi-track string matching ⋮ Fast and practical approximate string matching

Cites Work

• Unnamed Item
• The smallest automaton recognizing the subwords of a text
• Time optimal left to right construction of position trees
• An \(O(ND)\) difference algorithm and its variations
• Data structures and algorithms for approximate string matching
• Fast string matching with k differences
• Transducers and repetitions
• An Improved Algorithm For Approximate String Matching
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• The theory and computation of evolutionary distances: Pattern recognition
• Efficient string matching
• Fast parallel and serial approximate string matching
• The String-to-String Correction Problem

This page was built for publication: Approximate string matching with suffix automata