{"ID":5676059,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-05T01:25:09.323207391Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01580","arxiv_id":"2607.01580","title":"Fully Persistent Dynamic LCE via AVL Trees and AVL Grammars","abstract":"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.","short_abstract":"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 pe...","url_abs":"https://arxiv.org/abs/2607.01580","url_pdf":"https://arxiv.org/pdf/2607.01580v1","authors":"[\"Taiki Kaneda\",\"Hiroki Arimura\",\"Shunsuke Inenaga\"]","published":"2026-07-02T01:25:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}