{"ID":2885072,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.05124","arxiv_id":"2508.05124","title":"Text Indexing and Pattern Matching with Ephemeral Edits","abstract":"A sequence $e_0,e_1,\\ldots$ of edit operations in a string $T$ is called ephemeral if operation $e_i$ constructing string $T^i$, for all $i=2k$ with $k\\in\\mathbb{N}$, is reverted by operation $e_{i+1}$ that reconstructs $T$. Such a sequence arises when processing a stream of independent edits or testing hypothetical edits. We introduce text indexing with ephemeral substring edits, a new version of text indexing. Our goal is to design a data structure over a given text that supports subsequent pattern matching queries with ephemeral substring insertions, deletions, or substitutions in the text; we require insertions and substitutions to be of constant length. In particular, we preprocess a text $T=T[0\\mathinner{.\\,.} n)$ over an integer alphabet $Σ=[0,σ)$ with $σ=n^{\\mathcal{O}(1)}$ in $\\mathcal{O}(n)$ time. Then, we can preprocess any arbitrary pattern $P=P[0\\mathinner{.\\,.} m)$ given online in $\\mathcal{O}(m\\log\\log m)$ time and $\\mathcal{O}(m)$ space and allow any ephemeral sequence of edit operations in $T$. Before reverting the $i$th operation, we report all Occ occurrences of $P$ in $T^i$ in $\\mathcal{O}(\\log\\log n + \\text{Occ})$ time. We also introduce pattern matching with ephemeral edits. In particular, we preprocess two strings $T$ and $P$, each of length at most $n$, over an integer alphabet $Σ=[0,σ)$ with $σ=n^{\\mathcal{O}(1)}$ in $\\mathcal{O}(n)$ time. Then, we allow any ephemeral sequence of edit operations in $T$. Before reverting the $i$th operation, we report all Occ occurrences of $P$ in $T^i$ in the optimal $\\mathcal{O}(\\text{Occ})$ time. Along our way to this result, we also give an optimal solution for pattern matching with ephemeral block deletions.","short_abstract":"A sequence $e_0,e_1,\\ldots$ of edit operations in a string $T$ is called ephemeral if operation $e_i$ constructing string $T^i$, for all $i=2k$ with $k\\in\\mathbb{N}$, is reverted by operation $e_{i+1}$ that reconstructs $T$. Such a sequence arises when processing a stream of independent edits or testing hypothetical ed...","url_abs":"https://arxiv.org/abs/2508.05124","url_pdf":"https://arxiv.org/pdf/2508.05124v2","authors":"[\"Solon P. Pissis\"]","published":"2025-08-07T08:01:59Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}