String indexing for patterns with wildcards

DOI10.1007/s00224-013-9498-4zbMath1319.68262DBLPconf/swat/BilleGVV12arXiv1110.5236OpenAlexW2022942275WikidataQ60554398 ScholiaQ60554398MaRDI QIDQ2254487

Søren Vind, Hjalte Wedel Vildhøj, Inge Li Gørtz, Philip Bille

Publication date: 5 February 2015

Published in: Theory of Computing Systems, Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

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

zbMATH Keywords

wildcardsuffix treestring indexingLCP data structurevariable length gap

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (9)

Document retrieval with one wildcard ⋮ Reporting consecutive substring occurrences under bounded gap constraints ⋮ Less space: indexing for queries with wildcards ⋮ String indexing for top-\(k\) close consecutive occurrences ⋮ Fast String Dictionary Lookup with One Error ⋮ Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints ⋮ On the average-case complexity of pattern matching with wildcards ⋮ Gapped indexing for consecutive occurrences ⋮ Dynamic relative compression, dynamic partial sums, and substring concatenation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast index for approximate string matching
• A linear size index for approximate pattern matching
• Simple deterministic wildcard matching
• Text indexing with errors
• Efficient string matching with k mismatches
• Substring Range Reporting
• Approximate String Matching: A Simpler Faster Algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• Verifying candidate matches in sparse and wildcard matching
• Dictionary matching and indexing with errors and don't cares
• Finding Patterns with Variable Length Gaps or Don’t Cares
• Nested Counters in Bit-Parallel String Matching
• Faster and Space-Optimal Edit Distance “1” Dictionary
• Filtering Search: A New Approach to Query-Answering
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Fast parallel and serial approximate string matching
• Faster algorithms for string matching with k mismatches
• Space Efficient Indexes for String Matching with Don’t Cares

This page was built for publication: String indexing for patterns with wildcards