Efficient special cases of pattern matching with swaps

DOI10.1016/S0020-0190(98)00151-3zbMath1338.68303OpenAlexW2071882054MaRDI QIDQ293429

Gad M. Landau, Noa Lewenstein, Amihood Amir, Moshe Lewenstein

Publication date: 9 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001513?np=y

zbMATH Keywords

analysis of algorithmsdesign of algorithmspattern matchingapproximate pattern matchingcombinatorial algorithms on wordsgeneralized pattern matchingpattern matching with swaps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items

The swap matching problem revisited ⋮ PATTERN MATCHING WITH SWAPS IN PRACTICE ⋮ On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling ⋮ Overlap matching. ⋮ Property matching and weighted matching ⋮ Restricted and swap common superstring: a multivariate algorithmic perspective ⋮ Pattern matching with pair correlation distance ⋮ 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 ⋮ Approximate swapped matching.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two recognizable string-matching problems over free partially commutative monoids
• Efficient 2-dimensional approximate matching of half-rectangular figures
• String matching under a general matching relation
• Pattern matching in compressed texts
• A fast string searching algorithm
• Generalized String Matching
• An Extension of the String-to-String Correction Problem
• Fast Pattern Matching in Strings

This page was built for publication: Efficient special cases of pattern matching with swaps