我们研究了具有相等性和最长公共扩展（LCE）查询的完全持久动态字符串。对于基于splay树的FeST结构，直接实现完全持久性存在问题，因为同一个不平衡的过去版本可以无限重用，通常的摊销分析不再适用。
因此，我们提出了一种名为FeAVL的完全持久动态LCE结构，基于AVL树的路径复制。对于总长度为 $n$ 的字符串操作，它支持在最坏情况下以 $O(\log n)$ 时间进行拆分、连接和单字符更新，在最坏情况下以 $O(\log n)$ 时间（高概率）进行相等性检查，以及在最坏情况下以 $O(\log n + \log^2 \ell)$ 时间（高概率）进行LCE查询，其中 $\ell$ 是答案；每次更新仅会创建 $O(\log n)$ 个新的永久节点。
我们还通过AVL语法给出了一个压缩实例化：从初始语法大小为 $g_0$ 开始，在 $U$ 次更新后，永久语法节点的总数为 $O(g_0 + I + U \log n_{\text{max}})$，其中 $I$ 是插入的新字符数量，$n_{\text{max}}$ 是更新序列中出现的最大字符串长度。
博主点评： 该研究展示了如何利用AVL树和路径复制实现完全持久的动态字符串结构，解决了传统方法在特定情况下的局限性。通过对复杂度的精确分析，FeAVL结构在性能和内存管理方面均表现出色，具有广泛的应用潜力，尤其是在需要高效字符串操作的场景中。