The palindromic tree (a.k.a. eertree) is a linear-size data structure that provides access to all palindromic substrings of a string. In this paper, we propose a generalized version of eertree, called double-ended eertree, which supports linear-time online double-ended queue operations on the stored string. At the heart of our construction, is a class of substrings, called surfaces, of independent interest. Namely, surfaces are neither prefixes nor suffixes of any other palindromic substrings and characterize the link structure of all palindromic substrings in the eertree. As an application, we develop a framework for range queries involving palindromes on strings, including counting distinct palindromic substrings, and finding the longest palindromic substring, shortest unique palindromic substring and shortest absent palindrome of any substring. In particular, offline queries only use linear space. Apart from range queries, we enumerate palindromic rich strings with a given word in linear time on the length of the given word.
翻译:palindromic 树( a.k.a. a. eertree) 是一个线性大小的数据结构, 能够访问字符串中的所有正弦亚字串。 在本文中, 我们提出一个通用版本的eertree, 称为双成的eertree, 支持存储字符串上的线性在线双成队列操作。 在我们的构造中心, 是一个亚字串的类别, 叫做表面, 具有独立兴趣 。 也就是说, 表面既不是任何其他相干亚字串的前缀, 也不是其后缀, 并且描述该字符串中所有正弦亚字串的链接结构 。 作为应用程序, 我们开发一个范围查询的框架, 涉及字符串上的双成队列, 包括计算不同的相近角亚字串, 并找到最长的交点亚字符串, 最短的近似地盘系亚字串, 和任何子字串中最短的不见的边框。 特别是, 离线查询仅使用线性空间 。 除了范围的查询之外, 我们用线性字串以线性字串列出。 。