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 \sigma and is given in an online manner, then the palindromic tree of S can be constructed in O(n\log\sigma) time with O(n) space. In this paper, we consider the sliding window version of the problem: For a fixed window length d, we propose two algorithms to maintain the palindromic tree of size O(d) for every sliding window S[i.. i+d-1 ] over S, one running in O(n\log\sigma') time with O(d) space where \sigma' \leq d is the maximum number of distinct characters in the windows, and the other running in O(n + d\sigma) time with d \sigma + O(d) space. We also present applications of our algorithms for computing minimal unique palindromic substrings (MUPS) and for computing minimal absent palindromic words (MAPW) for a sliding window.
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 \sigma and is given in an online manner, then the palindromic tree of S can be constructed in O(n\log\sigma) 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\sigma') time with O(d) space where \sigma' \leq d is the maximum number of distinct characters in the windows, and the second one works in O(n + d\sigma) time with (d+2) \sigma + 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.
R
fixed window length
sliding window of length at most
R
propose two algorithms to maintain
present two versions of an algorithm which maintains
R
i+d-1
j
R
one running
where 1 \leq j-i+1 \leq d. The first version works
R
other running
second one works
R
d
(d+2)
R
present applications of our algorithms for computing
show how our algorithms can be applied to efficient computation of
D
for computing