Computing Palindromic Trees for a Sliding Window and Its Applications
share
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(nlogσ) 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(nlogσ') time with O(d) space where σ' ≤ d is the maximum number of distinct characters in the windows, and the other running in O(n + dσ) time with dσ + 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.
READ FULL TEXT