Dynamic Pattern Matching with Wildcards
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909998122008576 |
|---|---|
| author | Naeini, Arshia Ataee Mobed, Amir-Parsa Seddighin, Masoud Seddighin, Saeed |
| author_facet | Naeini, Arshia Ataee Mobed, Amir-Parsa Seddighin, Masoud Seddighin, Saeed |
| contents | We study the fully dynamic pattern matching problem where the pattern may contain up to kwildcard 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 O(nlog^2 n) preprocessing and update/query time O(knk/k+1 + k2 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 O(nw) and update time O(w + log n), which is truly sublinear whenever wis truly sublinear. - Using FFT technique combined with block decomposition, we design a deterministic truly sublinear algorithm with preprocessing time O(n^1.8) and update time O(n^0.8 log n) for the case that there are at most two non-wildcards. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16182 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Dynamic Pattern Matching with Wildcards Naeini, Arshia Ataee Mobed, Amir-Parsa Seddighin, Masoud Seddighin, Saeed Data Structures and Algorithms We study the fully dynamic pattern matching problem where the pattern may contain up to kwildcard 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 O(nlog^2 n) preprocessing and update/query time O(knk/k+1 + k2 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 O(nw) and update time O(w + log n), which is truly sublinear whenever wis truly sublinear. - Using FFT technique combined with block decomposition, we design a deterministic truly sublinear algorithm with preprocessing time O(n^1.8) and update time O(n^0.8 log n) for the case that there are at most two non-wildcards. |
| title | Dynamic Pattern Matching with Wildcards |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.16182 |