论文标题
用于计算静态和非静态字符串中独特的alindromes的数据结构
Data structures for computing unique palindromes in static and non-static strings
论文作者
论文摘要
据说，$ t $的palindromic substring $ t [i .. j] $是间隔$ [p，q] $ [p，q] $ t $的最短独特的alindromic substring（sups），如果$ t [i .. j] $是$ t [i .. j] $是$ t [i .. j .. j] $ in $ t $ t $ t $ t $ t $ t $ t $ t $ t $ t $ [i] $ [i] $ [i] $ [i] $ [i] SUPS问题是给定长度$ n $的字符串$ t $，用于构建一个可以在任何给定查询间隔计算所有SUPS的数据结构。众所周知，在$ o（n）$ - 时间预处理后，任何SUPS查询都可以在$ o（α）$中回答，其中$α$是输出的SUPS数量[Inoue等，2018]。在本文中，我们首先表明$α$最多是$ 4 $，并且上限很紧。我们还表明，与SUPS密切相关的字符串$ t $的最小独特的alindromic子字节的总和为$ o（n）$。然后，我们提出第一个$ o（n）$ - 位数据结构，可以在恒定时间内回答任何SUPS查询。另外，我们提出了一种算法来解决滑动窗口的SUPS问题，该窗口可以回答$ O（\ log \ log w）$ time中的任何查询，并更新amortized $ o（\logσ+ \ log \ log \ log \ log w）$ time中的数据结构，其中$ w $是窗口的大小，$σ$是Alphabet的大小。此外，我们考虑了编辑后模型中的SUPS问题，并提出了有效的算法。也就是说，我们提出了一种算法，该算法使用$ o（n）$时间进行预处理并回答$ o（\ log n \ log n \ log \ log \ log \ log \ log \ log \ log n + k \ log \ log \ log \ log \ log \ log \ log n）$ time单个字符后的时间。最后，作为副产品，我们提出了一个完全动态的数据结构，用于范围最小查询（RMQ），其中每个查询范围的宽度仅限于poly-logarithmic。受约束的RMQ数据结构可以在恒定时间内回答此类查询，并支持摊销恒定时间中的单元素编辑操作。
A palindromic substring $T[i.. j]$ of a string $T$ is said to be a shortest unique palindromic substring (SUPS) in $T$ for an interval $[p, q]$ if $T[i.. j]$ is a shortest palindromic substring such that $T[i.. j]$ occurs only once in $T$, and $[i, j]$ contains $[p, q]$. The SUPS problem is, given a string $T$ of length $n$, to construct a data structure that can compute all the SUPSs for any given query interval. It is known that any SUPS query can be answered in $O(α)$ time after $O(n)$-time preprocessing, where $α$ is the number of SUPSs to output [Inoue et al., 2018]. In this paper, we first show that $α$ is at most $4$, and the upper bound is tight. We also show that the total sum of lengths of minimal unique palindromic substrings of string $T$, which is strongly related to SUPSs, is $O(n)$. Then, we present the first $O(n)$-bits data structures that can answer any SUPS query in constant time. Also, we present an algorithm to solve the SUPS problem for a sliding window that can answer any query in $O(\log\log W)$ time and update data structures in amortized $O(\logσ+ \log\log W)$ time, where $W$ is the size of the window, and $σ$ is the alphabet size. Furthermore, we consider the SUPS problem in the after-edit model and present an efficient algorithm. Namely, we present an algorithm that uses $O(n)$ time for preprocessing and answers any $k$ SUPS queries in $O(\log n\log\log n + k\log\log n)$ time after single character substitution. Finally, as a by-product, we propose a fully-dynamic data structure for range minimum queries (RmQs) with a constraint where the width of each query range is limited to poly-logarithmic. The constrained RmQ data structure can answer such a query in constant time and support a single-element edit operation in amortized constant time.
