Ural Federal University, Ekaterinburg<EMAIL_ADDRESS>Ural
Federal University, Ekaterinburg<EMAIL_ADDRESS>Mikhail Rubinchik,
Arseny M. Shur Theory of computation Design and analysis of algorithms
Mathematics of computing Combinatorial algorithms

# Palindromic k-Factorization in Pure Linear Time

Mikhail Rubinchik  Arseny M. Shur

###### Abstract

Given a string $s$ of length $n$ over a general alphabet and an integer $k$,
the problem is to decide whether $s$ is a concatenation of $k$ nonempty
palindromes. Two previously known solutions for this problem work in time
$O(kn)$ and $O(n\log n)$ respectively. Here we settle the complexity of this
problem in the word-RAM model, presenting an $O(n)$-time online deciding
algorithm. The algorithm simultaneously finds the minimum odd number of
factors and the minimum even number of factors in a factorization of a string
into nonempty palindromes. We also demonstrate how to get an explicit
factorization of $s$ into $k$ palindromes with an $O(n)$-time offline
postprocessing.

###### keywords:

stringology, palindrome, palindromic factorization, online algorithm

##  1 Introduction

Algorithmic and combinatorial problems involving palindromes attracted the
attention of researchers since the first days of stringology. Recall that a
string $s=a_{0}a_{1}\cdots a_{n-1}$ is a _palindrome_ if it is equal to its
_reversal_ $\overset{{}_{\leftarrow}}{s}=a_{n-1}\cdots a_{1}a_{0}$;
_palindromic ( $k$-)factorization_ is a representation of a string as a
concatenation of ($k$) nonempty palindromes. There is a bunch of results on
palindromic factorization. One of them is a hardness result: deciding the
existence of a factorization into distinct palindromes is NP-complete [2]; for
all other natural types of palindromic factorization, sooner or later a
linear-time algorithm in the word-RAM model was designed. In 1977, Knuth,
Morris, and Pratt [10] presented such an algorithm deciding whether a string
has a factorization into even-length palindromes. Soon, Galil and Seiferas [8]
did the same for factorization into palindromes of length ${>}1$, and also for
2-, 3-, and 4-factorization. The existence of $k$-factorization was shown to
be decidable in $O(kn)$ time [11]. Most of the recent results were related to
_palindromic length_ of a string, which is the minimum number of factors in
its palindromic factorization. There are several combinatorics papers, see
e.g. [7, 6, 14], studying the conjecture that every aperiodic infinite word
has finite factors of arbitrarily big palindromic length. On algorithmic side,
the palindromic length of a string of length $n$ was shown to be computable in
$O(n\log n)$ time [4, 9, 13]. In [3], the optimal $O(n)$ bound was reached,
using bit compression and range operations.

A linear-time algorithm for palindromic length gave a hope for better results
on palindromic $k$-factorization, because finding the latter is equivalent to
computing the minimum even and minimum odd number of factors in a palindromic
factorization. An $O(n\log n)$ algorithm for palindromic length can be easily
transformed into an $O(n\log n)$ algorithm for even/odd palindromic length
[13]. However, the properties of palindromic length used in linear-time
algorithm does not hold for even/odd palindromic length. In this paper we show
how to overcome the technical difficulties and present the following optimal
result.

######  Theorem 1.1.

There exists an online algorithm deciding, in $O(n)$ time independent of $k$,
whether a length-$n$ input string over a general alphabet admits a palindromic
$k$-factorization.

In addition, we show how to find a palindromic $k$-factorization explicitly
within the linear time (but offline).

The paper is organized as follows: after preliminaries on strings and
palindromes, we give an $O(n\log n)$-algorithm for computing the even/odd
palindromic length of a string in Section 2. The main section is Section 3
where a linear-time algorithm is described. We conclude with an algorithm
finding an explicit $k$-factorization (Section 4).

###  1.1 Preliminaries

For any $i,j$, $[i..j]$ denotes the range $\\{k\in\mathbb{Z}\colon i\leq k\leq
j\\}$; we abbreviate $[i..i]$ as $[i]$. We use ranges, in particular, to index
strings and arrays. For strings we write $s=s[0..n{-}1]$, where $n=|s|$ is the
length of $s$. The _empty string_ is denoted by $\varepsilon$. A string $u$ is
a _substring_ of $s$ if $u=s[i..j]$ for some $i$, $j$ ($j<i$ means
$u=\varepsilon$). Such pair $(i,j)$ is not necessarily unique; $i$ specifies
an _occurrence_ of $u$ at _position_ $i$. A substring $s[0..j]$ (resp.,
$s[i..n{-}1]$) is a _prefix_ (resp. _suffix_) of $s$. An integer $p\in[1..n]$
is a _period_ of $s$ if $s[0..n{-}p{-}1]=s[p..n{-}1]$. We write $s^{k}$ for
the concatenation of $k$ copies of $s$ (thus $s^{k}$ has period $|s|$). We
write $\overset{{}_{\leftarrow}}{s}$ for a string or array obtained from $s$
by reversing the order of elements (thus the equality
$s=\overset{{}_{\leftarrow}}{s}$ defines a _palindrome_). A substring (resp.
suffix, prefix) that is a palindrome is called a _subpalindrome_ (resp.
_suffix-palindrome_ , _prefix-palindrome_). If $s[i..j]$ is a subpalindrome of
$s$, the numbers $(j+i)/2$ and $\lfloor(j-i+1)/2\rfloor$ are respectively the
_center_ and the _radius_ of $s[i..j]$.

A representation $s=w_{1}\cdots w_{k}$, where $w_{1},\ldots,w_{k}$ are
palindromes, is a palindromic ($k$-)factorization of $s$. Efficient algorithms
for palindromic factorization [3, 4, 9, 11, 13] used the following (or very
similar) combinatorial properties.

######  Lemma 1.2 ([11, Lemmas 2, 3]).

For any palindrome $w$ and any $p\in[1..|w|]$, the following conditions are
equivalent: (1) $p$ is a period of $w$, (2) there are palindromes $u$, $v$
such that $|uv|=p$ and $w=(uv)^{k}u$ for some $k\geq 1$, (3) $w[p..|w|{-}1]$
($w[0..|w|{-}p{-}1]$) is a palindrome.

######  Lemma 1.3 ([11, Lemma 7]).

Suppose that $w=(uv)^{k}u$, where $k\geq 1$, $u$ and $v$ are palindromes, and
$|uv|$ is the minimal period of $w$; then, the center of any subpalindrome $x$
of $w$ such that $|x|\geq|uv|{-}1$ coincides with the center of some $u$ or
$v$ from the decomposition.

The minimum $k$ such that a palindromic $k$-factorization of a string $s$
exists is the _palindromic length_ of $s$, denoted by $\mathsf{pl}(s)$. We
define the _even palindromic length_ $\mathsf{pl}^{0}(s)$ and _odd palindromic
length_ $\mathsf{pl}^{1}(s)$ as the minimum even (resp., odd) $k$ among all
such factorizations of $s$. If no such $k$ exists, the corresponding length is
set to $\infty$. For example, $\mathsf{pl}(abcba)=\mathsf{pl}^{1}(abcba)=1$,
$\mathsf{pl}^{0}(abcba)=\infty$;
$\mathsf{pl}(acaaba)=\mathsf{pl}^{0}(acaaba)=2$, $\mathsf{pl}^{1}(acaaba)=5$.

A palindromic factorization $s=w_{1}\cdots w_{k}$ with $k\leq|s|-2$ can be
easily transformed into a palindromic $(k{+}2)$-factorization: either
$|w_{i}|\geq 3$ for some $i$, so $w_{i}=aua$ for some letter $a$ and
palindrome $u$, or $|w_{i}|=|w_{j}|=2$ for some $i,j$, so $w_{i}$ and $w_{j}$
can be replaced by four 1-letter factors. This leads to the following crucial
observation (see [13, Sect. 4.1]).

######  Lemma 1.4.

(1) A string $s$ has a palindromic $k$-factorization iff $\mathsf{pl}^{k\bmod
2}(s)\leq k$.
(2) A palindromic $k$-factorization of $s$ can be obtained in $O(n)$ time from
its palindromic $\mathsf{pl}^{k\bmod 2}(s)$-factorization.

######  Remark 1.5.

Due to Lemma 1.4, throughout the paper we study the palindromic
$k$-factorization problem for a string $s$ as the problem of finding
$\mathsf{pl}^{0}(s)$ and $\mathsf{pl}^{1}(s)$.

Recall that the method for computing $\mathsf{pl}(s)$ is dynamic programming:
we compute the array $\mathsf{pl}[0..n{-}1]$ such that
$\mathsf{pl}[i]=\mathsf{pl}(s[0..i])$ using an artificial initial value
$\mathsf{pl}[-1]=0$ and the rule $\mathsf{pl}[k]=1+\min_{i\in
S_{k}}\mathsf{pl}[i{-}1]$, where $S_{k}$ is the set of positions of all
suffix-palindromes of $s[0..k]$. This rule can be easily adapted to compute
$\mathsf{pl}^{0}(s)$ and $\mathsf{pl}^{1}(s)$: for $j\in\\{0,1\\}$ we define
the array $\mathsf{pl}^{j}[0..n{-}1]$ and employ the scheme

$\mathsf{pl}^{0}[-1]=0,\ \mathsf{pl}^{1}[-1]=\infty,\
\mathsf{pl}^{j}[k]=1+\min_{i\in S_{k}}\mathsf{pl}^{1-j}[i{-}1],\text{ where
}S_{k}=\\{i:s[i..k]=\overleftarrow{s[i..k]}\\}$ (1)

Henceforth, $s$ denotes the input string of length $n$ and
${\mathsf{PL}}[i]=(\mathsf{pl}^{0}[i],\mathsf{pl}^{1}[i])$. All considered
algorithms work in the unit-cost word-RAM model with $\Theta(\log n)$-bit
machine words and standard operations like in the C programming language. All
algorithms except Algorithm 2 are online and work in _iterations_ : $i$th
iteration begins with reading $s[i]$ and ends before reading $s[i{+}1]$.

##  2 An $O(n\log n)$ Algorithm

###  2.1 Palindromic Iterator

We process the input string using a data structure called (palindromic)
_iterator_ [11], which stores a string $s$ and answers the following queries
in $O(1)$ time:
\- $\mathsf{rad}(x)$ / $\mathsf{len}(x)$ returns the radius / length of the
longest palindrome in $s$ with the center $x$;
\- $\mathsf{maxPal}$ returns the center of the longest suffix-palindrome of
$s$;
\- $\mathsf{nextPal}(x)$ returns the center of the longest proper suffix-
palindrome of the suffix-palindrome of $s$ with the center $x$.
The iterator stores an array of radii for all possible centers of palindromes
and a list of centers of suffix-palindromes in increasing order. The update
query $\mathsf{add}(a)$ appends letter $a$ to $s$. Performing this query, the
iterator emulates an iteration of Manacher’s algorithm [12] and updates the
list of suffix-palindromes, all within
$O(1+\mathsf{maxPal}_{new}-\mathsf{maxPal}_{old})$ time, which is $O(n)$ for
$n$ updates to the originally empty structure. Below we assume that
$\mathsf{add}(a)$ returns the list of deleted centers in the form
${\mathsf{dead}}(x)=(x,\text{answers to all queries about }x)$.

With the iterator, dynamic program (1) can be implemented to work in time
proportional to the number of subpalindromes in $s$ ($\Omega(n^{2})$ in the
worst case); one iteration is as follows:

1:$\mathsf{add}(s[n]);\;\mathsf{pl}^{0}[n],pl^{1}[n]\leftarrow+\infty$

2:for ($x\leftarrow\mathsf{maxPal};\;x\neq
n+\frac{1}{2};\;x\leftarrow\mathsf{nextPal}(x)$) do

3: for ($j\in\\{0,1\\}$) do
$\mathsf{pl}^{j}[n]\leftarrow\min\\{\mathsf{pl}^{j}[n],1+\mathsf{pl}^{1-j}[n-\mathsf{len}(x)]\\}$

###  2.2 Series of Palindromes

Let $u_{1},\ldots,u_{k}$ be all non-empty suffix-palindromes of a string $s$
in the order of decreasing length. For any $i<j$, since $u_{j}$ is a suffix of
$u_{i}$, any period of $u_{i}$ is a period of $u_{j}$. Hence the sequence of
minimal periods of $u_{1},\ldots,u_{k}$ is non-increasing. The groups of
suffix-palindromes with the same minimal period are _series of palindromes_
(of $s$):

$\underbrace{u_{1},\ldots,u_{i_{1}}}_{p_{1}},\underbrace{u_{i_{1}+1},\ldots,u_{i_{2}}}_{p_{2}},\ldots,\underbrace{u_{i_{t-1}+1},\ldots,u_{k}}_{p_{t}}.$

We refer to the longest and the shortest palindrome in a series as its _head_
and _tail_ respectively (they coincide in the case of a 1-element series); we
enumerate the elements of a series from the head to the tail. Given an integer
$p$, the _$p$ -series_ is the series with period $p$.

######  Lemma 2.1 ([4, 9, 11]).

For any string $s[0..n]$, if $r$ is the length of a tail of a series, then the
head of the next series has length less than $2r/3$. In particular, If
$p_{1},\ldots,p_{t}$ are periods of all series of $s[0..n]$, then $t=O(\log
n)$ and $p_{1}+\cdots+p_{t}=O(n)$.

Note that strings with $\Omega(\log n)$ series for $\Omega(n)$ prefixes do
exist [4].

Below we present an $O(n\log n)$ algorithm finding even and odd palindromic
lengths of a string. Due to symmetry, we always write $\mathsf{pl}^{j}$
assuming $j\in\\{0,1\\}$. The algorithm, which is a straightforward adaptation
of the algorithm of [3] for palindromic length, serves as a base for the
linear-time solution, so we provide necessary details. We rewrite rule (1) as

$\mathsf{pl}^{j}[n]=1+\min_{U}\min_{u\in U}\mathsf{pl}^{1-j}[n{-}|u|],\text{
where }U\text{ runs through the series of }s,$ (2)

and compute the internal minimum in $O(1)$ time using precalculations based on
the structure of series, described in the following lemma.

######  Lemma 2.2 ([3]).

For a string $s$ and $p\geq 1$, let $U$ be a $p$-series of palindromes,
$k=\\#U$. Then there exist unique palindromes $u,v$ with $|uv|=p$,
$v\neq\varepsilon$ such that one of three conditions hold:
1) $U=\\{(uv)^{k+1}u,(uv)^{k}u,\ldots,(uv)^{2}u\\}$ and the next series begins
with $uvu$,
2) $U=\\{(uv)^{k}u,(uv)^{k-1}u,\ldots,uvu\\}$ and the next series begins with
$u$,
3) $U=\\{v^{k},v^{k-1},\ldots,v\\}$, $p=1$, $|v|=1$, $u=\varepsilon$, and $U$
is the last series for $s$.

######  Proof 2.3.

The lemma appeared in [3] without a proof, so we provide it here. If $p=1$, 3)
trivially holds, so let $p>1$. By Lemma 1.2, the head $w$ of $U$ has the form
$(uv)^{q}u$ for some $q\geq 1$ and some palindromes $u$ and $v$ such that
$|uv|=p$ and the longest proper suffix-palindrome of $w$ is $(uv)^{q-1}u$.
Applying Lemma 1.2 iteratively, we finally get
$U=\\{(uv)^{q}u,\ldots,(uv)^{q-k+1}u\\}$. Note that the only suffix-palindrome
of $(uv)^{2}u$ with length ${\geq}|uv|$ is $uvu$ by Lemma 1.3. Hence by Lemma
1.2 the minimal period of $(uv)^{2}u$ equals $p$. So either $(uv)^{2}u\in U$
and thus $U$ satisfies 1) or 2), or $U=\\{uvu\\}$, also satisfying 2).

Our algorithm maintains an array $\mathsf{left}[1..n]$: for $p\in[1..n]$, if
there is a $p$-series, then $\mathsf{left}[p]$ is such that
$s[\mathsf{left}[p]{+}1..n]$ is the longest suffix (which is not necessarily a
palindrome) of $s[0..n]$ with period $p$; otherwise, $\mathsf{left}[p]$ is
undefined. For example, if $s[0..n]=\cdots aaabaaba$ and $p=3$, then the
mentioned suffix is $s[n{-}6..n]=aabaaba$ and $\mathsf{left}[3]=n-7$. If we
extend $s$ by $b$, this will break period 3 and make $\mathsf{left}[3]$
undefined. If we then append $ba$, the resulting string $s\cdot bba=\cdots
aaabaab\boldsymbol{abba}$ will have a suffix-palindrome of period 3 again, and
$\mathsf{left}[3]$ will get a new value $n-2$.

######  Remark 2.4.

We do _not_ explicitly make $\mathsf{left}[p]$ undefined if it was defined
earlier. We compute it at the iterations where a $p$-series is present. If the
new value differs from the old one, we conclude that since we saw the previous
$p$-series, period $p$ broke.

######  Lemma 2.5.

Given a number $p$ and the length of the head of the $p$-series of $s$,
$\mathsf{left}[p]$ can be computed in $O(1)$ time.

######  Proof 2.6.

Let $w=(uv)^{k}u$ be the head of the $p$-series (see Lemma 2.2), $x$ be the
center of $w$, and $z(uv)^{k}u$ be the longest suffix of $s[0..n]$ with period
$p$ (for $s$ in the above example, $u=\varepsilon$, $v=aba$, $x=n-5/2$,
$z=a$). Then $z$ is a proper suffix of $uv$. Hence the center $x_{1}$ of the
prefix-palindrome $u$ of $w$ satisfies $\mathsf{len}(x_{1})=2|z|+|u|$ (in the
example, $x_{1}=n-11/2$, $\mathsf{len}(x_{1})=|aa|$). Note that
$|u|=\mathsf{len}(x)\bmod p$ and $x_{1}=2x-\mathsf{cntr}(|u|)$, where
$\mathsf{cntr}(d)=n-(d-1)/2$ is the center of the length $d$ suffix-palindrome
of $s[0..n]$. Thus, $|z|$ and $\mathsf{left}[p]=n{-}\mathsf{len}(x){-}|z|$ are
computed in $O(1)$ time.

Computations of internal minima in (2) are based on the following idea. Let
$U$ be a $p$-series for $s[0..n]$ with $k>1$ palindromes (w.l.o.g.,
$U=\\{(uv)^{k}u,\ldots,uvu\\}$). Updating $\mathsf{pl}^{j}[n]$ using $U$, we
compute
$m=\min\\{\mathsf{pl}^{1-j}[n{-}kp{-}|u|],\ldots,\mathsf{pl}^{1-j}[n{-}p{-}|u|]\\}$.
Now note that $s[0..n]$ ends with $(uv)^{k}u$ but not with $(uv)^{k+1}u$:
otherwise, the latter string would belong to $U$. Then $s[0..n{-}p]$ ends with
$(uv)^{k-1}u$ but not with $(uv)^{k}u$ and thus has the $p$-series
$U^{\prime}=\\{(uv)^{k-1}u,\ldots,uvu\\}$. Thus, at that iteration we computed
$m^{\prime}=\min\\{\mathsf{pl}^{1-j}[n{-}kp{-}|u|],\ldots,\mathsf{pl}^{1-j}[n{-}2p{-}|u|]\\}$
for updating $\mathsf{pl}^{j}[n{-}p]$. If we saved $m^{\prime}$ into an
auxiliary array, then $m=\min\\{m^{\prime},\mathsf{pl}^{1-j}[n-p-|u|]\\}$ is
computed in constant time, as required. We store all precomputed minima in two
arrays ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{j}[1..n]$,
where $j\in\\{0,1\\}$ and each ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}^{j}[p]$ is, in turn, an array ${\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{j}[p][0..p{-}1]$ such
that

${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}^{j}[p][i]=\min\\{\mathsf{pl}^{j}[t]\colon t\geq\mathsf{left}[p]\text{ and
}(t-\mathsf{left}[p])\bmod p=i\\\ \text{ and }s[t{+}1..n]\text{ has a prefix-
palindrome of minimal period }p\\}$ (3)

(see Fig. 1). We also denote ${\mathsf{PRE}}[p][i]=({\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{0}[p][i],{\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{1}[p][i])$. If the
minimum in (3) is taken over the empty set (i.e., the related prefix of $s$
has no $p$-series), then ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}^{j}[p][i]$ is undefined. If
$\\{u_{1},\ldots,u_{k}\\}$ is a $p$-series for $s[0..n]$, then (3) implies
${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}^{j}[p][n{-}|u_{1}|{-}\mathsf{left}[p]]=\min\\{\mathsf{pl}^{j}[n{-}|u_{i}|]\colon
i\in[1..k]\\}$, which is exactly the value $m$ mentioned above.

Figure 1: Precomputed values. Palindromes with minimal period $p=4$ are shown.
By (3), ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}^{j}[p][0..2]=\big{[}\mathsf{pl}^{j}[n{-}10];\min\\{\mathsf{pl}^{j}[n{-}9],\mathsf{pl}^{j}[n{-}5]\\};\mathsf{pl}^{j}[n{-}8]\big{]};{\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{j}[p][3]$ is undefined.

Overall, given a new letter $s[n]$, we compute ${\mathsf{PL}}[n]$ as follows:

Algorithm 1 : $O(n\log n)$ algorithm, $n$th iteration

1:$\mathsf{add}(s[n]);\;{\mathsf{PL}}[n]\leftarrow(+\infty,+\infty);$

2:for ($x\leftarrow\mathsf{maxPal};\;x\neq
n+\frac{1}{2};\;x\leftarrow\mathsf{nextPal}(\mathsf{cntr}(d))$) do
$\triangleright$ goes to next head each time

3:
$p\leftarrow\mathsf{len}(x)-\mathsf{len}(\mathsf{nextPal}(x));$$\triangleright$
min. period of the head centered at $x$

4: $d\leftarrow p+(\mathsf{len}(x)\bmod p);$$\triangleright$ length of
candidate tail in $p$-series

5: if
$\mathsf{len}(\mathsf{cntr}(d))-\mathsf{len}(\mathsf{nextPal}(\mathsf{cntr}(d)))\neq
p$ then $d\leftarrow d+p;$$\triangleright$ corrected length of tail

6: $y\leftarrow\mathsf{left}[p]$; compute $\mathsf{left}[p]$; $i\leftarrow
n{-}\mathsf{len}(x){-}\mathsf{left}[p]$;$\triangleright$ $O(1)$ time by Lemma
2.5

7: if $\mathsf{left}[p]>y$ then clear ${\mathsf{PRE}}[p]$;$\triangleright$
delete obsolete values

8: if $\mathsf{len}(x)=d$ then
${\mathsf{PRE}}[p][i]\leftarrow{\mathsf{PL}}[n{-}d];$

9: ${\mathsf{PRE}}[p][i]\leftarrow(\min\\{{\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}^{0}[p][i],\mathsf{pl}^{0}[n{-}d]\\},\min\\{{\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}^{1}[p][i],\mathsf{pl}^{1}[n{-}d]\\})$;

10: ${\mathsf{PL}}[n]\leftarrow(\min\\{\mathsf{pl}^{0}[n],1+{\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}^{1}[p][i]\\},\min\\{\mathsf{pl}^{1}[n],1+{\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}^{0}[p][i]\\});$

######  Proposition 2.7.

Algorithm 1 correctly computes ${\mathsf{PL}}[0..n]$ in $O(n\log n)$ time.

######  Proof 2.8.

All queries $\mathsf{add}$ require $O(n)$ time in total, so we ignore them.
Let $x$ be the center of a processed suffix-palindrome $w=(uv)^{k}u$ with
period $p$. By Lemma 1.2,
$p=|uv|=\mathsf{len}(x)-\mathsf{len}(\mathsf{nextPal}(x))$. Let
$x^{\prime}=\mathsf{cntr}(p+(\mathsf{len}(x)\bmod p))$, so that $x^{\prime}$
is the center of the suffix-palindrome $uvu$. By Lemma 2.2, $uvu$ is,
depending on its period
$\mathsf{len}(x^{\prime})-\mathsf{len}(\mathsf{nextPal}(x^{\prime}))$, either
the tail of the $p$-series or the head of the next series. Thus in lines 3–5
Algorithm 1 computes, using $O(1)$ queries to the iterator, the period and the
length of the tail of the series containing $w$. This means, in particular,
that the for loop iterates over all heads of series in $s$, for the total of
$O(\log n)$ runs.

Next note that when a symbol added to $s$ breaks period $p$, all values in
${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{j}[p]$ become
obsolete and should be deleted. Algorithm 1 does this in lines 6–7: if the
“new” and “old” values of $\mathsf{left}[p]$ differ, then period $p$ broke
since the last update of ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}^{j}[p]$.

Let $\\{u_{1},\ldots,u_{k}\\}$ be a $p$-series,
$i=n{-}|u_{1}|{-}\mathsf{left}[p]$. If $k=1$, there was no $p$-series $p$
iterations ago, so the undefined value ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}^{j}[p][i]$ is set to
$\mathsf{pl}^{j}[n{-}|u_{k}|]$ in line 8. Otherwise one has ${\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}^{j}[p][i]=\min\\{\mathsf{pl}^{j}[n{-}|u_{1}|],\ldots,\mathsf{pl}^{j}[n{-}|u_{k-1}|]\\}$
by (3), and this value is updated using $\mathsf{pl}^{j}[n{-}|u_{k}|]$ in line
9; so ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}^{j}$ is
correctly maintained. Finally, in line 10 the rule (2) is implemented. So the
algorithm is correct and each run of the for loop takes $O(1)$ time. The
result now follows.

If $s[0..n]$ has a suffix-palindrome $w$ centered at $x$, we say that $w$
_survives_ the next iteration if $x$ is the center of a suffix-palindrome of
$s[0..n{+}1]$. Otherwise, $w$ (or $x$) _dies_ at that iteration. We refer to
the number of iterations $x$ survives as its _time-to-live_ , denoted by
$\mathsf{pttl}_{n}(x)$. The same notions apply to any $p$-series of $s[0..n]$
and to its period $p$; we write $\mathsf{ttl}_{n}(p)$ for the time-to-live of
$p$. If $p$ dies, then $p$-series also dies, but not vice versa. More
precisely, while $p$ is live, $p$-series evolves as follows (cf. Fig. 1).

A $p$-series appears at $n$th iteration as a single palindrome
$\mathsf{head}(p)=\mathsf{tail}(p)=uvu$ centered at $x$. Then at some
iteration $n{+}i$, $0<i<p$, $x$ reaches $\mathsf{left}[p]$ on the left and
dies together with the series. At some iteration $n{+}i{+}j$, $0\leq j,p{-}i$,
a palindrome centered at $x+\frac{p}{2}$ “resurrects” the series (if $j=0$, we
can say that the series has not died). Finally, at the $(n{+}p)$th iteration a
palindrome centered at $x{+}p$ joins the series; every subsequent $p$
iterations follow the same pattern (but the death of the head no longer means
the death of the series). In Fig. 1, $p=4,i=2,j=1$.

######  Lemma 2.9.

Suppose that $s[0..n]$ has $p$-series and $q$-series such that $p>q$ and
$\mathsf{ttl}_{n}(p)\geq p$. Then $\mathsf{ttl}_{n}(q)<p$.

######  Proof 2.10.

Let $\mathsf{head}(p)=(uv)^{r}u$. If $\mathsf{ttl}(q)\geq p$, the string
$s[n-q+1..n+p]$ of length $p+q$ has periods $p$ and $q$. Hence it has period
$d=\gcd(p,q)$ by the Fine-Wilf theorem [5]. Thus $vu$ is a $(p/d)$-power of a
shorter word; so $(uv)^{r}u$ has period $d<p$, contradicting the definition of
$p$-series.

######  Lemma 2.11.

Let a string $s[0..n]$ have series with periods $P=p_{1}>p_{2}>\cdots>p_{l}$
and let $t>0$. Then
$\sum_{i=1}^{l}\min\\{\mathsf{ttl}_{n}(p_{i}),t\\}=O(P+t)$.

######  Proof 2.12.

Divide the periods in two groups: those with $\mathsf{ttl}_{n}(p)<p$ and the
rest. In the first group, the sum of $\mathsf{ttl}$’s is majorized by
$\sum_{i=1}^{l}p_{i}$, which is $O(P)$ by Lemma 2.1. For the second group,
$\mathsf{ttl}_{n}(p_{i})$ is smaller than the previous period from this group
by Lemma 2.9. So we can take $t+\sum_{i=1}^{l}p_{i}=O(P+t)$ as the upper
bound. The result now follows.

Lemma 2.11 has an immediate corollary used in the linear algorithm.

######  Corollary 2.13.

Suppose that Algorithm 1 processed $s[0..n]$ and $p<n$. During the next $t$
iterations, the number of times the for loop of Algorithm 1 processes series
which survived since $s[0..n]$ and have periods $\leq p$ is $O(p+t)$.

##  3 Linear Algorithm

###  3.1 Resources for Speed-Up

In some cases, dynamic programming over arrays can be sped up by a $\log n$
factor by a technique called _four Russians’ trick_ [1]. The idea is to store
the DP array(s) in a compressed form requiring $O(1)$ bits per element and
update $(\log n)$-size chunks of the compressed array using $O(1)$ operations
on machine words. The key operations used are _table operations_ : the total
number of valid inputs for such an operation is $o(n)$ and the results for all
valid inputs can be computed in advance in $o(n)$ time and stored in an
auxiliary table; the typical time/space restriction is $O^{*}(n^{\alpha})$,
where $\alpha<1$ and $O^{*}$ suppresses polylog factors. To apply this
technique to Algorithm 1, we should met several necessary conditions:
1) the array ${\mathsf{PL}}$ can be compressed to $O(1)$ bits per element;
2) each array ${\mathsf{PRE}}[p]$ can be compressed to $O(p+\log n)$ bits;
3) each update of arrays ${\mathsf{PL}},{\mathsf{PRE}}[p]$ (lines 8–10
operations of Algorithm 1) can be performed without decompression,
simultaneously for $\Omega(\log n)$ successive iterations with a constant
number of operations over machine words, including table operations;
4) all intermediate states of arrays ${\mathsf{PL}}$ and ${\mathsf{PRE}}[p]$
during the course of the algorithm are valid inputs for the compression
scheme.

Let us recall how it works for palindromic length (see [3]). Condition 1 is
provided by

######  Lemma 3.1 ([13, Lemma 4.11]).

If $w$ is a string and $a$ is a letter, then
$|\mathsf{pl}(wa)-\mathsf{pl}(w)|\leq 1$.

Due to Lemma 3.1, it is possible to store any subarray $\mathsf{pl}[i..j]$ as
one number $\mathsf{pl}[i]$ followed by $(j-i)$ 2-bit codes for the
differences $\mathsf{pl}[k]-\mathsf{pl}[k{-}1]$. The situation is more subtle
with the arrays ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}[p]$, but it was proved in [3] that each of these arrays can be efficiently
split into a constant number of chunks, where successive elements of the same
chunk differ by at most one. For each chunk, the same encoding as for
$\mathsf{pl}$ works; so condition 2 is also met.

The following observation shows the resource for range updates (condition 3).
Let $s=\cdots a(uv)^{k}u$ have $p$-series $U$ with the head $(uv)^{k}u$ (cf.
Lemma 2.2), where $|uv|=p$, $a$ is the last letter of $v$, and an element
${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}[p][i]$, for some
$i$, was updated at the current iteration. Thus $\mathsf{pl}[n]$ was just
updated using ${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\
E}[p][i]$. Now if the next letter is $a$, the string $s^{\prime}=sa$ retains
the $p$-series, and each palindrome in it extends one letter left and right,
retaining the same center as its counterpart in $s$. This means that during
this iteration we update ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}[p][i{-}1]$, and then $\mathsf{pl}[n{+}1]$ using
${\rm Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}[p][i{-}1]$. If
this situation repeats, say, $t$ times, one can assign
$\mathsf{pl}[n..n{+}t]\leftarrow\min\\{\mathsf{pl}[n..n{+}t],1+\overleftarrow{{\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}[p][i{-}t..i]}\\}$ in
line 10 of Algorithm 1.

Let $t=\lfloor\frac{\log n}{8}\rfloor$. Formally, a _chunk_ is an array
$A=A[0..i]$, where $i<t$, of $(\log n)$-bit numbers, in which any two
consecutive numbers differ by at most one; it is stored as a $(\log n)$-bit
number followed by $i$ $2$-bit codes encoding the differences between
consecutive values. If the length of a chunk is less than $t$, then the unused
2-bit code is added to the end.

Note that in both $\overset{{}_{\leftarrow}}{A}$ and $\min\\{A,B\\}$
consecutive elements differ by at most 1, so these chunks can be compressed.
Therefore, condition 4 is also met in view of the following lemma.

######  Lemma 3.2.

The following operations can be performed in $O(1)$ time using table
operations:
1) increment chunk $A$;
2) extract an element: given chunk $A$ and number $l<|A|$, return the number
$A[l]$;
3) extract a chunk: given chunks $A,B$ with $|B[0]-A[|A|{-}1]|\leq 1$ and
numbers $l,d$, return chunk $AB[l..r]$, where $r=\min\\{l{+}d{-}1,|AB|{-}1\\}$
and $AB$ is the concatenation of $A$ and $B$;
4) reverse a chunk: given chunk $A$, return $\overset{{}_{\leftarrow}}{A}$;
5) concatenate two chunks: given chunks $A$ and $B$, return a chunk $C=AB$ or,
if $|AB|>t$, two chunks $C,D$ such that $CD=AB$ and $|C|=t$;
6) extend a chunk: given a chunk $A$ and numbers $l,r$ such that $|A|+l+r\leq
t$, return a chunk $C$ of length $|A|{+}l{+}r$ such that
$C[l..l{+}|A|{-}1]=A$, $C[i{+}1]=C[i]-1$ for each $i<l$, and $C[i{+}1]=C[i]+1$
for each $i\geq l+|A|$.
7) take minimum of two chunks: given chunks $A,B$, $|A|=|B|$, return the chunk
$C$ of length $|A|$ such that $C[i]=\min\\{A[i],B[i]\\}$ for each $i$.

######  Proof 3.3.

1) It suffices to increment $A[0]$.
2) Create a table containing, for any $k<t$, the sum of values encoded by
every $k$ 2-bit codes. The table has less than $2^{2t}$ entries, each of them
is an $O(\log\log n)$-bit number, for a total size of $O^{*}(n^{1/4})$. Thus,
such a sum is a table operation; we add its result to $A[0]$ to get $A[i]$.
3) Using the previous operation, extract $A[l]$ and $A[|A|{-}1]$; $C$ is
encoded by $A[l]$ followed some final codes from $A$, the code of
$B[0]-A[|A|{-}1]$, and some initial codes of $B$. (Or $l{+}d\leq|A|$ and $B$
is not involved at all.)
4) Extract $A[|A|{-}1]$ and use a table to “invert” a sequence of 2-bit codes;
the table contains $O(2^{2t})$ entries of size $O(2^{2t})$ each, for
$O^{*}(n^{1/4})$ total size.
5) Extract $A[|A|{-}1]$, getting $C$ as $A[0]$ plus codes from $A$, plus the
code of $B[0]-A[|A|{-}1]$ and some initial codes from $B$. To get $D$ (if
exists), extract the corresponding symbol of $B$ and append the rest of codes
from $B$ to it.
6) Add $l$ to $A[0]$, append $l$ codes of -1 from the left and $r$ codes of 1
from the right to the codes in $A$.
7) If $|A[0]-B^{\prime}[0]|\geq 2t$, then the answer is the chunk with the
smaller number. Otherwise, the difference is a $\lceil 1+\log t\rceil$-bit
number. One has $C[0]=\min\\{A[0],B[0]\\}$. Further, construct a table with
$O^{*}(n^{1/2})$ entries which contains, for the given difference and two
sequences of 2-bit codes, the sequence of 2-bit codes for $C$. Since the size
of $C$ is $O^{*}(n^{3/4})$ bits, this is a table operation.

##### Overview of linear-time algorithm for palindromic length.

The algorithm [3] is based on grouping consecutive iterations into _phases_.
Each phase begins immediately after the end of the previous phase and
continues until one of three conditions is fulfilled: $t=\lfloor\frac{\log
t}{8}\rfloor$ iterations passes, the input string ends, or the next iteration
will break the longest suffix-palindrome. In the beginning of a phase, an
assumption is made that the next $t$ iterations will not change
$\mathsf{maxPal}$. Under this assumption, $O(1)$ queries to the iterator is
sufficient to compute the number $t_{p}=\min\\{t,\mathsf{ttl}(p)\\}$. Then the
corresponding updates to ${\rm Phys.\leavevmode\nobreak\
Rev.\leavevmode\nobreak\ E}[p]$ and $\mathsf{pl}$ are applied simultaneously
for the next $t_{p}$ iterations, using $O(1)$ operations described in Lemma
3.2. After processing all series, actual $t$ letters are added one by one;
each time the iterator is updated, constant number of new series (with freshly
appeared centers) are added, and the arrays $\mathsf{pl}$ and ${\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ E}[p]$ are updated using
these new series. When the processing of the letter $s[i]$ is finished,
$\mathsf{pl}[i]$ gets its true value. If an input symbol violates the
assumption (i.e., it changes $\mathsf{maxPal}$), the phase is aborted,
unfinished updates are deleted, and a new phase is started from the current
symbol. The of operations performed is $O(t)$ for a phase of $t$ iterations
and $O(P+i)$ for a phase of $i<t$ iterations, where $P$ is the period of the
longest suffix-palindrome at the beginning of the phase. Since $P\leq
2\cdot(\mathsf{maxPal}_{new}-\mathsf{maxPal}_{old})$, and $\mathsf{maxPal}$
monotonely increases from $0$ to at most $n$ during the course of the
algorithm, all phases take $O(n)$ time in total.

###  3.2 Even/Odd Palindromic Length

The following analog of Lemma 3.1 allows one to store the array
${\mathsf{PL}}$ in compressed form.

######  Lemma 3.4.

If $w$ is a string, $a,b$ are letters, $j\in\\{0,1\\}$, then
$\mathsf{pl}^{j}(wab)\in\\{\mathsf{pl}^{1-j}(wa)+1$,
$\mathsf{pl}^{1-j}(wa)-1,\mathsf{pl}^{1-j}(w)+1\\}$.

######  Proof 3.5.

Let $k=\mathsf{pl}^{j}(wab)$. Consider all palindromic factorizations of the
form $wab=w_{1}\cdots w_{k}$. Three cases are possible.
1\. There is a factorization with $w_{k}=b$. Then $k=\mathsf{pl}^{1-j}(wa)+1$.
2\. There is a factorization with $w_{k}=bub$, $u\neq\varepsilon$, and no
factorization with $w_{k}=b$. Then $wa$ has no $(k{-}1)$-factorization, but
has a $(k{+}1)$-factorization $w_{1}\cdots w_{k-1}bu$; so
$k=\mathsf{pl}^{1-j}(wa)-1$.
3\. $w_{k}=ab$ in each factorization (so $a=b$). Then
$k=\mathsf{pl}^{1-j}(w)+1$.

As above, we set $t=\lfloor\frac{\log n}{8}\rfloor$. The chunks are segments
$A=A[0..i]=(A^{0}[0..i],A^{1}[0..i])$ of ${\mathsf{PL}}$ or
${\mathsf{PRE}}[p]$. We encode them using $O(t)=O(\log n)$ bits. The
difference with the case of palindromic length is that we store four explicit
values: $A^{0}[0],A^{1}[0],A^{0}[1],A^{1}[1]$. Subsequent elements are encoded
by 2-bit codes associated with the cases of Lemma 3.4, the unused 2-bit code
indicates the end of a shorter chunk. Below we demonstrate a problem with this
encoding and show the solution.

Let us consider the graphs of two functions $f_{1}(i)=\mathsf{pl}^{(i-1)\bmod
2}[i]$ and $f_{2}(i)=\mathsf{pl}^{i\bmod 2}[i]$ ($f_{2}$ is undefined for
small values of $i$ until two consecutive equal letters occur in $s$). At most
points, $f_{1}$ and $f_{2}$ have the first difference $\pm 1$, but in some
points, corresponding to case 3 from Lemma 3.4, the upper graph drops down to
the lower one; see Fig. 2.

Figure 2: even/odd palindromic length visualized by
$f_{1}(i)=\mathsf{pl}^{(i-1)\bmod 2}[i]$ and $f_{2}(i)=\mathsf{pl}^{i\bmod
2}[i]$.

The drops cause the following problem: taking minimum of two chunks can result
in a chunk having no valid encoding (condition 4 is violated). For example,
taking the minimum of two valid chunks
$\small\begin{array}[]{|c|c|c|c|}\hline\cr\cdots&3&7&3\\\
\hline\cr\cdots&6&4&4\\\ \hline\cr\end{array}$ and
$\small\begin{array}[]{|c|c|c|c|}\hline\cr\cdots&1&7&3\\\
\hline\cr\cdots&6&2&6\\\ \hline\cr\end{array}$ , we get the chunk
$\small\begin{array}[]{|c|c|c|c|}\hline\cr\cdots&1&7&3\\\
\hline\cr\cdots&6&2&\boldsymbol{4}\\\ \hline\cr\end{array}$ . The marked
element does not satisfy any alternative from Lemma 3.4. To remedy this, we
consider the following _smoothing_ operation on the computed array
${\mathsf{PL}}[0..n{-}1]$: for each $i\in[0..n{-}2]$, $j\in\\{0,1\\}$ replace
$\mathsf{pl}^{j}[i]$ by $\min\\{\mathsf{pl}^{j}[i],\mathsf{pl}^{(j+1)\bmod
2}[i{+}1]+1,\ldots,\mathsf{pl}^{(j+n-1-i)\bmod 2}[n{-}1]+n-1-i\\}$. For
example, the graphs of $f_{1}$ and $f_{2}$ from Fig. 2 after smoothing will
look as follows (empty circles represent redefined values):

The idea of smoothing is clarified by the following lemma.

######  Lemma 3.6.

Smoothing of the array ${\mathsf{PL}}[0..n{-}1]$ does not affect the value
${\mathsf{PL}}[n]$ computed by rule (1).

######  Proof 3.7.

Assume that we applied smoothing and then computed $k=\mathsf{pl}^{k\bmod
2}[n]$ by rule (1) getting the minimum $k{-}1$ as the element
$\mathsf{pl}^{(k-1)\bmod 2}[r]$. Since the minimum cannot increase after
smoothing, we just need to check that $s[0..n]$ indeed has a palindromic
$k$-factorization. This is obvious if $\mathsf{pl}^{(k-1)\bmod 2}[r]$ was not
changed by smoothing. Otherwise, $k{-}1=\mathsf{pl}^{(k-1+i-r)\bmod 2}[i]+i-r$
for some $i>r$. Since $s[r{+}1..n]$ is a palindrome (see (1)), we factor it as
$uv\overset{{}_{\leftarrow}}{u}$, where $u=s[r{+}1..i]$. So,
$s[0..n]=s[0..i]v\overset{{}_{\leftarrow}}{u}$ indeed has a $k$-factorization:
$s[0..i]$ can be factored into $k{-}1{-}i{+}r$ palindromes and
$\overset{{}_{\leftarrow}}{u}$ into $i{-}r$ palindromes.

We extend smoothing to subarrays of the form ${\mathsf{PL}}[l..r]$: for each
$i\in[l..r{-}1]$, $j\in\\{0,1\\}$ replace $\mathsf{pl}^{j}[i]$ by
$\min\\{\mathsf{pl}^{j}[i],\mathsf{pl}^{(j+1)\bmod
2}[i{+}1]+1,\ldots,\mathsf{pl}^{(j+r-i)\bmod 2}[r]+r-i\\}$. The resulting
values are always between the values from the original ${\mathsf{PL}}$ and
those from smoothed ${\mathsf{PL}}$, so Lemma 3.6 stays true for this sort of
operations. The following lemma is crucial.

######  Lemma 3.8.

Smoothing a chunk can be done in $O(1)$ time.

######  Remark 3.9.

Let $\\{j,l\\}=\\{1,2\\}$ and let $f_{j}$ have a drop at position $i$ (i.e.,
$f_{j}(i)=f_{l}(i{-}2)+1\leq f_{j}(i{-}1)-3$). Then neither $f_{j}$ nor
$f_{l}$ has a drop at position $i{+}1$. Indeed, $f_{l}(i{+}1)\leq
f_{l}(i{-}2)+3<f_{j}(i{-}1)$ and $f_{l}(i{-}1)\geq f_{l}(i{-}2)-2=f_{j}(i)+3$
(so either $f_{l}(i{-}1)\geq f_{j}(i{+}1)$ or $f_{j}(i{+}1)>f_{j}(i)+3$).

######  Proof 3.10 (Proof of Lemma 3.8).

Assume that a chunk $A$ is given. We enumerate its positions from 1 to $t$ and
write $\tilde{A}$ for the result of its smoothing. The functions $f_{1},f_{2}$
are defined as above; let $\tilde{f}_{1},\tilde{f}_{2}$ be their counterparts
after smoothing. If we know $f_{j}$ up to an additive constant (i.e., know
some function $f_{j}+c$), then it is easy to obtain $\tilde{f}_{j}+c$. Hence
if we know both $f_{1}+c$ and $f_{2}+c$, we can reconstruct $\tilde{A}$ up to
the same additive constant $c$. Note that if $f_{j}$ has a drop at position 2,
then $f_{j}(1)$ can be replaced by $f_{j}(2)+1$ without affecting
$\tilde{f}_{j}$. So if we know the difference $\delta=f_{1}(2)-f_{2}(2)$ and
2-bit codes for the second and all subsequent elements of the chunk, we can
compute $\tilde{f}_{1}$ and $\tilde{f}_{2}$ up to the constant $c=-f_{2}(2)$.
Indeed, if $f_{j}$ has no drop at position 3, then we compute $f_{j}(3)+c$
from $\delta$ and the corresponding 2-bit code; if $f_{j}$ has a drop at 3,
i.e., $f_{j}(3)=f_{3-j}(1)$, then by Remark 3.9 there is no drop at 2, so we
compute $f_{3-j}(1)+c$ and increment it to get $f_{j}(3)+c$. After computing
$f_{1}(3),f_{2}(3)$, the rest is easily reconstructed from 2-bit codes.

Now we observe that if $|\delta|>2t$, only two cases are possible, and they
can be easily distinguished: either there are no drops, so
$\tilde{f}_{j}=f_{j}$ for $j=1,2$, or the leftmost drop is in $f_{j}$ at
position $i$, and then $\tilde{f}_{j}(i-r)=f_{j}(i)+r$ for all $r<i$. So in
this case only the sign of $\delta$ matters, and we assign $\delta=\pm\infty$.
Thus we obtained a table operation which, given $(2t-2)$ 2-bit codes and a
number $\delta$ with $O(t)$ distinct values, returns a compressed chunk;
adding $f_{2}(2)$ to the explicit values in this chunk, one gets $\tilde{A}$.

###  3.3 Linear-Time Algorithm: An Overview

Below we describe one phase of Algorithm EOPL computing even and odd
palindromic lengths of the input string. We avoid pseudocode since it is too
long.

##### Prerequisites.

P1. Arrays ${\mathsf{PL}}$ and ${\mathsf{PRE}}[p]$ are stored in compressed
form as sequences of length-$t$ chunks (the last chunk in a sequence can be
short). We maintain a _work chunk_ $W$ to compute the reversal of a new chunk
of ${\mathsf{PL}}$ during the current phase; we move symbols from $W$ to
${\mathsf{PL}}$ one by one and thus avoid the reversal operation. List
${\mathsf{wait}}$ stores new palindromes and palindromes that changed periods,
to perform ${\mathsf{PRE}}$ updates at the end of the phase.
P2. The operations 1–3, 5 from Lemma 3.2 are based on extracting an element
and trivially extend to our type of chunks. We smooth (in $O(1)$ time by Lemma
3.8) chunks from ${\mathsf{PL}}$ before applying $\min$ operations; the
correctness of this approach is justified by Lemma 3.6. Since the first
difference of the functions $f_{1},f_{2}$ in a smoothed chunk is $\pm 1$, a
smoothed chunk can be safely extended by extending these functions as in Lemma
3.2(6); this approach was justified in [11, 3]. Then computing $\min$ of
smoothed chunks can be easily done in $O(1)$ time as in Lemma 3.2(7). The
arrays ${\mathsf{PRE}}[p]$ consist of smoothed chunks and $W$ is also
smoothed; drops may occur only between the last element of ${\mathsf{PL}}$ and
the first element of $W$.
P3. _Big_ $p$-series ($p\geq t$) and _small_ $p$-series ($p<t$) are processed
separately.

##### First iteration.

F1. Read the next symbol (say, $s[n]$), perform $\mathsf{add}(n)$; at this
moment
a. the iterator stores $s[0..n]$ and returns the list ${\mathsf{dead}}$;
b. the array ${\mathsf{PL}}[0..n{-}1]$ and the arrays ${\mathsf{PRE}}[p]$ for
$s[0..n{-}1]$ are correctly computed;
c. the chunk $W$ is initialized by $\infty$’s, the list ${\mathsf{wait}}$ is
empty;
d. the maximum number of iterations in the phase is set to
$t^{\prime}=\min\\{n-\mathsf{len}(\mathsf{maxPal}),t\\}$ (if the first number
is smaller, $\mathsf{maxPal}$ must change after at most $t^{\prime}$
iterations).
F2. Loop through the list of big $p$-series of $s[0..n{-}1]$:
a. compute $\mathsf{left}[p]$ and clear ${\mathsf{PRE}}[p]$ if necessary;
b. compute
$\mathsf{ttl}^{\prime}[p]=\min\\{\mathsf{ttl}_{n-1}[p],t^{\prime}\\}$ using
symmetry inside palindromes;
c*. using $\mathsf{left}[p]$ and $\mathsf{ttl}^{\prime}[p]$, update
${\mathsf{PRE}}[p]$, $W$, and ${\mathsf{wait}}$ (details in a separate item
below).
F3. Process new suffix palindromes with centers $n-\frac{1}{2}$ (if
$s[n{-}1]=s[n]$) and $n$:
a. update $W$ directly using the chunks of ${\mathsf{PL}}$ ending at position
$n{-}1$ (and possibly $n{-}2$);
b. using symmetry again, check whether $n$ and/or $n-\frac{1}{2}$ remain
centers of suffix-palindromes after the last iteration of the phase; add the
center(s) with the answer “yes” to the list ${\mathsf{wait}}$.
F4. Small series and finalization:
a. extract from $W$ its last element $m=(m_{0},m_{1})$ and delete it from $W$;
b. process small $p$-series of $s[0..n{-}1]$ directly by Algorithm 1,
substituting $m_{j}$ for $\mathsf{pl}^{j}[n]$;
c. assign ${\mathsf{PL}}[n]=(m_{0},m_{1})$;
d. update arrays ${\mathsf{PRE}}[p]$ with all palindromes from the list
${\mathsf{dead}}$.

##### Subsequent iterations.

S1. Read $s[i]$, compare it to $s[i{-}1{-}\mathsf{len}(\mathsf{maxPal})]$.
S2. If $s[i]$ extends the longest suffix-palindrome, the phase continues:
perform $\mathsf{add}(s[i])$ and then the operations from steps F3 and F4,
replacing $n$ by $i$.
S3. If $s[i]$ breaks the longest suffix-palindrome, the phase is aborted:
a. update the lists ${\mathsf{PRE}}[p]$ using suffix-palindromes from the list
${\mathsf{wait}}$, clear ${\mathsf{wait}}$;
b. start the next phase with $\mathsf{add}(s[i])$.
S4. If there was no abortion and all $t^{\prime}$ symbols were processed, the
phase is terminated:
a. update the lists ${\mathsf{PRE}}[p]$ using suffix-palindromes from
${\mathsf{wait}}$, clear ${\mathsf{wait}}$;
b. start the next phase with $\mathsf{add}(s[n{+}t])$.

##### F2c detailed.

Let $x$ be the center of $\mathsf{tail}(p)$,
$\mathsf{pttl}^{\prime}(x)=\min\\{\mathsf{pttl}_{n-1}(x),t^{\prime}\\}$,
$d=\min\\{\mathsf{ttl}^{\prime}(p),\mathsf{pttl}^{\prime}(x)\\}$. Update
${\mathsf{PRE}}[p]$ with a length-$d$ chunk from ${\mathsf{PL}}$ and $W$ with
the updated length-$d$ chunk from ${\mathsf{PRE}}[p]$. If
$\mathsf{ttl}^{\prime}(p)<\mathsf{pttl}^{\prime}(x)$ (after $d$ iterations
period $p$ dies, but $\mathsf{head}(p)=\mathsf{tail}(p)$ survives, becoming a
palindrome with a bigger period), additionally update $W$ with a chunk of
length $\mathsf{pttl}^{\prime}(x)$; if $\mathsf{pttl}^{\prime}(x)\geq
t^{\prime}$, add $x$ to ${\mathsf{wait}}$. Note that if $p$-series gets new
tail $x{+}\frac{p}{2}$ during the phase, then at the start of the phase
$x{+}\frac{p}{2}$ was the center of the head of some $p^{\prime}$-series,
survived the death of that series, and thus was used for an additional update
of $W$. Necessary updates of ${\mathsf{PRE}}[p]$ are carried when the lists
${\mathsf{dead}}$ and ${\mathsf{wait}}$ are processed. All the same stays true
for $x{+}p$ which is the next potential tail of the $p$-series.

######  Lemma 3.11.

Algorithm EOPL correctly computes the array ${\mathsf{PL}}$.

######  Proof 3.12.

The computation of ${\mathsf{PL}}$ by Algorithm EOPL differs from the correct
computation by Algorithm 1 in a few points. The use of smoothed chunks is
justified by Lemmas 3.6, 3.8, so below we take smoothing into account speaking
about correctness of the arrays ${\mathsf{PRE}}[p]$. We prove the lemma by
induction, with an obvious base and F1b as the hypothesis; more precisely, we
assume that at the start of a new phase with $s[n]$, the array
${\mathsf{PL}}[0..n{-}1]$ and all arrays ${\mathsf{PRE}}[p]$ are correct,
where $p$ runs through the set of live periods of $s[0..n{-}1]$ (i.e.,
$s[0..n{-}1]$ has a $p$-periodic suffix with at least one $p$-periodic
palindrome in it).

First we note that in an aborted phase some predictions in F2c can be made
beyond the actual end of the phase (i.e., the phase processes
$s[n..n{+}i{-}1]$, and updates are made for more than $i$ elements of $W$ and
${\mathsf{PRE}}[p]$). For $W$, this does not matter, because $W$ is translated
to ${\mathsf{PL}}$ one element at a time; see F4a. For ${\mathsf{PRE}}[p]$,
the situation means that the actual symbol $s[n{+}i]$ breaks period $p$,
because it differs from the predicted symbol which preserved the period; thus,
$p$ is dead and ${\mathsf{PRE}}[p]$ will be cleared if more $p$-series appear
in the future.

Next, if $p$ is alive for $s[0..n{+}i{-}1]$, all necessary updates for
${\mathsf{PRE}}[p]$ were made at steps F2c, F4d (useful if a palindrome dies
while its period survives), and S3a/S4a. Note that repeated updates using the
same palindrome (say, first at step F2c and then at F4b) cannot harm.

Finally, all palindromes ending in $s[n{-}1..n{+}i{-}2]$ were used to update
$W$, so ${\mathsf{PL}}[n..n{+}i{-}1]$ is computed according to rule (1). The
result now follows.

######  Lemma 3.13.

If Algorithm EOPL spends, apart from the $\mathsf{add}$ queries, $O(\log P+i)$
time for each phase of $i$ iterations, where $P$ is the period of the longest
suffix-palindrome at the start of the phase, then it works in $O(n)$ time.

######  Proof 3.14.

For a phase of $t$ iterations, $\log P=O(t)$, giving us $O(1)$ time per
iteration. A phase of less than $t$ iterations either was aborted or fell into
the case F1d; in any case, it was followed by an increment of
$\mathsf{maxPal}$ by at least $P/2$. Since $\mathsf{maxPal}$ never decreases
and the iterator performs $n$ $\mathsf{add}$’s in $O(n)$ time, we obtain the
desired bound.

In the next subsection we show how to organize the details of Algorithm EOPL
in order to satisfy the time bound of Lemma 3.13.

###  3.4 Details of Algorithm EOPL

####  3.4.1 Maintaining ${\mathsf{PRE}}[p]$ Arrays

There are two problems related to the crucial task of maintaining the arrays
${\mathsf{PRE}}[p]$. First, a linear-time RAM algorithm should fit into $O(n)$
words of memory. Since Algorithm EOPL clears an array ${\mathsf{PRE}}[p]$ only
before using it next time, these arrays are stored for all periods of
palindromes in the word. Note that a string may contain palindromes with
$\Omega(n)$ distinct periods (e.g., $a_{1}\cdots a_{i}a_{i+1}a_{i}\cdots
a_{1}$ contains palindromes with all even periods up to $2i$). We cannot
allocate $\Omega(n^{2})$ bits of memory, so instead we store only the elements
we computed at least once. The number of such elements is the number of series
of all prefixes in the string, i.e., $O(n\log n)$; this upper bound is OK for
storing ${\mathsf{PRE}}$ in compressed form. We allow for $O(\log n)$
additional elements per array to ease range operations.

The second problem is that ${\mathsf{PRE}}[p]$ may consist of several
unrelated parts, which hardens the use of compression. An example given in
Fig. 3 represents the situation in a quite general form: for the string
$s[0..n]=\cdots babaaabaaab$ the array ${\mathsf{PRE}}[p]$ $(p=4)$ evolves as
follows. At $(n{-}4)$th iteration, the suffix-palindrome $baaab$ appeared,
${\mathsf{PRE}}[4]$ was cleared, and ${\mathsf{PRE}}[p][1]={\mathsf{PL}}[n-9]$
was assigned. At the next iteration we assigned
${\mathsf{PRE}}[p][0]={\mathsf{PL}}[n-10]$ (note that we moved left by 1 in
the array ${\mathsf{PL}}$); ${\mathsf{PRE}}[p][0..1]$ is part 1 of the array.
Then at the $(n{-}2)$th iteration the palindrome $aba\cdot a\cdot aba$ with
the center $n{-}6$ died, reaching $\mathsf{left}[4]$; however, its suffix
$aba$ survived since period 4 survived as well; $aba$ extended to $aabaa$,
which has period 4 but also period 3. Thus, at this moment there was no
$p$-series and ${\mathsf{PRE}}[p][3]$ remained undefined; it constitutes part
3 of the array. Part 3 always corresponds to biggest indices in the array due
to the fact that $\mathsf{left}[p]$ was just reached; this corresponds to
jumping $(p-1)$ symbols right in ${\mathsf{PL}}$. At the $(n{-}1)$th iteration
we assigned ${\mathsf{PRE}}[p][2]={\mathsf{PL}}[n-8]$ (again moving left by 1
in ${\mathsf{PL}}$); ${\mathsf{PRE}}[p][2]$ constitutes part 2. Finally, at
the $n$th iteration we returned to part 1, using ${\mathsf{PL}}[n-5]$ (a jump
$(p-1)$ symbols right in ${\mathsf{PL}}$) to update ${\mathsf{PRE}}[p][1]$. If
the period survives further, then after updating part 1 we make another jump
in ${\mathsf{PL}}$ and fill part 3, then update part 2, and so on.

Figure 3: Filling and updating ${\mathsf{PRE}}[p]$ array. Currently, part 3 is
being filled. Arrows below ${\mathsf{PL}}$ show the order in which the
elements of ${\mathsf{PL}}$, gathered in chunks, are used to fill/update
${\mathsf{PRE}}[p]$.

The general pattern (see Fig. 3) can be restored looking at the order in which
Algorithm 1 fills and updates ${\mathsf{PRE}}[p]$. Filling ${\mathsf{PRE}}[p]$
is started from the element $i=n-\mathsf{len}(x)-\mathsf{left}[p]$, where $x$
is the center of the head of $p$-series, and continues left to the 0’s element
(part 1). At the next iteration $x$ dies; the palindrome with the center
$y=\mathsf{nextPal}(x)$ either has a period smaller than $p$ and we enter part
3, or no such period, and we immediately enter part 2 (part 3 has length 0) to
fill the $(p{-}1)$th element, jumping in ${\mathsf{PL}}$ by $p{-}1$ elements
to the right. As the period survives, the filling and updating of
${\mathsf{PRE}}[p]$ continues as in the above example.

We store ${\mathsf{PRE}}[p]$ as a triple of arrays $(L,C,R)$,
$|L|+|C|+|R|\leq\mathsf{ttl}_{i}[p]$, where $i$ is the iteration in which
${\mathsf{PRE}}[p]$ was cleared last time. The arrays represent, respectively,
part 1, part 2, and part 3 of ${\mathsf{PRE}}[p]$. We also store
$|L|,|C|,|R|$, and the rightmost positions $end_{L},end_{C}$ of the first two
arrays in ${\mathsf{PRE}}[p]$. The arrays are stored as sequences of smoothed
chunks. If we just cleared ${\mathsf{PRE}}[p]$, we define $end_{L}$ and add a
chunk from ${\mathsf{PL}}$ to $L$. All subsequent updates can be partitioned
into “early” ($|L|+|C|+|R|<p$) and “late” ($|L|+|C|+|R|=p$). We first assume
$p>t$. Since a chunk is shorter than $p$, no jumps inside a chunk is possible.
So during early updates we first completely fill $L$, then set $end_{C}$ and
completely fill $C$. Next we update the whole $L$ (using $\min$ operations on
smoothed chunks), and finally fill $R$ (the stage of filling $R$ is shown in
Fig. 3). If some chunk should be applied partially to $C$ and partially to
$R$, we split it in two. During late updates we just perform $\min$ operations
with chunks from corresponding arrays. Overall we perform each update in
$O(1)$ time using table operations (see Lemmas 3.2 and 3.8). Each of three
arrays consists of compressed smoothed chunks; so ${\mathsf{PRE}}[p]$ occupies
$O(|L|+|C|+|R|)$ bits of space and any chunk needed to update ${\mathsf{PL}}$
can be constructed in $O(1)$ time. By construction, the next lemma is
immediate.

######  Lemma 3.15.

Updating ${\mathsf{PRE}}[p]$ with one chunk requires $O(1)$ time.

In the special case of small series we split each input chunk into several
smaller chunks which fit into the arrays $L,C,R$. Then we can state the result
about the “range” updates of the lists ${\mathsf{PRE}}[p]$.

######  Lemma 3.16.

During a phase of length $i$, all range updates of ${\mathsf{PRE}}[p]$ at
steps F2c and S3a/S4a spend in total $O(\log P+i)$ time, where $P$ is the
minimum period, at the end of the phase, of the longest suffix-palindrome of
$s$.

######  Proof 3.17.

For one run of the loop F2, a constant number of updates of
${\mathsf{PRE}}[p]$ with one chunk is performed (the maximum is 3 updates in
case 3), each in $O(1)$ time by Lemma 3.15. Since the longest suffix-
palindrome belongs to $P$-series, the head of the next series has length $<2P$
by Lemma 2.2. Then by Lemma 2.1 the number of series is $O(\log P)$.

Similarly, applying palindromes from the list ${\mathsf{wait}}$ requires
$O(1)$ chunk updates per palindrome if its period is $>i$, and one could write
to the list at most $O(\log P)$ times at step F2c and at most $O(i)$ times at
step F3b, which is exactly the desired bound.

Finally, the palindrome of periods $<i$ are used to update ${\mathsf{PRE}}$ in
chunks only at steps S3a/S4a, and we have $O(i)$ such palindromes. The number
of chunks needed for an update using a palindrome $w$ with period $p$ is
$O(i/p)$. However, $w$ has $O(i/p)$ suffix-palindromes in its series, and all
of them are separate elements of ${\mathsf{wait}}$. So we have only $O(i)$
chunks to apply to ${\mathsf{PRE}}$. The result now follows.

####  3.4.2 Other Details

We analyze the remaining steps of Algorithm EOPL one-by-one, omitting the
$\mathsf{add}$ queries. The steps F1c, F1d require $O(1)$ time; the same is
true for F2a by Lemma 2.5 and for F2b by Lemma 3.18 below.

######  Lemma 3.18.

For a string $s$, suppose that $s[0..n{-}1]$ is processed,
$t^{\prime}=\min\\{t,n-\mathsf{len}(\mathsf{maxPal})\\}$ and the segment
$s[n..n{+}t^{\prime}{-}1]$ will be processed in one phase. Let
$\mathsf{ttl}^{\prime}[p]=\min\\{\mathsf{ttl}_{n-1}[p],t^{\prime}\\}$ and let
$p_{1}>p_{2}>\cdots>p_{m}$ be the periods of all _big_ series of
$s[0..n{-}1]$. Then all values
$\mathsf{ttl}^{\prime}[p_{1}],\ldots,\mathsf{ttl}^{\prime}[p_{m}]$ can be
computed in $O(m)$ time.

######  Proof 3.19.

We loop through the heads of series as in Algorithm 1. Let $x$ be a center of
the head $(uv)^{k}u$ of $p_{i}$-series. As in Lemma 2.5, we compute
$|u|=\mathsf{len}(x)\bmod p_{i}$ and $y=\mathsf{cntr}(|u|)$. Then
$y^{\prime}=2\mathsf{maxPal}-y$ is the center of the prefix-palindrome $u$ of
the longest suffix-palindrome $s[i..n{-}1]$ of $s[0..n{-}1]$; note that the
longest suffix-palindrome of $s[0..n{+}t^{\prime}{-}1]$ is
$z=s[i{-}t^{\prime}..n{+}t^{\prime}{-}1]$ by conditions of the lemma. Let $w$
be the longest palindrome with the center $y^{\prime}$; using the query
$\mathsf{rad}(y^{\prime})$ we determine whether $w$ is located inside $z$ or
begins outside it. In the latter case, $z$ has a $p_{i}$-periodic prefix
ending with $(uv)^{k}u$ and then a $p_{i}$-periodic suffix beginning with
$(uv)^{k}u$. So $\mathsf{ttl}_{n-1}[p_{i}]\geq t^{\prime}$ and then
$\mathsf{ttl}^{\prime}[p_{i}]=t^{\prime}$. In the former case,
$w=\overset{{}_{\leftarrow}}{w}_{1}uw_{1}$, where $w_{1}$ is a proper prefix
of $vu$ because $|vu|=p_{i}>t^{\prime}\geq|w_{1}|$. Hence the period $p_{i}$
breaks on the left of $w$, which means that
$\mathsf{rad}(y^{\prime})=\mathsf{rad}(y)=\mathsf{ttl}_{n-1}[p_{i}]$. All
computations above take $O(1)$ time. The result now follows.

Next, the radii of suffix-palindromes with the centers $n$, $n-{\frac{1}{2}}$
can be found by the use of symmetry inside the longest suffix-palindrome; it
is sufficient to query $\mathsf{rad}(2\mathsf{maxPal}-n)$ and
$\mathsf{rad}(2\mathsf{maxPal}-n+\frac{1}{2})$. After this, step F3a requires
a constant number of chunk updates, $O(i)$ in total for a phase of $i$
iterations. By Lemma 3.2, this takes $O(i)$ time.

For step F4b, Lemma 3.2 allows one to simulate Algorithm 1 in $O(1)$ time per
update as follows: extract an element of $W$, an element of
${\mathsf{PRE}}[p]$ and an element of ${\mathsf{PL}}$, then update the second
with the third and the first with the second. After that, “return” the updated
elements to ${\mathsf{PRE}}[p]$ and $W$, extending 1-element chunk and using
$\min$ operations. Now Corollary 2.13 gives us the time bound $O(t)$ for a
phase of $t$ iterations and $O(P{+}i)$ for the phase aborted after $i$
iterations, where $P$ is the period of the longest suffix-palindrome.

Finally, for step F4d note that we can safely use $O(1)$ time to process one
palindrome from the list, because the total length of all lists
${\mathsf{dead}}$ is upper bounded by $2n$. Since ${\mathsf{dead}}(x)$
contains the answers to all queries about $x$, we compute the period $p$ and
$\mathsf{left}[p]$ in $O(1)$ time. By Lemma 3.15, we can update
${\mathsf{PRE}}[p]$ in $O(1)$ time if $p\geq t$. For $p<t$, we need a closer
look into the purpose of step F4d. This update is useful only if the only
palindrome in the $p$-series died but period $p$ survived (part 3 of
${\mathsf{PRE}}[p]$; see Fig. 3). Being the only palindrome in a series means
$\mathsf{len}(x)<3p$. Therefore, if $\mathsf{len}(x)\geq 3p$, we make no
update (period $p$ died, so ${\mathsf{PRE}}[p]$ will be cleared before the
next use), and if $\mathsf{len}(x)<3p$, then the update requires $O(1)$ chunks
and thus $O(1)$ time by Lemma 3.15.

The above analysis, together with Lemma 3.16, covers all steps of Algorithm
EOPL. Then in total we have $O(\log P+i)$ bound for one phase, plus the
aggregate $O(n)$ time bound for all $\mathsf{add}$ queries and step F4d. Now
the references to Lemma 3.13, Lemma 3.11 and Remark 1.5 finish the proof of
Theorem 1.1.

##  4 Computing $k$-factorization

A run of linear-time Algorithm EOPL leaves the iterator containing the input
string $s=s[0..n{-}1]$ and the arrays $\mathsf{pl}^{0}[0..n{-}1]$,
$\mathsf{pl}^{1}[0..n{-}1]$ for $s$. Let us use them to construct an explicit
$k$-factorization in additional linear time. Let
$k^{\prime}=\mathsf{pl}^{k\bmod 2}[n{-}1]$. By Lemma 1.4, it suffices to build
a $k^{\prime}$-factorization of $s$ in $O(n)$ time, which can be done as
follows.

Algorithm 2 : Computing $k^{\prime}$-factorization

1:for ($i\leftarrow 1;i<k^{\prime};i{+}{+})$ do build a list
$\mathsf{list}[i]$ of all positions $j:\mathsf{pl}^{i\bmod 2}[j]=i$

2:$end\leftarrow n-1$; $factors\leftarrow\\{\\}$

3:for ($i\leftarrow k^{\prime}-1;i>1;i{-}{-}$) do

4: for $j\in\mathsf{list}[i]$ do

5: if $\mathsf{len}(\frac{j+1+end}{2})=end-j$ then break $\triangleright$
$s[j{+}1..end]$ is a palindrome

6: add $s[j{+}1..end]$ to $factors$; $end\leftarrow j$

7:add $s[0..end]$ to $factors$

Algorithm 2 builds a $k^{\prime}$-factorization of $s$ in reversed order,
using a trivial observation that if a string $w$ has even (odd) palindromic
length $i$ then $w=uv$, where $u$ has odd (resp., even) palindromic length
$i{-}1$ and $v$ is a nonempty palindrome. All lists are build in parallel in
linear time. In the main cycle, each position serves as $j$ at most once, so
the algorithm performs $O(n)$ $\mathsf{len}$ queries to the iterator. Thus we
proved

######  Theorem 4.1.

There is a linear-time word-RAM algorithm which, given a string $s$ over a
general alphabet and a number $k$, builds a palindromic $k$-factorization of
$s$ or reports that no such factorization exists.

## References

  * [1] V. Arlazarov, E. Dinic, M. Kronrod, and I. Faradzev.  On economical construction of the transitive closure of a directed graph.  Dokl. Akad. Nauk SSSR, 194(11):1209–1210, 1970.
  * [2] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Simon J. Puglisi, and Shiho Sugimoto.  Diverse palindromic factorization is np-complete.  In Developments in Language Theory - 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings, volume 9168 of Lecture Notes in Computer Science, pages 85–96. Springer, 2015\.  doi:10.1007/978-3-319-21500-6\\_6.
  * [3] Kirill Borozdin, Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur.  Palindromic length in linear time.  In 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, volume 78 of LIPIcs, pages 23:1–23:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.  doi:10.4230/LIPIcs.CPM.2017.23.
  * [4] G. Fici, T. Gagie, J. Kärkkäinen, and D. Kempa.  A subquadratic algorithm for minimum palindromic factorization.  J. of Discrete Algorithms, 28:41–48, 2014.  doi:10.1016/j.jda.2014.08.001.
  * [5] N. J. Fine and H. S. Wilf.  Uniqueness theorems for periodic functions.  Proceedings of the American Mathematical Society, 16(1):109–114, 1965.
  * [6] Anna E. Frid.  Sturmian numeration systems and decompositions to palindromes.  Eur. J. Comb., 71:202–212, 2018.  doi:10.1016/j.ejc.2018.04.003.
  * [7] Anna E. Frid, Svetlana Puzynina, and Luca Q. Zamboni.  On palindromic factorization of words.  Adv. Appl. Math., 50(5):737–748, 2013.  doi:10.1016/j.aam.2013.01.002.
  * [8] Z. Galil and J. Seiferas.  A linear-time on-line recognition algorithm for “Palstar”.  J. ACM, 25:102–111, 1978.
  * [9] T. I, S. Sugimoto, S. Inenaga, H. Bannai, and M. Takeda.  Computing palindromic factorizations and palindromic covers on-line.  In CPM 2014, volume 8486 of LNCS, pages 150–161. Springer, 2014.
  * [10] D. E. Knuth, J. Morris, and V. Pratt.  Fast pattern matching in strings.  SIAM J. Comp., 6:323–350, 1977.
  * [11] D. Kosolobov, M. Rubinchik, and A. M. Shur.  $\mathrm{Pal}^{k}$ is linear recognizable online.  In SOFSEM 2015, volume 8939 of LNCS, pages 289–301. Springer, 2015.  doi:10.1007/978-3-662-46078-8_24.
  * [12] G. Manacher.  A new linear-time on-line algorithm finding the smallest initial palindrome of a string.  J. of the ACM, 22(3):346–351, 1975.
  * [13] Mikhail Rubinchik and Arseny M. Shur.  EERTREE: an efficient data structure for processing palindromes in strings.  Eur. J. Comb., 68:249–265, 2018.  doi:10.1016/j.ejc.2017.07.021.
  * [14] Aleksi Saarela.  Palindromic length in free monoids and free groups.  In Combinatorics on Words - 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11-15, 2017, Proceedings, volume 10432 of Lecture Notes in Computer Science, pages 203–213. Springer, 2017.  doi:10.1007/978-3-319-66396-8\\_19.