On the average-case complexity of pattern matching with wildcards

DOI10.1016/j.tcs.2022.04.009OpenAlexW1517097234MaRDI QIDQ2672571

Carl Barton

Publication date: 13 June 2022

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

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

zbMATH Keywords

pattern matchingaverage-case complexitystringologypattern matching with wildcardspattern matching with don't care symbols

Mathematics Subject Classification ID

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

Uses Software

• BS Seeker
• BSMAP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Less space: indexing for queries with wildcards
• Simple deterministic wildcard matching
• Pattern matching with don't cares and few errors
• String indexing for patterns with wildcards
• Compressed text indexing with wildcards
• Non-standard stringology
• Weighted Ancestors in Suffix Trees
• Space-Efficient String Indexing for Wildcard Pattern Matching.
• Succincter Text Indexing with Wildcards
• Verifying candidate matches in sparse and wildcard matching
• Dictionary matching and indexing with errors and don't cares
• The Complexity of Pattern Matching for a Random String
• Periodicity in data streams with wildcards

This page was built for publication: On the average-case complexity of pattern matching with wildcards