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

DOI10.1007/S00453-021-00851-6OpenAlexW3179960022MaRDI QIDQ2118199FDOQ2118199

Authors: Avivit Levy, B. R. Shalom 

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

Recommendations

• Dictionary matching with a few gaps
• Dictionary matching with one gap
• Parameterized dictionary matching and recognition with one gap
• Mind the gap!
• Mind the gap: essentially optimal algorithms for online dictionary matching with one gap

zbMATH Keywords

pattern matchingdictionary matchingparameterized matchingonline dictionary matching with gaps

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Dictionary matching with a few gaps
• Parameterized dictionary matching and recognition with one gap
• A new faster multi-pattern matching algorithm and design in IDS
• String distances and intrusion detection: Bridging the gap between formal languages and computer security

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

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