Fast algorithms for two dimensional and multiple pattern matching

DOI10.1007/3-540-52846-6_102MaRDI QIDQ5056115zbMATH OpenOpenAlexFDO

Authors Mireille Régnier, Ricardo Baeza-Yates

Publication date 9 December 2022

Published in SWAT 90 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-52846-6_102

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• Fast two-dimensional pattern matching
• A failure function for multiple two-dimensional pattern matching
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• scientific article; zbMATH DE number 1003305
• Fastest Pattern Matching in Strings

Cites work

• A Correct Preprocessing Algorithm for Boyer–Moore String-Searching
• A fast string searching algorithm
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 432780 (Why is no real title available?)
• scientific article; zbMATH DE number 17821 (Why is no real title available?)
• scientific article; zbMATH DE number 140461 (Why is no real title available?)
• scientific article; zbMATH DE number 3633757 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• The Complexity of Pattern Matching for a Random String

Cited in

(22)

• Analysis of two-dimensional approximate pattern matching algorithms
• Average running time of the Boyer-Moore-Horspool algorithm
• Fast two-dimensional pattern matching
• Constant-space string-matching in sublinear average time
• Fast practical multi-pattern matching
• Dynamic and approximate pattern matching in 2D
• Multiple matching of rectangular patterns
• Fast string matching for multiple searches
• Looking for MUM and DAD: text-text comparisons do help
• scientific article; zbMATH DE number 2185645 (Why is no real title available?)
• scientific article; zbMATH DE number 1003305 (Why is no real title available?)
• New multi-pattern matching algorithm
• Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms
• Two-dimensional pattern matching in linear time and small space
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• On linear-time alphabet-independent 2-dimensional pattern matching
• Exact online two-dimensional pattern matching using multiple pattern matching algorithms
• Fast-search algorithms: new efficient variants of the Boyer-Moore pattern-matching algorithm
• Two-dimensional pattern matching by sampling
• A simple fast hybrid pattern-matching algorithm
• Fast profile matching algorithms - A survey
• A faster algorithm for matching a set of patterns with variable length don't cares

This page was built for publication: Fast algorithms for two dimensional and multiple pattern matching

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