回文树双端修改问题

© 2025 by the Author. Licensee Art and Design, USA. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution -Noncommercial 4.0 International License (CC BY-NC 4.0) ( https://creativecommons.org/licenses/by-nc/4.0/ )

Download PDF

Cite

XML

HTML

Abstract

在回文树已有的单侧修改算法的基础上，本文独立提出了回文树双端修改算法，解决了在字符串两端插入删除字符并维护回文树的问题。此外，本文讨论了广义回文树与持久化回文树的拓展，并给出了它在字符串问题上的应用。

Keywords

数据结构

字符串算法

回文树

References

[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/.

Previous article in this issue

Next article in this issue