Dictionary matching with a few gaps

DOI10.1016/j.tcs.2015.04.011zbMath1319.68106arXiv1408.2350OpenAlexW1978055030MaRDI QIDQ2346375

Avivit Levy, B. Riva Shalom, Ely Porat, Amihood Amir

Publication date: 1 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.2350

zbMATH Keywords

string matchingdictionary matchinggapped patterns

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items

Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Online parameterized dictionary matching with one gap ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ Online recognition of dictionary with one gap ⋮ Parameterized dictionary matching and recognition with one gap ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Real-Time Streaming Multi-Pattern Search for Constant Alphabet ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

Cites Work

• Unnamed Item
• String matching with variable length gaps
• A faster algorithm for matching a set of patterns with variable length don't cares
• Dynamic dictionary matching
• Matching a set of strings with variable length don't cares
• Truncated suffix trees and their application to data compression.
• New techniques for regular expression searching
• Improved dynamic dictionary matching
• On-line construction of suffix trees
• Dictionary matching and indexing with errors and don't cares
• Finding Patterns with Variable Length Gaps or Don’t Cares
• Faster Regular Expression Matching
• Efficient string matching
• A Space-Economical Suffix Tree Construction Algorithm
• A Four Russians algorithm for regular expression pattern matching
• Alphabet-Independent and Scaled Dictionary Matching
• Text Indexing and Dictionary Matching with One Error
• Orthogonal range searching on the RAM, revisited