Two-dimensional pattern matching in linear time and small space

DOI10.1007/3-540-59042-0_72MaRDI QIDQ4596620zbMATH OpenOpenAlexFDO

Authors Maxime Crochemore, Wojciech Plandowski, Leszek Gąsieniec, Wojciech Rytter

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_72

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• On linear-time alphabet-independent 2-dimensional pattern matching
• Fast two-dimensional pattern matching
• Approximation algorithms for maximum two-dimensional pattern matching
• scientific article; zbMATH DE number 1003305
• Fast algorithms for two dimensional and multiple pattern matching
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching
• Analysis of two-dimensional approximate pattern matching algorithms
• Dynamic and approximate pattern matching in 2D

Cited in

(13)

• Fast two-dimensional pattern matching
• The zooming method: A recursive approach to time-space efficient string-matching
• Dynamic and approximate pattern matching in 2D
• On the computational complexity of 2-interval pattern matching problems
• Succinct 2D dictionary matching
• Pattern Matching with Swaps for Short Patterns in Linear Time
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• On linear-time alphabet-independent 2-dimensional pattern matching
• Two-dimensional pattern matching by sampling
• Optimal bounds for distinct quartics
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Pattern matching in doubling spaces

This page was built for publication: Two-dimensional pattern matching in linear time and small space

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