TACSTechnology and Application of Computer Science2998-89262998-8934Art and Design10.61369/TACS.2025060006Article回文树双端修改问题https://artdesignp.com/journal/TACS/2/6/10.61369/TACS.2025060006李响2025262025-03-28在回文树已有的单侧修改算法的基础上，本文独立提出了回文树双端修改算法，解决了在字符串两端插入删除字符并维护回文树的问题。此外，本文讨论了广义回文树与持久化回文树的拓展，并给出了它在字符串问题上的应用。数据结构,字符串算法,回文树

 [1]Manacher, G.: A new linear-time on-line algorithm finding the smallest initial palindrome of a string. J. ACM 22(3), 346–351 (1975). [2]Groult, R., Prieur, E., Richomme, G. Counting distinct palindromes in a word in linear time. Inform. Process. Lett. 110, 908–912 (2010). [3]Kosolobov, D., Rubinchik, M., Shur, A.M.: Finding distinct subpalindromes online. In: Proc. Prague Stringology Conference. PSC 2013. pp. 63–69. Czech Technical University in Prague (2013). [4] 徐毅. 浅谈回文子串问题. 北京: 2014年信息学奥林匹克中国国家队候选队员论文集, 2014. [5]Mikhail Rubinchik, Arseny M. Shur. EERTREE: An Efficient Data Structure for Processing Palindromes in Strings. arXiv:1506.04862 (2015). [6] 翁文涛. 回文树及其应用. 北京: IOI2017中国国家候选队论文集, 2017. [7] 徐安矣. 浅谈回文串问题的相关算法及其应用. 北京: 2023年信息学奥林匹克中国国家集训队论文, 2017. [8]OI-Wiki. 可持久化线段树.https://oi-wiki.org/ds/persistent-seg/. [9]2017山东一轮集训Day4. 基因. https://loj.ac/p/6070. [10]OI-Wiki. 普通莫队算法. https://oi-wiki.org/misc/mo-algo/.