Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars
This work provides the first fully persistent dynamic LCE structure with worst-case guarantees, addressing a key limitation of previous amortized approaches for applications requiring persistent string operations.
The paper presents FeAVL, a fully persistent dynamic string structure supporting split, concatenate, and updates in worst-case O(log n) time, equality in O(log n) time w.h.p., and LCE in O(log n + log^2 ℓ) time w.h.p., with each update creating only O(log n) new nodes. It also provides a grammar-compressed version with bounded grammar size.
We study fully persistent dynamic strings with equality and longest common extension (LCE) queries. Straightforward full persistence is problematic for the splay-based FeST structure, since the same unbalanced past version can be reused indefinitely and the usual amortized analysis no longer applies. We give a fully persistent dynamic LCE structure, called FeAVL, based on path copying over AVL trees. For an operation involving string(s) of total length $n$, it supports split, concatenate, and single-character updates in worst-case $O(\log n)$ time, equality in worst-case $O(\log n)$ time w.h.p., and LCE in worst-case $O(\log n+\log^2\ell)$ time w.h.p., where $\ell$ is the answer; each update creates only $O(\log n)$ new permanent nodes. We also give a grammar-compressed instantiation via AVL grammars: starting from an initial grammar of size $g_0$, after $U$ updates, the total number of permanent grammar nodes is $O(g_0+I+U\log n_{\max})$, where $I$ is the number of inserted fresh characters and $n_{\max}$ is the maximum string length appearing during the update sequence.