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 present a fully persistent dynamic LCE structure called FeAVL, based on path copying over AVL trees. For an operation involving strings 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 with high probability, and LCE in worst-case $O(\log n + \log^2 \ell)$ time with high probability, where $\ell$ is the answer; each update creates only $O(\log n)$ new permanent nodes.
We also provide 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_{\text{max}})$, where $I$ is the number of inserted fresh characters and $n_{\text{max}}$ is the maximum string length appearing during the update sequence.
Blogger's Review: This study demonstrates how to achieve fully persistent dynamic string structures using AVL trees and path copying, addressing the limitations of traditional methods under specific conditions. With precise complexity analysis, the FeAVL structure excels in both performance and memory management, showcasing significant potential for applications requiring efficient string operations.