Approximate string matching with suffix automata

DOI10.1007/BF01769703zbMath0779.68038MaRDI QIDQ689099

Esko Ukkonen, Derick Wood

Publication date: 19 January 1994

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximate occurrences; pattern string; text string

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68W10: Parallel algorithms in computer science

Related Items

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