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

DOI10.1007/S00453-021-00851-6MaRDI QIDQ2118199zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

pattern matchingdictionary matchingparameterized matchingonline dictionary matching with gaps

Mathematics Subject Classification ID

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

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

Cites work

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

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)