Pattern Matching with Swaps for Short Patterns in Linear Time

DOI10.1007/978-3-540-95891-8_25MaRDI QIDQ3599078zbMATH OpenOpenAlexFDO

Authors Domenico Cantone, Simone Faro

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-95891-8_25

zbMATH Keywords

combinatorial algorithms on wordsdesign and analysis of algorithmsnonstandard pattern matchingpattern matching with swaps

Mathematics Subject Classification ID

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

Recommendations

• Efficient special cases of pattern matching with swaps
• A new algorithm for efficient pattern matching with swaps
• Pattern matching with swaps in practice
• Pattern Matching with Swaps
• A linear time algorithm for consecutive permutation pattern matching
• Efficient algorithms for approximate string matching with swaps
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• A simple streaming bit-parallel algorithm for swap pattern matching
• Two-dimensional pattern matching in linear time and small space

Cites work

• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Approximate swapped matching.
• Efficient special cases of pattern matching with swaps
• Overlap matching.
• Pattern Matching with Swaps

Cited in

(12)

• Approximate swapped matching.
• On a compact encoding of the swap automaton
• A weak approach to suffix automata simulation for exact and approximate string matching
• Pattern matching with swaps in practice
• The swap matching problem revisited
• A new algorithm for efficient pattern matching with swaps
• scientific article; zbMATH DE number 2080211 (Why is no real title available?)
• Pattern Matching with Swaps
• A simple streaming bit-parallel algorithm for swap pattern matching
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Quantum string matching unfolded and extended
• On the complexity of indeterminate strings matching

This page was built for publication: Pattern Matching with Swaps for Short Patterns in Linear Time

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