Approximate swapped matching.

DOI10.1016/S0020-0190(01)00302-7MaRDI QIDQ1853034zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Moshe Lewenstein, Ely Porat

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(01)00302-7

zbMATH Keywords

Pattern matchingDesign and analysis of algorithmsCombinatorial algorithms on wordsNon-standard pattern matchingPattern matching with swapsApproximate pattern matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics on words (68R15)

Recommendations

• scientific article; zbMATH DE number 2080211
• Pattern Matching with Swaps
• Pattern matching with swaps in practice
• Efficient special cases of pattern matching with swaps
• Pattern Matching with Swaps for Short Patterns in Linear Time

Cites work

• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 3557227 (Why is no real title available?)
• scientific article; zbMATH DE number 1303588 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• An Extension of the String-to-String Correction Problem
• An Improved Algorithm For Approximate String Matching
• Efficient 2-dimensional approximate matching of half-rectangular figures
• Efficient special cases of pattern matching with swaps
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching
• Generalized String Matching
• Incremental String Comparison
• Overlap matching
• Pattern Matching with Swaps
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• String matching under a general matching relation

Cited in

(25)

• Pattern Matching with Swaps for Short Patterns in Linear Time
• On the hardness of optimal vertex relabeling and restricted vertex relabeling
• Swap and mismatch edit distance
• Pattern matching with swaps in practice
• Approximate string matching with stuck address bits
• Property matching and weighted matching
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• String matching with up to k swaps and mismatches
• Efficient Algorithms for the Spoonerism Problem
• Approximate string matching with address bit errors
• Efficient special cases of pattern matching with swaps
• The swap matching problem revisited
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Fast algorithms for single and multiple pattern Cartesian tree matching
• scientific article; zbMATH DE number 2080211 (Why is no real title available?)
• On the relationship between histogram indexing and block-mass indexing
• The approximate swap and mismatch edit distance
• Exploiting pseudo-locality of interchange distance
• Approximate periodicity
• Finding patterns and periods in Cartesian tree matching
• Overlap matching.
• Using swaps and deletes to make strings match
• Cartesian Tree Matching and Indexing
• Approximate String Matching with Address Bit Errors
• Fast Cartesian tree matching

This page was built for publication: Approximate swapped matching.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853034)