Approximate swapped matching.

DOI10.1016/S0020-0190(01)00302-7zbMath1043.68082OpenAlexW1978432631MaRDI QIDQ1853034

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)

Related Items (19)

Swap and mismatch edit distance ⋮ The swap matching problem revisited ⋮ PATTERN MATCHING WITH SWAPS IN PRACTICE ⋮ Exploiting pseudo-locality of interchange distance ⋮ The approximate swap and mismatch edit distance ⋮ On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling ⋮ On the relationship between histogram indexing and block-mass indexing ⋮ Approximate String Matching with Address Bit Errors ⋮ Finding patterns and periods in Cartesian tree matching ⋮ String matching with up to \(k\) swaps and mismatches ⋮ Fast algorithms for single and multiple pattern Cartesian tree matching ⋮ Property matching and weighted matching ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Approximate string matching with stuck address bits ⋮ Pattern Matching with Swaps for Short Patterns in Linear Time ⋮ A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns ⋮ Cartesian Tree Matching and Indexing ⋮ Approximate string matching with address bit errors ⋮ Approximate periodicity

Cites Work

• Efficient special cases of pattern matching with swaps
• Efficient 2-dimensional approximate matching of half-rectangular figures
• String matching under a general matching relation
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• An Improved Algorithm For Approximate String Matching
• Generalized String Matching
• An Extension of the String-to-String Correction Problem
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching
• Incremental String Comparison
• Pattern Matching with Swaps
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximate swapped matching.