Reconstructing general matching graphs

DOI10.4230/LIPICS.CPM.2024.2MaRDI QIDQ6891099zbMATH OpenFDO

Authors Amihood Amir, Michael Itzhaki

Publication date 2 December 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2024.2

zbMATH Keywords

matching graphsNP-hardnesspattern matchingreconstruction

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• A fast string searching algorithm
• A theory of parameterized pattern matching
• Algorithms on Strings
• Algorithms – ESA 2004
• Alphabet dependence in parameterized matching
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Approximate pattern matching on elastic-degenerate text
• Approximate subset matching with don't cares
• Comparing Degenerate Strings
• Comparing elastic-degenerate strings: algorithms, lower bounds, and applications
• Degenerate string comparison and applications
• Efficient 2-dimensional approximate matching of half-rectangular figures
• Efficient pattern matching in elastic-degenerate strings
• Efficient validation and construction of border arrays and validation of string matching automata
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Elastic-degenerate string matching with 1 error
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Fast Pattern Matching in Strings
• Fast pattern-matching on indeterminate strings
• Faster algorithms for string matching with k mismatches
• Finding patterns and periods in Cartesian tree matching
• Function Matching
• Generalized function matching
• Generalized String Matching
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1044854 (Why is no real title available?)
• scientific article; zbMATH DE number 2119688 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• Inferring strings from Lyndon factorization
• Maximal degenerate palindromes with gaps and mismatches
• On suffix tree detection
• Order-preserving indexing
• Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
• Parameterized matching with mismatches
• Parameterized pattern matching: Algorithms and applications
• Reconstructing parameterized strings from parameterized suffix and LCP arrays
• Simple deterministic wildcard matching
• String inference from longest-common-prefix array
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Verifying and enumerating parameterized border arrays
• Which regular expression patterns are hard to match?

Cited in

(1)

• A unifying taxonomy of pattern matching in degenerate strings and founder graphs

This page was built for publication: Reconstructing general matching graphs

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