Dynamic Pattern Matching with Wildcards

Pattern matching is a fundamental problem in computer science with applications in text search, bioinformatics, log analysis, and data mining [37, 40, 20, 2, 25, 6, 36, 12, 15, 11, 28]. In its basic form, given a pattern P of length $m$ and a text T of length $n$ with symbols from alphabet $\mathrm{\Sigma }$ with size $\sigma$, the task is to decide whether P occurs in T as a contiguous substring; that is, whether there exists an index $i\in \{1,\mathrm{\dots },n-m+1\}$ such that ${\text{T}}_{i:i+m-1}=\text{P}.$ This problem has been studied for decades, and many efficient linear-time solutions such as the Knuth–Morris–Pratt and Boyer–Moore algorithms are well known [32, 10].

Traditionally, pattern matching aims to find exact occurrences of a pattern, yet in many practical applications such rigidity is unrealistic [41, 33, 35, 23]. The pattern or the text may contain uncertain or corrupted symbols due to noise, ambiguity, or small variations; for example when accounting for mutations in genomic data. This motivates the study of algorithms that search for substrings close to the pattern under standard distance measures such as Hamming distance [1, 13, 27]. Another common way to model uncertainty is to assume that the positions of the corrupted symbols are known. This is typically handled by introducing a wildcard symbol, which matches any single symbol of the alphabet $\mathrm{\Sigma }$ [22, 26, 29]. This gives rise to the problem of pattern matching with wildcards, where across both the pattern and the text, the total number of wildcard positions is at most $k$. Since each wildcard can stand for any symbol of $\mathrm{\Sigma }$, a pattern with $k$ wildcards implicitly represents up to ${|\mathrm{\Sigma }|}^k$ different strings.

Adding wildcards makes the pattern matching problem harder. With a fixed pattern, the search space is small. For example, let the text be $\text{T}=\text{CACCGGCT}$ and the pattern be $\text{P}=\text{CG}$. For this instance, there is only one match. If we instead use ${\text{P}}^{\prime }=\text{C?}$, where “?” refers to the wildcard symbol, then every occurrence of C in T becomes a match. This simple change increases the number of matches from $1$ to $4$. Thus, even limited uncertainty can drastically increase the complexity of the problem.

A substantial body of work has studied pattern matching with wildcards in either the pattern or the text [29, 8, 5]. For this problem, Fischer and Paterson [22] gave an $𝒪(n\log m\log \sigma )$ algorithm, and later Indyk [26] gave a randomized $𝒪(n\log n)$ algorithm. Kalai [29] subsequently obtained a randomized $𝒪(n\log m)$ algorithm, while the first deterministic $𝒪(n\log m)$ algorithm was given by Cole and Hariharan [17].

In this paper, we study pattern matching with wildcards in a fully dynamic setting. Both the text and the pattern may change through insertions, deletions, or substitutions, including updates to wildcard positions. Our goal is to maintain pattern-matching queries in sublinear time. For dynamic pattern matching, most prior work considers settings without wildcards. In these studies, dynamism may arise in several ways: the text may be updated dynamically, the pattern may be updated dynamically, or both may change over time. All three cases have been studied extensively. For dynamic text with a static pattern, Amir et al. [4] presented an algorithm that preprocesses a text of length $n$ and a pattern of length $m$ in $𝒪(n\log \log m+m\sqrt{\log m})$ time, reporting all new occurrences of the pattern after each text update in $𝒪(\log \log m)$ time.

For static text with a dynamic pattern, efficient suffix tree based solutions were introduced by Weiner [43] and later improved by McCreight [34], Ukkonen [42], Farach [19], and others [30]. For a fixed finite alphabet, these algorithms preprocess the text in $𝒪(n)$ time and answer pattern queries in $𝒪(m+\mathrm{𝑜𝑐𝑐})$ time, where $\mathrm{𝑜𝑐𝑐}$ is the number of occurrences of the pattern. Finally, in the fully dynamic setting where both text and pattern may change, several algorithms have been developed [24, 21, 38, 3]. For example, Sahinalp and Vishkin [38] support insertions and deletions in $𝒪({\log }^{3}n+m)$ time per update, with query times comparable to Weiner’s static algorithm. Alstrup, Brodal, and Rauhe [3] handle insertions, deletions, and substring moves in $𝒪({\log }^{2}n\log \log n{\log }^{\ast }n)$ time per update, and answer pattern searches in $𝒪(\log n\log \log n+m+\mathrm{𝑜𝑐𝑐})$ time.

Our work extends these dynamic pattern matching studies to consider wildcards. We provide a randomized algorithm that, after $𝒪(n{\log }^{2}n)$ preprocessing, supports updates and queries in amortized time $\widetilde{𝒪}\left(k{n}^{\frac{k}{k+1}}+k^2\log n\right),$ which is sublinear for $k=o(\log n)$ and truly sublinear for constant $k$. We also show that this bound is almost tight: under SETH, no algorithm with subquadratic preprocessing time can achieve truly sublinear update time when $k=\mathrm{\Omega }(\log n)$. In addition to the general result, we design specialized algorithms for two restricted settings, with the complexity expressed in terms of the number of non-wildcard symbols in the pattern.

1. 1.

   When the wildcard positions are fixed, we obtain preprocessing in $𝒪(nw)$ time and support updates in time $𝒪(w+\log n)$ time, where $w$ is the number of non-wildcard symbols.

2. 2.

   When the pattern contains at most two non-wildcard symbols, we give a deterministic algorithm based on FFT and block decomposition techniques, with preprocessing time $𝒪(n^{1.8})$ and update time $𝒪(n^{0.8}\log n)$.

We study the problem of dynamic pattern matching in the presence of wildcard symbols. Our contributions fall into two main lines.

We consider a finite alphabet $\mathrm{\Sigma }$ of size $|\mathrm{\Sigma }|=\sigma$. Our input consists of two strings: a text $\text{T}\in {(\mathrm{\Sigma }\cup \{\text{?}\})}^{\ast }$ of length $n$, and a pattern $\text{P}\in {(\mathrm{\Sigma }\cup \{\text{?}\})}^{\ast }$ of length $m$. Both the text and the pattern together may contain at most $k$ wildcard symbols, denoted by ?. A wildcard symbol can match any symbol from the alphabet.

For a string $S$ and $1\le \mathrm{\ell }\le r\le |S|$, we use $S_{\mathrm{\ell }:r}$ to denote the substring $S_{\mathrm{\ell }}{S}_{\mathrm{\ell }+1}\mathrm{\dots }{S}_r.$ For example, if $S=\text{abcde}$, then $S_{2:4}=\text{bcd}$. We say that P matches a substring ${\text{T}}_{i:i+m-1}$ ($1\le i\le n-m+1$) if for every $1\le j\le m$, either ${\text{P}}_j={\text{T}}_{i+j-1}$, ${\text{P}}_j=\text{?}$ or ${\text{T}}_{i+j-1}=\text{?}$. The set of all matching positions is denoted by

The concatenation of two strings $S$, $S^{\prime }$, denoted $S\cdot S^{\prime }$, is defined by appending $S^{\prime }$ to the end of $S$. For instance, if $S=\text{ab}$ and $S^{\prime }=\text{cd}$, then $S\cdot S^{\prime }=\text{abcd}$.

We classify symbols in $\mathrm{\Sigma }$ as frequent or rare according to a frequency threshold. Let the threshold value be

A symbol $c\in \mathrm{\Sigma }$ is called rare if it occurs fewer than $\tau$ times in T, and frequent otherwise.

For each symbol $c\in (\mathrm{\Sigma }\cup \text{?})$, we maintain the set $\Re (c)=\{i\mid 1\le i\le n,{\text{T}}_i=c\},$ which stores all positions where $c$ appears in T. In addition to membership queries for $\Re (c)$, we also require efficient support for lower bound queries, i.e., finding the smallest index in $\Re (c)$ that is greater than or equal to a given value. For handling the updates and queries efficiently, we use balanced binary search trees.

Many of our algorithms are randomized and succeed with high probability. Throughout this paper, we say an event occurs with high probability if it holds with probability at least $1-1/n$.

The foundation for our analysis, based on polynomial hashing, is detailed in Handling Matching Query section in the full version. We use a polynomial rolling hash with a prime modulus $p$ [31] to efficiently support matching queries. The hash function is formally defined as follows.

We leverage the following lemma from Handling Matching Query section to prove our probabilistic claims in the paper.

In this section, we consider the general case of dynamic pattern matching with wildcards problem. Note that here both the text T and the pattern P may contain wildcard symbols. We assume that updates consist only of single-character substitutions, and do not include insertions or deletions. This simplifies the presentation of the main ideas. We will later explain in the full version how the algorithm extends to handle insertions and deletions as well.

Our solution is based on maintaining a modified version of the text, denoted by T’, where every rare symbol is replaced with a special placeholder “#”. Therefore, T’ is defined as

Note that the frequency of symbols may change during the dynamic updates. Whenever the frequency of a symbol crosses the threshold $\tau$, we update T’ by replacing its occurrences with “#” (if it becomes rare) or restoring them to the original symbol (if it becomes frequent). To implement this, we maintain for each symbol $c\in \mathrm{\Sigma }$ the occurrence set $\Re (c)$. When the text is updated at position $i$ from $c_{\text{old}}$ to $c_{\text{new}}$, we remove $i$ from $\Re (c_{\text{old}})$ and insert it into $\Re (c_{\text{new}})$. If the frequency of a frequent symbol falls below $\tau$, we mark its $\tau$ occurrences in T’ with the placeholder “#”; conversely, if a rare symbol becomes frequent, we restore its actual symbol at those positions. Each such change involves only $𝒪(\tau )$ positions, giving an update cost of $𝒪(\tau )$. The full procedure is formalized in the full version.

The preprocessing phase (Algorithm 1) initializes the data structures, including building T’, maintaining occurrence sets $\Re (\cdot )$ for each symbol, and computing the frequent set F. The algorithm that, after each update, maintains these structures efficiently is explained in the full version.

Given this setup, the matching procedure proceeds differently depending on whether the pattern contains a rare symbol. If it does (Case 1, Algorithm 2), then any valid match must align that rare symbol either with one of its actual occurrences in the text or with one of the wildcard positions in the text. This observation allows us to restrict attention to candidate substrings centered around these positions in T, checking them directly for consistency with the rest of the pattern.

If, on the other hand, the pattern contains no rare symbols (Case 2, Algorithm 3), then each wildcard may be filled with either a frequent symbol or the placeholder “#”. We systematically enumerate all possible completions of both the pattern and the text under this rule and verify each candidate against T’ using efficient LCS queries. Since the number of completions depends only on the number of wildcards and the frequency threshold, this approach avoids recomputation from scratch after updates and remains tractable when the number of wildcards is small.

The overall procedure is summarized in Algorithm 4, and the correctness and efficiency of the algorithm are proved in Theorem 4.1. In the interest of space, the proof of Theorem 4.1 is deferred to the full version.

In this section we study sparse patterns, namely patterns $P\in {(\mathrm{\Sigma }\cup \{\text{?}\})}^m$ in which only a few positions are non-wildcard and the remaining positions are wildcards. Let $S=\{i\in [m]:{\text{P}}_i\in \mathrm{\Sigma }\}$ be the set of non-wildcard indices and let $s=|S|\ll m$. Such sparse patterns naturally arise in applications such as biological sequence analysis, where only a few positions of a motif are fixed while the rest may vary, or in intrusion detection, where signatures often contain only a few fixed bytes. In this section we consider two regimes: (i) the case where the pattern contains at most two non-wildcard symbols, and (ii) the case where the wildcard positions in the pattern are fixed in advance and the text T contains no wildcards. Throughout this section we work in a substitution-only dynamic model: updates may change symbols in the text or in the pattern, but no insertions or deletions are allowed, so both lengths $n$ and $m$ (and, in the fixed-wildcard regime, the wildcard index set) remain fixed.

In this section, we establish a conditional lower bound for Dynamic Pattern Matching with Wildcards through a reduction from the Orthogonal Vectors problem. Our goal is to show that any significant improvement in the query time for Dynamic Pattern Matching with Wildcards would imply a breakthrough for Orthogonal Vectors , which is widely believed to be unlikely under the Strong Exponential Time Hypothesis ($\mathrm{𝖲𝖤𝖳𝖧}$).

Williams [44] establishes the following connection between Orthogonal Vectors and $\mathrm{𝖲𝖤𝖳𝖧}$.

We now show a reduction of Orthogonal Vectors to Dynamic Pattern Matching with Wildcards. This reduction forms the backbone of our lower bound.