Compact Representation of Maximal Palindromes

Manacher’s algorithm [18] can output an integer array of linear length, occupying $O(n\log n)$ bits of space, that stores the lengths of all maximal palindromes in a string $w$ of length $n$. If we are interested in the variety of distinct palindromic factors in $w$, rather than their occurrences, we can store them using the palindromic tree (a.k.a. EERTREE) data structure, which requires $O(d\log n)$ bits of space [25], where $d$ is the number of distinct palindromic factors in $w$ and is known to be at most $n+1$ [4]. The palindromic tree of $w$ can be extremely small when $w$ has very few distinct palindromic factors; however, it does not support locating occurrences of palindromic factors in $w$. Charalampopoulos et al. [3] presented an $O(n/{\log }_{\sigma }n)$-time (namely, sublinear-time) algorithm for computing a longest palindromic factor in $w$, assuming that the alphabet size $\sigma$ is small and that $w$ is given in a packed representation occupying $O(n\log \sigma )$ bits of space. Recently, Mieno and Funakoshi [20] proposed an $O(n)$-bit data structure that represents all unique palindromic factors in $w$, where a factor is said to be unique if it occurs exactly once in $w$.

For non-negative integers $i,j$ with $i\le j$, let $[i..j]=\{i,i+1,\mathrm{\dots },j\}$ be the set of consecutive integers from $i$ to $j$. Further, let $[i..j)=[i..j]\setminus \{j\}$. Note that $[i..i)=\mathrm{\varnothing }$. We sometimes refer to a set $[i..j]$ of consecutive integers as an interval.

Let $\mathrm{\Sigma }$ be an alphabet of size $\sigma$. An element in $\mathrm{\Sigma }$ is called a character. An element in ${\mathrm{\Sigma }}^{\star }$ is called a string. The length of string $w$ is denoted by $|w|$. The string of length zero is called the empty string. If $w=xyz$ holds for strings $w,x,y,z\in {\mathrm{\Sigma }}^{\star }$, then $x$, $y$, and $z$ are called a prefix, a factor, and a suffix of $w$, respectively. For a string $w$ and integers $i,j\in [0..|w|)$, we denote by $w[i]$ the $i$-th character of $w$, and by $w[i..j]$ the factor of $w$ that starts at position $i$ and ends at position $j$. For convenience, let $w[i..j]$ be the empty string if $i>j$. We denote by $w^R$ the reversal of string $w$, i.e., $w^R=w[|w|-1]w[|w|-2]\mathrm{\cdots }w[0]$. A positive integer $p$ is called a period of a string $w$ if $w[i]=w[i+p]$ holds for all $i\in [0..|w|-p)$. We also say that $w$ has a period $p$ if $p$ is a period of $w$. If string $w$ has a period $p^{\star }$ with $p^{\star }\le |w|/2$, then $w$ is said to be periodic.

A string $w$ is called a palindrome if $w=w^R$ holds. Note that the empty string is a palindrome. A factor of a string is called palindromic if it is a palindrome. An occurrence of a palindromic factor $w[i..j]$ of $w$ is called a maximal palindrome if (1) $i=0$, (2) $j=|w|-1$, or (3) $w[i-1]\ne w[j+1]$. A palindrome is called an even-palindrome (resp. odd-palindrome) if its length is even (resp. odd). Throughout this paper, we focus only on even-palindromes. As discussed in Section 3 of [2], if we are interested in odd-palindromes, we can convert the input string $w$ into $\widehat{w}=w[0]w[0]w[1]w[1]\mathrm{\cdots }w[n-1]w[n-1]$, which is obtained by doubling each character of $w$. Then, Observation 1 holds:

Namely, detecting palindromes in a string of length $n$ can be reduced to detecting even-palindromes in a string of length $2n$. In the rest of this paper, we simply refer to “even-palindromes” as “palindromes” unless otherwise specified.

If $w[c-r..c+r-1]$ is a palindromic factor of $w$ for some non-negative integers $c$ and $r$, we say that $c$ is the center of $w[c-r..c+r-1]$, or $w[c-r..c+r-1]$ is centered at $c$. Note that $c$ is not exactly the median of interval $[c-r..c+r-1]$, but it is the first position of the right half of the interval. For notational simplicity, we sometimes say that a factor is the MPal at $c$ if the factor is the maximal palindrome centered at $c$.

In what follows, we arbitrarily fix the input string $w$ of length $n$. In this paper, when we omit the base of $\log$, it is two. Our computation model is a standard word RAM model of word size $\mathrm{\Omega }(\log n)$. We assume that every character from $\mathrm{\Sigma }$ fits within a single machine word, i.e., given two characters, the equality of them can be determined in constant time.

Manacher [18] proposed a linear-time algorithm to compute the longest palindromic factors in a given string, which inherently computes all the maximal palindromes in the string. By running Manacher’s algorithm, we can obtain a representation of the maximal palindromes in $w$ in linear time. In this paper, we define the maximal even-palindrome array ${\mathrm{𝖬𝖤𝖯𝖺𝗅}}_w$ of length $n$ as follows: ${\mathrm{𝖬𝖤𝖯𝖺𝗅}}_w[c]$ stores the length of the MPal at $c$ in $w$ for every $c\in [0..n)$. Next, we define the longest even-palindrome array ${\mathrm{𝖫𝖤𝖯𝖺𝗅}}_w$ of length $n$ such that ${\mathrm{𝖫𝖤𝖯𝖺𝗅}}_w[j]$ stores the length of the longest even-palindrome that is a suffix of $w[0..j]$ for every $j\in [0..n)$. We may omit subscripts if they are clear from the context. The following lemma can be shown in a similar way to Lemma 2 of [11].

Using Lemma 2, we can compactly encode array $\mathrm{𝖬𝖤𝖯𝖺𝗅}$.

Our compact data structure consists of two main components: one is for long maximal palindromes (Section 3.2), which we denote by ${𝒟}_{\mathrm{long}}$, and the other one is for short maximal palindromes (Section 3.3), which we denote by ${𝒟}_{\mathrm{short}}$. We also construct a bit vector $\mathrm{𝖫𝖲}$ of length $n$ that indicates whether the corresponding maximal palindrome is long or short, i.e., $\mathrm{𝖫𝖲}[c]=1$ iff $\mathrm{𝖬𝖤𝖯𝖺𝗅}[c]>2\tau$. Given an integer $c$ as a query input, we first check the $c$-th bit of $\mathrm{𝖫𝖲}$. If $\mathrm{𝖫𝖲}[c]=1$ then we use ${𝒟}_{\mathrm{long}}$, and otherwise we use ${𝒟}_{\mathrm{short}}$.

The idea behind the first data structure ${𝒟}_{\mathrm{long}}$ is the sparsification of array $\mathrm{𝖬𝖤𝖯𝖺𝗅}$ by using the periodicity of palindromes. Array $\mathrm{𝖬𝖤𝖯𝖺𝗅}$ is decomposed into $O(n/\tau )$ blocks of size $\tau$. Roughly speaking, long palindromes whose centers lie within the same block must be periodic, except for at most one possible exception, and can be represented in $O(\log n)$ bits using a constant number of arithmetic progressions. Then, every long maximal palindrome can be restored in constant time, from the arithmetic progressions, upon a query. Since each block has $O(\log n)$ bits of information, the total size of ${𝒟}_{\mathrm{long}}$ is $O(\frac{n}{\tau }\log n)$ bits. Later, we will choose $\tau$ so that $\tau \in \mathrm{\Theta }(\log n)$.

The second data structure ${𝒟}_{\mathrm{short}}$ is based on a lookup table. By definition, every short maximal palindrome is a factor of $w[(k-1)2\tau ..(k+1)2\tau -1]$ of length $4\tau$ for some integer $k$. We refer to such factors as $4\tau$-windows. Given a center position $c$, we detect a $4\tau$-window that contains the (short) maximal palindrome centered at $c$. We then obtain $\mathrm{𝖬𝖤𝖯𝖺𝗅}[c]$ by a single access to a precomputed lookup table $T$. Since the total number of length-$4\tau$ strings over $\mathrm{\Sigma }$ is ${\sigma }^{4\tau }$, a naïve implementation of table $T$ leads to an $\mathrm{\Omega }({\sigma }^{4\tau })$-bit data structure, which may be superlinear unless $\tau$ or $\sigma$ is sufficiently small. However, using a compact representation of $\mathrm{𝖬𝖤𝖯𝖺𝗅}$ (Lemma 3), the dependency on $\sigma$ can be eliminated. Finally, the size of table $T$ can be reduced to $O({\alpha }^{\tau }{\tau }^2)$ bits where $\alpha$ is a constant that is independent of $\sigma$ and $\tau$. Furthermore, by Lemma 3, each $4\tau$-window can be encoded using $O(\tau )$ bits. By choosing $\tau =({\log }_{\alpha }n)/2\in \mathrm{\Theta }(\log n)$, the space usage can be $O(n)$ bits in total.

We separate interval $[0..n)$ into $O(n/\tau )$ sub-intervals where each sub-interval is of length $\tau$. We refer to such a sub-interval as a block. Let us focus on $k$-th block, denoted by $B_k$. Let $L_k$ be the set of long maximal palindromes whose centers lie within the $k$-th block $B_k$. If $|L_k|\le 2$, then we simply store their lengths using $O(\log n)$ bits. Otherwise, we use periodicity of palindromes whose centers are close to each other, which is summarized as the following lemma:

The essence of this lemma is the same as that of Lemma 12 in [19], which follows from classical results shown by Apostolico, Breslauer, and Galil [2]. A concrete example of Lemma 6 is provided in Fig. 2. For completeness, we give a proof of Lemma 6 in Appendix A.

By Lemma 6, even if $L_k$ is large, it can be represented in $O(\log n)$ bits and each element of $L_k$ can be retrieved by a constant number of arithmetic operations. Finally, let us consider the construction of the data structure. Given a string $w$ of length $n$, we first compute the array ${\mathrm{𝖬𝖤𝖯𝖺𝗅}}_w$. For each block, we scan the corresponding sub-array of ${\mathrm{𝖬𝖤𝖯𝖺𝗅}}_w$ and extract the lengths of long maximal palindromes within that sub-array. By Lemma 6, they can be represented by at most three arithmetic progressions. Clearly, such arithmetic progressions can be computed in $O(\tau )$ time for each block. Thus, in total, the data structure of Lemma 7 can be constructed in $O(n)$ time.

From the above discussion, we obtain the following:

If we choose $\tau \in \mathrm{\Theta }(\log n)$ and naïvely store the length of every short maximal palindrome, which can be represented in $O(\log \tau )=O(\log \log n)$ bits, we obtain a sub-linear $O(n\log \log n/\log n)$-space representation of $\mathrm{𝖬𝖤𝖯𝖺𝗅}$:

In this subsection, we show the following lemma to reduce the size of the data structure of Corollary 8 to $O(n)$ bits.