Anouk Duyster

collaborators

2 papers

cs.DS2026

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes

Anouk Duyster, Tomasz Kociumaka

A Random Access query to a string $T \in [0.. I ¨ )^{n}$ asks for the character $T [i]$ at a given position $i \in [0.. n)$ . In $O (n lo g I ¨ )$ bits of space, this fundamental task admits cons…

cs.DS2025

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts

Anouk Duyster, Tomasz Kociumaka

Internal Pattern Matching (IPM) queries on a text $T$ , given two fragments $X$ and $Y$ of $T$ such that $∣ Y ∣ < 2∣ X ∣$ , ask to compute all exact occurrences of $X$ within $Y$ . IPM quer…