Dynamic Pattern Matching with Wildcards

We study the fully dynamic pattern matching problem where the pattern may contain up to k wildcard symbols, each matching any symbol of the alphabet. Both the text and the pattern are subject to updates (insert, delete, change). We design an algorithm with 𝒪 (n log² n) preprocessing and update/query time 𝒪̃ (kn^k/{k+1} + k² log n). The bound is truly sublinear for a constant k, and sublinear when k = o (log n). We further complement our results with a conditional lower bound: assuming subquadratic preprocessing time, achieving truly sublinear update time for the case k = Ω (log n) would contradict the Strong Exponential Time Hypothesis (SETH). Finally, we develop sublinear algorithms for two special cases: - If the pattern contains w non-wildcard symbols, we give an algorithm with preprocessing time 𝒪 (nw) and update time 𝒪 (w + log n), which is truly sublinear whenever w is truly sublinear. - Using FFT technique combined with block decomposition, we design a deterministic truly sublinear algorithm with preprocessing time 𝒪 (n^1. 8) and update time 𝒪 (n^0. 8 log n) for the case that there are at most two non-wildcards.