Dynamic Pattern Matching with Wildcards

Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin, Saeed Seddighin · 2026

Read Dynamic Pattern Matching with Wildcards by Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin, Saeed Seddighin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16182.txt.

Introduction

Arshia Ataee Naeini and three coauthors solve live text search with wild card marks. Their 2026 preprint deals with search where marks can stand for any sign. Up to a set count of wild marks may sit in the search term. Both the text and the term can change live. Changes span add, drop and swap of signs.

The team gives steps that keep search fast through all such changes. Fast live search serves code bases and data sets that shift oft. Wild marks add reach but also add cost to each check. Steps that hold cost down have wide use. The work is in the theory of text code steps.

Catalog record

CREATORArshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin, Saeed Seddighin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16182

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Pattern Matching with Wildcards Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin, Saeed Seddighin Abstract We study the fully dynamic pattern matching problem where the pattern may contain up to k 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 2 ​ n ) \mathcal{O}(n\log^{2}n) preprocessing and update/query time 𝒪 ~ ​ ( k ​ n k / k + 1 + k 2 ​ log ⁡ n ) \tilde{\mathcal{O}}(kn^{k/{k+1}}+k^{2}\log n) . The bound is truly sublinear for a constant k k , and sublinear when k = o ⁡ ( log ⁡ n ) 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 ) k=\Omega(\log n) would contradict the Strong Exponential Time Hypothesis (SETH). Finally, we develop sublinear algorithms for two special cases: • If the pattern contains w w non-wildcard symbols, we give an algorithm with preprocessing time 𝒪 ⁡ ( n ​ w ) \mathcal{O}(nw) and update time 𝒪 ⁡ ( w + log ⁡ n ) \mathcal{O}(w+\log n) , which is truly sublinear whenever w w is truly sublinear. • Using FFT technique combined with block decomposition, we design a deterministic truly sublinear algorithm with preprocessing time 𝒪 ⁡ ( n 1.8 ) \mathcal{O}(n^{1.8}) and update time 𝒪 ⁡ ( n 0.8 ​ log ⁡ n ) \mathcal{O}(n^{0.8}\log n) for the case that there are at most two non-wildcards. 1 Introduction Pattern matching is a fundamental problem in computer science with applications in text search, bioinformatics, log analysis, and data mining [ Pandiselvam et al., 2014 , Tahir, 2017 , Faro and Lecroq, 2013 , Abrishami et al., 2013 , Hakak et al., 2019 , Amit et al., 2014 , Neamatollahi et al., 2020 , Capacho et al., 2017 , Cheng et al., 2013 , Bushong et al., 2020 , Johannesmeyer et al., 2002 ] . In its basic form, given a pattern P of length m and a text T of length n with symbols from alphabet \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,\dots,n-m+1\} such that \textsf{T}_{i:i+m-1}=\textsf{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 [ Knuth et al., 1977 , Boyer and Moore, 1977 ] . Traditionally, pattern matching aims to find exact occurrences of a pattern, yet in many practical applications such rigidity is unrealistic [ Ukkonen, 1985 , Landau and Vishkin, 1988 , Navarro, 2001 , Galil and Park, 1990 ] . 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 [ Abrahamson, 1987 , Chan et al., 2023 , Jin and Xu, 2024 ] . 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 \Sigma [ Fischer and Paterson, 1974 , Indyk, 1998 , Kalai, 2002 ] . 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 \Sigma , a pattern with k wildcards implicitly represents up to |\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 \textsf{T}=\texttt{CACCGGCT} and the pattern be \textsf{P}=\texttt{CG} . For this instance, there is only one match. If we instead use \textsf{P}^{\prime}=\texttt{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 [ Kalai, 2002 , Bathie et al., 2024b , Amir et al., 2004 ] . For this problem, Fischer and Paterson [ Fischer and Paterson, 1974 ] gave an \mathcal{O}(n\log m\log\sigma) algorithm, and later Indyk [ Indyk, 1998 ] gave a randomized \mathcal{O}(n\log n) algorithm. Kalai [ Kalai, 2002 ] subsequently obtained a randomized \mathcal{O}(n\log m) algorithm, while the first deterministic \mathcal{O}(n\log m) algorithm was given by Cole and Hariharan [ Cole and Hariharan, 2002b ] . 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. [ Amir et al., 2007a ] presented an algorithm that preprocesses a text of length n and a pattern of length m in \mathcal{O}(n\log\log m+m\sqrt{\log m}) time, reporting all new occurrences of the pattern after each text update in \mathcal{O}(\log\log m) time. For static text with a dynamic pattern, efficient suffix tree based solutions were introduced by Weiner [ Weiner, 1973a ] and later improved by McCreight [ McCreight, 1976 ] , Ukkonen [ Ukkonen, 1995 ] , Farach [ Farach, 1997 ] , and others [ Kärkkäinen and Sanders, 2003 ] . For a fixed finite alphabet, these algorithms preprocess the text in \mathcal{O}(n) time and answer pattern queries in \mathcal{O}(m+\mathit{occ}) time, where \mathit{occ} 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 [ Gu et al., 1994 , Ferragina and Grossi, 1995 , Sahinalp and Vishkin, 1996 , Alstrup et al., 2000 ] . For example, Sahinalp and Vishkin [ Sahinalp and Vishkin, 1996 ] support insertions and deletions in \mathcal{O}(\log^{3}n+m) time per update, with query times comparable to Weiner’s static algorithm. Alstrup, Brodal, and Rauhe [ Alstrup et al., 2000 ] handle insertions, deletions, and substring moves in \mathcal{O}(\log^{2}n\log\log n\log^{*}n) time per update, and answer pattern searches in \mathcal{O}(\log n\log\log n+m+\mathit{occ}) time. Our work extends these dynamic pattern matching studies to consider wildcards. We provide a randomized algorithm that, after \mathcal{O}(n\log^{2}n) preprocessing, supports updates and queries in amortized time \tilde{\mathcal{O}}\left(kn^{\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

Read the complete text