Streaming Pattern Matching with d Wildcards

DOI10.4230/LIPICS.ESA.2016.44MaRDI QIDQ4606315zbMATH OpenOpenAlexFDO

Authors Shay Golan, Tsvi Kopelowitz, Ely Porat

Publication date 2 March 2018

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

zbMATH Keywords

don't-caresfingerprintsstreaming pattern matchingwildcards

Mathematics Subject Classification ID

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

Abstract: In the pattern matching with $d$ wildcards problem one is given a text $T$ of length $n$ and a pattern $P$ of length $m$ that contains $d$ wildcard characters, each denoted by a special symbol ${?}^{\prime }$. A wildcard character matches any other character. The goal is to establish for each $m$-length substring of $T$ whether it matches $P$. In the streaming model variant of the pattern matching with $d$ wildcards problem the text $T$ arrives one character at a time and the goal is to report, before the next character arrives, if the last $m$ characters match $P$ while using only $o(m)$ words of space. In this paper we introduce two new algorithms for the $d$ wildcard pattern matching problem in the streaming model. The first is a randomized Monte Carlo algorithm that is parameterized by a constant $0leqdeltaleq1$. This algorithm uses $ildeO(d^{1-delta})$ amortized time per character and $ildeO(d^{1+delta})$ words of space. The second algorithm, which is used as a black box in the first algorithm, is a randomized Monte Carlo algorithm which uses $O(d+logm)$ worst-case time per character and $O(dlogm)$ words of space.

Recommendations

• Streaming pattern matching with \(d\) wildcards
• Pattern matching in multiple streams
• scientific article; zbMATH DE number 7758337
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Pattern matching with arbitrary-length wildcards
• Pattern matching with wildcards and length constraints using maximum network flow
• Real-time streaming string-matching
• Real-time streaming string-matching

Cited in

(9)

• Streaming pattern matching with \(d\) wildcards
• On the average-case complexity of pattern matching with wildcards
• Streaming periodicity with mismatches
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Multi-pattern matching algorithm with wildcards based on bit-parallelism
• scientific article; zbMATH DE number 7758337 (Why is no real title available?)
• Regular languages in the sliding window model
• Pattern matching with wildcards and length constraints using maximum network flow

This page was built for publication: Streaming Pattern Matching with d Wildcards

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606315)