Palindromic trees for a sliding window and its applications

Abstract 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 ≤ j − i + 1 ≤ d . The first version works in O ( n log ⁡ σ ′ ) time with O ( d ) space where σ ′ ≤ 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.