论文标题
滑动窗口及其应用
Palindromic Trees for a Sliding Window and Its Applications
论文作者
论文摘要
使用$ o（n）$ space [Rubinchik和Shur，2018年，代表$ n $ s $ s $ s $ n $ s $ n $的字符串$ s $ n $的字符串$ s $ s $ s $ n $的字符串$ s $ n $的字符串$ s $ s $ [RUBINCHIK和SHUR，2018年]。众所周知，当$ s $超过尺寸$σ$的字母，并以在线方式给出时，则可以用$ o（n \logσ）$ time用$ o（n）$ space构建$ s $的palindromic树。在本文中，我们考虑了该问题的滑动窗口版本：对于最多$ d $的长度滑动窗口，我们提供了两个版本的算法，该算法维持每个滑动窗口$ s [i..j] $ over $ s $的大小$ o（d）$的palindromic树，其中$ 1 \ leq j-iq j-i+1 \ iq j-i+1 \ leq d $。第一个版本可在$ o（n \logσ'）$ time中使用$ o（d）$ space，其中$σ'\ leq d $是窗口中不同字符的最大数量，第二个是$ o（n+dσ）$ time的$（d+ 2）σ+ o（d+ o（d）$（d）$（n+dσ）$（d）。我们还展示了如何将算法应用于对滑动窗口的最小独特的独特子字（MUP）和最小缺乏的allindromic单词（MAPW）的有效计算。
The palindromic tree (a.k.a. eertree) for a string $S$ of length $n$ is a tree-like data structure that represents the set of all distinct palindromic substrings of $S$, using $O(n)$ space [Rubinchik and Shur, 2018]. It is known that, when $S$ is over an alphabet of size $σ$ and is given in an online manner, then the palindromic tree of $S$ can be constructed in $O(n\logσ)$ time with $O(n)$ space. In this paper, we consider the sliding window version of the problem: For a sliding window of length at most $d$, we present two versions of an algorithm which maintains the palindromic tree of size $O(d)$ for every sliding window $S[i..j]$ over $S$, where $1 \leq j-i+1 \leq d$. The first version works in $O(n\logσ')$ time with $O(d)$ space where $σ' \leq d$ is the maximum number of distinct characters in the windows, and the second one works in $O(n + dσ)$ time with $(d+2)σ+ O(d)$ space. We also show how our algorithms can be applied to efficient computation of minimal unique palindromic substrings (MUPS) and minimal absent palindromic words (MAPW) for a sliding window.
