线性时间双端回文树 (Double-Ended Palindromic Trees in Linear Time)

from arxiv, Full version, 64 pages, 2 tables, 17 algorithms. Title changed, abstract improved, some proofs simplified, the persistent part removed for simplicity

The palindromic tree (a.k.a. eertree) is a data structure that provides access to all palindromic substrings of a string. In this paper, we propose a dynamic version of eertree, called double-ended eertree, which supports online operations on the stored string, including double-ended queue operations, counting distinct palindromic substrings, and finding the longest palindromic prefix/suffix. At the heart of our construction, we identify a new class of substring occurrences, called surfaces, that are palindromic substring occurrences that are neither prefixes nor suffixes of any other palindromic substring occurrences, which is of independent interest. Surfaces characterize the link structure of all palindromic substrings in the eertree, thereby allowing a linear-time implementation of double-ended eertrees through a linear-time maintenance of surfaces.

翻译：回文树（亦称eertree）是一种能够提供字符串所有回文子串访问的数据结构。本文提出一种动态版本的eertree，称为双端eertree，其支持对存储字符串的在线操作，包括双端队列操作、统计不同回文子串数量以及查找最长回文前缀/后缀。我们构建方法的核心在于识别出一类新的子串出现形式，称为表面（surfaces），即那些既不是其他回文子串出现的前缀也不是后缀的回文子串出现，这一概念本身具有独立研究价值。表面刻画了eertree中所有回文子串的链接结构，从而通过表面的线性时间维护，实现了双端eertree的线性时间构建。