An Alphabet Independent Approach to Two-Dimensional Pattern Matching

DOI10.1137/S0097539792226321MaRDI QIDQ4291559zbMATH OpenFDO

Authors Amihood Amir, Martin Farach, G. Benson

Publication date 10 May 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539792226321

zbMATH Keywords

multidimensional matchingpattern matchingperiodstring matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• Fast two-dimensional pattern matching
• Two-dimensional dictionary matching
• Two-dimensional pattern matching in linear time and small space
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time

Cited in

(41)

• Analysis of two-dimensional approximate pattern matching algorithms
• Optimal parallel two dimensional text searching on a CREW PRAM
• Inplace run-length 2d compressed search.
• Generalizations of suffix arrays to multi-dimensional matrices.
• Networks of picture processors as problem solvers
• On Fine and Wilf's theorem for bidimensional words.
• On a conjecture on bidimensional words.
• Parallel two dimensional witness computation
• Lower bounds for the number of repetitions in 2D strings
• Towards a real time algorithm for parameterized longest common prefix computation
• Succinct 2D dictionary matching
• Generalized function matching
• Optimal discovery of repetitions in 2D
• Sequential and indexed two-dimensional combinatorial template matching allowing rotations
• A multidimensional critical factorization theorem
• A failure function for multiple two-dimensional pattern matching
• Complexity of sets of two-dimensional patterns
• Optimal parallel randomized renaming
• Compressed matching for feature vectors
• Efficient string matching on packed texts
• Alphabet-Independent and Scaled Dictionary Matching
• Complexity of matching sets of two-dimensional patterns by two-dimensional on-line tessellation automaton
• Optimal two-dimensional compressed matching
• Alphabet-Independent Two-Dimensional Witness Computation
• On linear-time alphabet-independent 2-dimensional pattern matching
• 2D Lyndon words and applications
• THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW
• The number of repetitions in 2D-strings
• Approximation algorithms for maximum two-dimensional pattern matching
• Generalizations of suffix arrays to multi-dimensional matrices.
• Reconstructing parameterized strings from parameterized suffix and LCP arrays
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
• Fast parallel string prefix-matching
• Optimal bounds for distinct quartics
• Reconstructing general matching graphs
• Binomial coefficients of multidimensional arrays
• Better indexing for rectangular pattern matching
• Faster two dimensional scaled matching
• Faster two-dimensional pattern matching with rotations
• Searching for a set of correlated patterns
• Parameterized matching on non-linear structures

This page was built for publication: An Alphabet Independent Approach to Two-Dimensional Pattern Matching

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