Takuya Mieno

Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai et al.

The sliding suffix tree (Fiala \& Greene, 1989) is a suffix tree that is maintained for a sliding window $W_i = T[i..i+d-1]$ of size $d$ that shifts over an input text $T$ of length $n$ from left to right, for increasing $i = 1, \ldots, n-d+1$. It is known that the sliding suffix tree can be maintained in $O(n \log σ)$ time with $O(d)$ space, where $σ$ is the alphabet size. Updating the sliding suffix tree from $W_i = T[i..i+d-1]$ to $W_{i+1} = T[i+1..i+d]$ requires the following three major tasks: (1) Delete the leaf that represents the longest suffix $W_i$, (2) Insert new leaves that represent the suffixes of $W_{i+1}$ that appear exactly once in $W_{i+1}$, and (3) After the leaf deletion due to Task (1) and each leaf insertion due to Task (2), maintain the label $\langle \ell, r \rangle$ of every edge as a valid pair in the new window $W_{i+1}$, such that $i+1 \leq \ell \leq r \leq i+d$. In this paper, we present the first algorithm that performs Task (3) in $O(1)$ worst-case time per node deletion/insertion, which leads to another alternative to efficient sliding suffix tree construction. This is an improvement over the existing algorithms by Larsson (1996, 1999) and by Senft (2005) both of which can only perform Task (3) in $O(1)$ amortized time. Our key data structure is a non-trivial extension of leaf pointers, which were originally proposed by Brodnik and Jekovec (2018) for pattern matching with sliding suffix trees.

Takuya Mieno, Tomohiro I

Palindromes are strings that read the same forward and backward. The computation of palindromic structures within strings is a fundamental problem in string algorithms, being motivated by potential applications in formal language theory and bioinformatics. Although the number of palindromic factors in a string of length $n$ can be quadratic, they can be implicitly represented in $O(n \log n)$ bits of space by storing the lengths of all maximal palindromes in an integer array, which can be computed in $O(n)$ time [Manacher, 1975]. In this paper, for any positive constant $ε< 1$, we propose a novel $(3(1+ε)n + o(n))$-bit representation of all maximal palindromes in a string, which enables $O(1)$-time retrieval of the length of the maximal palindrome centered at any given position. The data structure can be constructed in $O(n)$ time from the input string of length $n$. Since Manacher's algorithm and the notion of maximal palindromes are widely utilized for solving numerous problems involving palindromic structures, our compact representation will accelerate the development of more space-efficient solutions to such problems. Indeed, as the first application of our compact representation of maximal palindromes, we present a data structure of size $O(n)$ bits that can compute the longest palindrome appearing in any given factor of a string of length $n$ in $O(\log n)$ time.