Overlap matching.

DOI10.1016/S0890-5401(02)00035-4zbMath1054.68119MaRDI QIDQ1401926

Ramesh Hariharan, Moshe Lewenstein, Ely Porat, Amihood Amir, Richard John Cole

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(02)00035-4

zbMATH Keywords

Pattern matching; Design and analysis of algorithms; Combinatorial algorithms on words; Non-standard pattern matching; Pattern matching with swaps

Mathematics Subject Classification ID

68P10: Searching and sorting

68R15: Combinatorics on words

68T10: Pattern recognition, speech recognition

Related Items

Unnamed Item, Cartesian Tree Matching and Indexing, A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns, Isometric words based on swap and mismatch distance, The swap matching problem revisited, Pattern matching in pseudo real-time, Approximate string matching with stuck address bits, The approximate swap and mismatch edit distance, Pattern matching with address errors: rearrangement distances, Property matching and weighted matching, Approximate string matching with address bit errors, String matching with up to \(k\) swaps and mismatches, Order-preserving pattern matching indeterminate strings, Exploiting pseudo-locality of interchange distance, Finding patterns and periods in Cartesian tree matching, Fast algorithms for single and multiple pattern Cartesian tree matching, Swap and mismatch edit distance, Order-preserving matching, On a compact encoding of the swap automaton, PATTERN MATCHING WITH SWAPS IN PRACTICE, 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, Pattern Matching with Swaps for Short Patterns in Linear Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient special cases of pattern matching with swaps
• Alphabet dependence in parameterized matching
• Efficient 2-dimensional approximate matching of half-rectangular figures
• String matching under a general matching relation
• An Improved Algorithm For Approximate 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
• A theory of parameterized pattern matching