Dictionary matching with a few gaps

DOI10.1016/j.tcs.2015.04.011zbMath1319.68106arXiv1408.2350MaRDI 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 matching; dictionary matching; gapped patterns

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W32: Algorithms on strings

Related Items

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

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