A comparative study of dictionary matching with gaps: limitations, techniques and challenges

DOI10.1007/s00453-021-00851-6OpenAlexW3179960022MaRDI QIDQ2118199

B. Riva Shalom, Avivit Levy

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00851-6

zbMATH Keywords

pattern matchingdictionary matchingparameterized matchingonline dictionary matching with gaps

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Multiple matching of parameterized patterns
• Fast set intersection and two-patterns matching
• A faster algorithm for matching a set of patterns with variable length don't cares
• On the longest common parameterized subsequence
• Alphabet dependence in parameterized matching
• Dynamic dictionary matching
• Matching a set of strings with variable length don't cares
• Pattern matching on encrypted streams
• Dictionary matching with a bounded gap in pattern or in text
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Improved dynamic dictionary matching
• Online parameterized dictionary matching with one gap
• Online recognition of dictionary with one gap
• Parameterized dictionary matching and recognition with one gap
• Dictionary matching with a few gaps
• Fast and compact regular expression matching
• Mind the gap!
• Towards polynomial lower bounds for dynamic problems
• The string B-tree
• Dynamic Set Intersection
• Dictionary matching and indexing with errors and don't cares
• Arboricity and Subgraph Listing Algorithms
• Efficient string matching
• Finding a Minimum Circuit in a Graph
• A Four Russians algorithm for regular expression pattern matching
• Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
• Alphabet-Independent and Scaled Dictionary Matching
• Text Indexing and Dictionary Matching with One Error
• Threesomes, Degenerates, and Love Triangles
• Higher Lower Bounds from the 3SUM Conjecture
• Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
• Dictionary Matching with One Gap
• Listing Triangles
• A theory of parameterized pattern matching
• Advances in Cryptology - EUROCRYPT 2004
• A Framework for Dynamic Parameterized Dictionary Matching
• Fully Dynamic Orthogonal Range Reporting on RAM

This page was built for publication: A comparative study of dictionary matching with gaps: limitations, techniques and challenges