Counting and Verifying Maximal Palindromes
Tomohiro I1 , Shunsuke Inenaga2 , Hideo Bannai1 , and Masayuki Takeda1
1

2

Department of Informatics, Kyushu University
Graduate School of Information Science and Electrical Engineering, Kyushu
University
744 Motooka, Nishiku, Fukuoka, 819–0395 Japan.
tomohiro.i@i.kyushu-u.ac.jp
inenaga@c.csce.kyushu-u.ac.jp{bannai,takeda}@inf.kyushu-u.ac.jp

Abstract. A palindrome is a symmetric string that reads the same forward and backward. Let Pals(w) denote the set of maximal palindromesof a string w in which each palindrome is represented by a pair (c, r),where c is the center and r is the radius of the palindrome. We saythat two strings w and z are pal-distinct if Pals(w) 6= Pals(z). Firstly,
we describe the number of pal-distinct strings, and show that we canenumerate all pal-distinct strings in time linear in the output size, foralphabets of size at most 3. These results follow from a close relationshipbetween maximal palindromes and parameterized matching. Secondly,
we present a linear time algorithm which ﬁnds a string w such that
Pals(w) is identical to a given set of maximal palindromes.

1

Introduction

1.1

Palindromes in Strings

A palindrome is a symmetric string that reads the same forward and backward.
Namely, a string w is a palindrome if w = xaxR where x is a string, xR is areversal of x, and a is either a single character or the empty string. Studying
palindromic structures in strings have gathered much attention in theoreticalcomputer science and in its applications.
In word combinatorics, palindromic structures of interesting family of words
have been extensively studied. For example, palindromic factors of Fibonacci
words and Sturmian words were investigated in [11, 12, 19, 26]. A concept called
palindrome complexity of inﬁnite words was introduced in [1] and its extension toﬁnite words was proposed in [2]. Palindromic occurrences in ternary square-freewords were studied in [10].
In algorithmics, several eﬃcient algorithms to compute palindromes in astring have been proposed. Manacher [27] showed a linear-time algorithm tocompute all preﬁx palindromes of an input string, which can immediately be extended to computing maximal palindromes of all positions of the string within
the linear complexity. Another linear-time algorithm for preﬁx palindromes detection was proposed in the KMP pattern matching algorithm paper [24]. There2

Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

exist eﬃcient parallel algorithms to ﬁnd all preﬁx palindromes or all maximal
palindromes of a string [3, 4, 7]. A polynomial-time algorithm to compute all
maximal palindromes from a given compressed string was proposed in [28].
In bioinformatics, some extended concepts of palindromes are known to beimportant in DNA and RNA sequence analysis [25]. An approximate palindrome,
where the ﬁrst half of the palindrome can be transformed into the reversal of
the second half within a predeﬁned edit distance, was introduced in [30]. Gusﬁeld showed a linear-time algorithm to compute maximal palindromes with aﬁxed gap [20]. Kolpakov and Kucherov proposed linear-time solutions allowing
more ﬂexible gaps [25]. In [21] an eﬃcient algorithm to compute all maximal
approximate gapped palindromes was developed.
1.2

Our Contribution

It is natural and convenient to represent each maximal palindrome p of a string
w by a pair (c, r) such that c is the center of p and r is the radius of p. Thisway the set of all maximal palindromes can be represented with O(n) space,
where n is the length of w. In what follows, we assume that the set of maximal
palindromes of a string is represented in this way.
The contribution of this paper is twofold: Firstly, we show new properties ofpalindromes which are closely related to parameterized matching [5]. That is, if
two strings are drawn from an alphabet of size at most 3, then they have the same
set of maximal palindromes if and only if they parameterized match. Based on theabove result and the results from [29], the number of distinct sets of palindromes
for alphabets of size at most 3 can immediately be obtained. Besides, we showthat there exists an eﬃcient algorithm to compute a representative string for all
distinct sets of maximal palindromes for alphabets of size at most 3.
Secondly, we study the problem of inferring a string from a given set of
palindromic structures. Namely, given a set P of pairs (c, r), ﬁnd a string whose
maximal palindromes coincide with P . We propose a linear time solution to thisproblem, which outputs the lexicographically smallest string over a minimumalphabet.
1.3

Related Work

Inferring a string from other string data structures has been widely studied. An
algorithm to ﬁnd a string having a given border array was presented in [16],which runs in linear time for an unbounded alphabet. A simpler linear-time
solution for the same problem for a bounded alphabet was shown in [14]. Lineartime and O(n1.5 )-time inferring algorithms for parameterized versions of border
arrays, on a binary alphabet and an unbounded alphabet, respectively, wererecently proposed [22, 23]. Linear-time inferring algorithms for suﬃx arrays [15,6], KMP failure tables [13, 18], preﬁx tables [8], cover arrays [9], directed acyclic
word graphs [6] and directed acyclic subsequence graphs [6] have been proposed,
which provide us with further insight concerning the data structures.

Counting and Verifying Maximal Palindromes

3

Counting and enumerating some of the above-mentioned data structures havealso been studied in the literature [29, 31, 22, 23].

2

Preliminaries

Let Σ be a ﬁnite alphabet. An element of Σ ∗ is called a string. The length ofa string w is denoted by |w|. The empty string ε is a string of length 0, that
is, |ε| = 0. Let Σ + = Σ ∗ − {ε}. For a string w = xyz, x, y and z are called apreﬁx, substring, and suﬃx of w, respectively. The i-th character of a string w
is denoted by w[i] for 1 ≤ i ≤ |w|, and the substring of a string w that begins at
position i and ends at position j is denoted by w[i : j] for 1 ≤ i ≤ j ≤ |w|. The
empty substring ε of w is denoted by w[i : i − 1] for 1 ≤ i ≤ n. For any stringw, let wR denote the reversed string of w, that is, wR = w[|w|] · · · w[2]w[1].
A string w is called a palindrome if w = wR . If |w| is even, then w is called
an even palindrome, that is, w = xxR for some x ∈ Σ + . If |w| is odd, then w iscalled an odd palindrome, that is, w = xaxR for some x ∈ Σ ∗ and a ∈ Σ. The
radius of a palindrome w is |w|
2 .
The center of a palindromic substring w[i : j] of a string w is i+j
2 . A palindromic substring w[i : j] is called the maximal palindrome at the center i+j
2 if
i+j
no other palindromes at the center 2 have a larger radius than w[i : j], i.e.,
if w[i − 1] 6= w[j + 1], i = 1, or j = |w|. In particular, w[1 : j] is called a preﬁx
palindrome of w, and w[i : |w|] is called a suﬃx palindrome of w.
We denote by (c, r)w the maximal palindrome of a string w whose centeris c and radius is r. We simply write (c, r) when the string w is clear fromthe context. The set of all maximal even and odd palindromes of a string w
is denoted by Pals(w). It is clear that for any string w Pals(w) has exactly
2|w| + 1 elements. Let SPals(w) denote the set of all suﬃx palindromes of w,
that is, SPals(w) = {(c, r) | (c, r) ∈ Pals(w), c + r − 0.5 = n}.
For example, let w = abbacabbba. Then
Pals(w) = {(0.5, 0), (1, 0.5), (1.5, 0), (2, 0.5), (2.5, 2), (3, 0.5), (3.5, 0),(4, 0.5), (4.5, 0), (5, 3.5), (5.5, 0), (6, 0.5), (6.5, 0), (7, 0.5),(7.5, 1), (8, 2.5), (8.5, 1), (9, 0.5), (9.5, 0), (10, 0.5), (10.5, 0)} andSPals(w) = {(8, 2.5), (10, 0.5), (10.5, 0)}.

3

Palindromes and Parameterized Matching

In this section we present new properties of palindromic structures in strings,
with a tight relationship with parameterized matching which was originally introduced by Baker [5].
For any string w, let σw denote the number of distinct characters that appear in w. Any two strings w and z over the alphabet Σ of the same length
are said to parameterized match (p-match in short) if there exists a renaming

4

Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

iw

Fig. 1. Illustration for Observation 1.

bijection f : Σ → Σ which transforms one string into the other [5], that is,
w = f (z[1])f (z[2]) · · · f (z[|z|]). For instance, strings w = abab and z = baba
p-match, since w can be transformed to z by applying a renaming function
f : Σ → Σ such that f (a) = b and f (b) = a.
The following intuitive property indeed holds.
Lemma 1. If two strings w and z p-match, then Pals(w) = Pals(z).
Proof. Assume for contrary that Pals(w) 6= Pals(z). Then there exists at least
one center c such that (c, r) ∈ Pals(w), (c, r0 ) ∈ Pals(z) and r 6= r0 . Assume
w.l.o.g. that r > r0 . Then it holds that w[c − r0 − 0.5] = w[c + r0 + 0.5] andz[c − r0 − 0.5] 6= z[c + r0 + 0.5]. Let a = w[c − r0 − 0.5] = w[c + r0 + 0.5],b = z[c − r0 − 0.5], and b = z[c + r0 + 0.5], where b denotes any characterin Σ − {b}. Then clearly there exists no bijection on the alphabet Σ that cantransform w into z, since a at position c − r0 − 0.5 needs to be mapped to b but
a at position c + r0 + 0.5 needs to be mapped to b. This contradicts that w andz p-match.
ut
The reverse of Lemma 1 is also true if the strings are unary, binary or ternary.
To show it, the following observation is useful.
Observation 1 For any string w of length n ≥ 1 and for any i ≤ n,Pals(w[1 : i]) = {(c, i + 0.5 − c) | (c, r) ∈ Pals(w), c ≤ i + 0.5, c + r − 0.5 > i}∪{(c, r) | (c, r) ∈ Pals(w), c + r − 0.5 ≤ i}.
(See also Fig. 1)
Lemma 2. If Pals(w) = Pals(z) and σw = σz ≤ 3, then w and z p-match.
Proof. Unary case σw = σz = 1. This case is trivial.
Binary case σw = σz = 2. We prove it by induction on the length i of thestrings. When i = 2, clearly two strings w and z of length 2 p-match, if
Pals(w) = Pals(z) and σw = σz = 2.
Suppose that the lemma holds for i = n − 1 ≥ 2. Let w and z be any stringsof length n over Σ, such that Pals(w) = Pals(z) and σw = σz = 2. By
Observation 1 Pals(w[1 : n − 1]) = Pals(z[1 : n − 1]), and by the induction
hypothesis w[1 : n − 1] and z[1 : n − 1] p-match. Let f : Σ → Σ be thebijection which transforms w[1 : n − 1] into z[1 : n − 1].

Counting and Verifying Maximal Palindromes5

1. When w[n − 1] = w[n]. If z[n − 1] 6= z[n], then (n − 0.5, 1) ∈ Pals(w) and(n − 0.5, 0) ∈ Pals(z). However, this contradicts that Pals(w) = Pals(z),and hence z[n − 1] = z[n]. Then f (w[n]) = f (w[n − 1]) = z[n − 1] = z[n],and therefore w and z p-match.
2. When w[n − 1] 6= w[n]. If z[n − 1] = z[n], then (n − 0.5, 0) ∈ Pals(w) and(n − 0.5, 1) ∈ Pals(z). However, this contradicts that Pals(w) = Pals(z),and hence z[n−1] 6= z[n]. Let f (w[n−1]) = z[n−1] = a and f (w[n]) = b.
Since z[n] 6= a, z[n] = b. Hence f (w[n]) = z[n] and therefore w and z
p-match.
Ternary case σw = σz = 3. We prove it by induction on the length i of thestrings. When i = 3, clearly two strings w and z of length 3 p-match, if
Pals(w) = Pals(z) and σw = σz = 3.
Suppose that the lemma holds for i = n − 1 ≥ 3. Let w and z be any stringsof length n over Σ, such that Pals(w) = Pals(z) and and σw = σz = 3. By
similar arguments to the binary case, w[1 : n − 1] and z[1 : n − 1] p-match.
Let g : Σ → Σ be the bijection which transforms w[1 : n − 1] into z[1 : n − 1].
1. When w[n − 1] = w[n]. This case can be shown similarly to the binarycase.
2. When w[n − 1] 6= w[n]. By similar arguments to the binary case, we getz[n − 1] 6= z[n]. Let m be the rightmost position of w[1 : n − 1] such thatw[m] 6= w[n − 1]. Let g(w[n − 1]) = z[n − 1] = a and g(w[n]) = b.
(a) When w[m] = w[n]. Since w[m + 1 : n − 1] is unary, w[m : n] is a
maximal palindrome of w. Since z[m : n] is a maximal palindromeof z, z[n] = z[m] = g(w[m]) = b = g(w[n]). Hence w and z p-match.
(b) When w[m] 6= w[n]. Let g(w[m]) = c. Since w[m + 1 : n − 1] is unary,w[m + 1 : n − 1] is a maximal palindrome of w. Since z[m + 1 :n − 1] is a maximal palindrome of z, z[n] 6= z[m] = g(w[m]) = c.
Additionally, since z[n] 6= z[n − 1] = g(w[n − 1]) = a, z[n] = b =g(w[n]). Consequently w and z p-match.
ut
The next proposition follows from Lemma 2.
Proposition 1. For any string w with σw ≤ 2, there exist no string z such that
Pals(w) = Pals(z) and σz > σw .
It is interesting to see that a similar argument to Lemma 2 does not holdif strings contain 4 or more distinct characters. For instance, two strings w =abbcdaa and z = accdbcc have the same set of maximal palindromes and σw =σz = 4, but w and z do not p-match. Also, Proposition 1 does not hold if
σw ≥ 3. For instance, w = abcabb and z = abcdaa have the same set of maximal
palindromes, while σw = 3 and σz = 4. It is easy to extend the above examples
to inﬁnite sequences of strings with an alphabet of size 4 or more.
Let us deﬁne equivalence relations ≡pal and ≡pm on Σ ∗ byw ≡pal z ⇐⇒ Pals(w) = Pals(z)w ≡pm z ⇐⇒ w and z p-match.

6

Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

By Lemma 1 and Lemma 2, the two equivalence relations are equivalent for|Σ| ≤ 3. Also, if |Σ| ≥ 4, then ≡pm is a reﬁnement of ≡pal .
Denote by [w]pal and [w]pm the equivalence classes with respect to ≡pal and≡pm , respectively. Deﬁne the representative of equivalence class [w]pal to be thelexicographically smallest member of [w]pal , and call each representative a palcanonical string. Moore et al. [29] counted the number of p-canonical strings,
each of which is the representative (i.e., the lexicographically smallest member)of an equivalence class [·]pm . They also presented an algorithm to enumerate
all p-canonical strings. From Lemma 1, Lemma 2 and the results of [29], we
immediately get the following theorems.
Theorem 1. Let p[k, n] be the number of distinct sets of maximal palindromes
for strings of length n containing exactly k characters. Then p[k, n] = S(n, k) for1 ≤ k ≤ 3 and p[k, n] < S(n, k) for k ≥ 4, where S(n, k) is the Stirling numberof the second kind.
Theorem 2. For every pair of integers k ≤ 3 and n ≥ k, all pal-canonicalstrings of length n consisting of exactly k characters can be computed in O(p[k, n])time and space.
Although the above theorems provide us with new insights and an eﬃcientalgorithm, yet they do not immediately help us solve the problem of inferringa string from a given set of maximal palindromes. In the next section, we will
provide a linear-time algorithm to solve it.

4

Inferring a String from Maximal Palindromes

4.1

Problem

Let N be the set of non-negative integers, and let Q = {i | i = 2j , j ∈ N }. In
this section we present a linear-time algorithm to solve the following problem.
Problem 1. Given a ﬁnite set P ⊂ Q × Q, ﬁnd a string w such that P = Pals(w)if such exists.
Concerning Lemma 2 and Proposition 1 of the previous section, we try to
ﬁnd the lexicographically smallest string over a minimum alphabet in solving
Problem 1.
4.2

Linear-Time Algorithm to Compute Maximal Palindromes froma String

Let us recall a linear-time algorithm to compute all maximal palindromes in agiven string, which is an extended version of Manacher’s algorithm that computes all preﬁx palindromes [27]. A pseudo-code of the algorithm is shown in
Algorithm 1. The algorithm is based on the following lemma.

Counting and Verifying Maximal Palindromes

7

Algorithm 1: Manacher’s algorithm to compute all maximal palindromes
in a given string [27].
Input: string w of length n.
Output: compute all maximal palindromes in s.
/* Let w[0] and w[n + 1] be special symbols that do not match othersymbols for convenience.
*/
1 add (0.5, 0) and (n + 0.5, 0) to P ;2 i ← 2; c ← 1; r ← 0.5;
3 while c ≤ n do4
j ← 2c − i;/* Set j to be the mirrored position w.r.t. c. */5while w[i] = w[j] do
6i + +; j − −; r + +;
7
8
9
10
11
12
13
14
15
16
17
18

add (c, r) to P ;d ← 0.5;
while d ≤ r dolet (c − d, r` ) ∈ P ;if r` = r − d then break;rr ← min{r − d, r` };add (c + d, rr ) to P ;d ← d + 0.5;
if d > r then i + +; r ← 0.5;
else r ← r − d;c ← c + d;/* Shift the value of c by d. */return P ;Lemma 3 ([27]). For any string w, let (c, r) ∈ Pals(w) and (c − d, r` ) ∈Pals(w) with some 0 < d ≤ r. Then (c + d, rr ) ∈ Pals(w), whereif r` < r − d,(1)rr ≥ r − d if r` = r − d,rr = r − d if r` > r − d.

(2)
(3)

rr = r`Recall Observation 1. This observation suggests to compute maximal palindromes from left to right in the input string, and therefore Algorithm 1 computes
the radius of each center in increasing order of the centers. Let c be the currently
focused center, that is, for every center less than c, the corresponding radius has
already been computed. Then we compute the radius for c, comparing leftward
and rightward substrings of c until a mismatch occurs. Let (c, r) ∈ Pals(w). The
key of the algorithm is that, if Condition 1 or 3 of Lemma 3 holds for a center
between c and c + r, then the radius of the center can be determined in constanttime. If there exists a center c + d with which Condition 2 holds, then we shift
the currently focused center to the center c + d, and compute the radius for c + d.
Since in this case the radius for c + d is at least r − d, the overall time complexityof Algorithm 1 is linear in the length of the input string.

8

Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

Algorithm 2: Algorithm to compute the lexicographically smallest string
over a minimum alphabet which has a given set of maximal palindromes.
Input: P ⊂ Q × Q.
Output: The lexicographically smallest string w over a minimum alphabet with
Pals(w) = P , if such exists.
1 w[1] ← a;
2 i ← 2; c ← 1; r̂ ← 0.5;
3 while c ≤ n do4
j ← 2c − i;/* Set j to be the mirrored position w.r.t. c. */5let (c, r) ∈ P ;6
if r < r̂ then return invalid;7
while r̂ < r do
8w[i] ← w[j];9i + +; j − −; r̂ + +;10
clear the list of forbidden characters;
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4.3

add w[j] to the list of forbidden characters for w[i];d ← 0.5;
while d ≤ r dolet (c − d, r` ), (c + d, rr ) ∈ P ;if r` = r − d then break;if rr 6= min{r − d, r` } then return invalid;d ← d + 0.5;/* w[i] 6= w[j]. */if d > r thenlet x be the lexicographically smallest character not in the list of
forbidden characters for w[i];w[i] ← x;
i + +; r̂ ← 0.5;
clear the list of forbidden characters;
else r̂ ← r − d;c ← c + d;/* Shift the value of c by d. */return w[1 : n];

Our Algorithm to Compute a String from Maximal Palindromes

Now we consider Problem 1. Any P ⊂ Q × Q is said to be valid if there exists a string w such that Pals(w) = P , and is said to be invalid otherwise.
For P ⊂ Q × Q to be valid, clearly P has to satisfy the following: For each c =0.5, 1, 1.5, . . . , n, n+0.5, there exists (c, r) ∈ P with some r ∈ {0, 0.5, 1, 1.5, . . . , k},where n = b|P |/2c and k = min{c − 0.5, n + 0.5 − c}. Hence in what follows weonly consider as input a set P satisfying the above property.
Algorithm 2 shows our algorithm for Problem 1.
Theorem 3. Given a valid set P ⊂ Q × Q, Algorithm 2 computes the lexicographically smallest string w over a minimum alphabet such that Pals(w) = P ,in linear time and space.

Counting and Verifying Maximal Palindromes

9

Proof. Let (c, r) ∈ P . If Condition 1 or Condition 3 of Lemma 3 holds for thecenter c, then P is never rejected w.r.t. c in line 16 of Algorithm 2. Also, if
Condition 2 of Lemma 3 holds for the center c, then P is never rejected w.r.t. cin line 6 of Algorithm 2. Therefore, if P is a valid set, then it is veriﬁed as valid
by Algorithm 2.
In line 8 of Algorithm 2, w[i] is set to w[j] where j = 2c − i is the mirrored
position of i w.r.t. c. When i goes “outside” of the radius r of the maximal
palindrome (c, r), then w[j] is recorded as a forbidden character for w[i] in line 11,that is, w[i] cannot be equal to w[j]. Then in line 19, w[i] is set to be thelexicographically smallest character that is not in the list of forbidden characters.
Therefore, for a given valid set P Algorithm 2 computes the lexicographicallysmallest string w such that P = Pals(w).
The key for time complexity analysis is how to choose the lexicographicallysmallest character in line 19. We use a bit vector F of length n = b|P |/2cwhere each F [h] corresponds to the h-th lexicographically smallest character.
We initialize F with F [h] = 0 for every 1 ≤ h ≤ n. If a character w[j] isforbidden for w[i] in line 11 and if w[j] is the h-th lexicographically smallest
character, then we set F [h] = 1. After ﬁnding all forbidden characters for w[i],we ﬁnd the lexicographically smallest character for w[i] by scanning F from left
to right until reaching the smallest index k with F [k] = 0. After setting w[i] to be
the k-th lexicographically smallest character, we initialize every entry F [h] = 1
to F [h] = 0.
Since σw ≤ n for any string w of length n, the bit vector F is suﬃciently
large. For each position i, let fc(i) and lc(i) be the ﬁrst (leftmost) center andthe last (rightmost) center w.r.t. i, respectively. Namely, w[i] is determined rightafter lc(i) is obtained by shifting fc(i) several times in line 24, Then, the numberof forbidden characters for w[i] does not exceed 2(lc(i) − fc(i)). Hence the total
number of forbidden characters for all i is bounded by |P |. Consequently we canmaintain the bit vector F in a total of linear time and space.
ut
We remark that Algorithm 2 veriﬁes some invalid sets to be valid. For instance, the following invalid set P is veriﬁed to be valid by Algorithm 2:
P = {(0.5, 0), (1, 0.5), (1.5, 1), (2, 0.5), (2.5, 0), (3, 1.5),(3.5, 0), (4, 0.5), (4.5, 1), (5, 0.5), (5.5, 0)}.
Therefore, we ﬁrstly use Algorithm 2 as a ﬁlter. Consider the case where Algorithm 2 veriﬁes an input set P to be valid. Let w be the output string of
Algorithm 2 w.r.t. P . We then run Algorithm 1 over w to compute Pals(w).
Finally, we check whether Pals(w) = P or not. Note that P is valid if and only
if Pals(w) = P . Hence we obtain:
Theorem 4. Problem 1 can be solved in linear time.
Reducing Extra Space. Here we consider to reduce extra working space of
Algorithm 2. The next lemma is useful to estimate it.

10

Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

c3

c2
d

c1

i

d

a
a

a

a

a
a

Fig. 2. Illustration for Proposition 2.

For any string w, let SPC (w) be the set of centers of suﬃx palindromes ofw, that is,
SPC (w) = {c | (c, r) ∈ SPals(w)}.
Lemma 4 ([17, 28]). For any string w of length n, SPC (w) can be representedby O(log n) arithmetic progressions.
For any w of length n and 1 ≤ i ≤ n, let
MC (i) = {w[2c − i] | (c, r) ∈ Pals(w), i = c + r + 0.5}.
Proposition 2. Let P be the set of maximal palindromes of some string oflength n. Then, there exists a string w over an alphabet of size O(log n) suchthat Pals(w) = P .
Proof. Take any three elements from SPals(w[1 : i − 1]) whose centers belong to
the same arithmetic progression, i.e., (c1 , r1 ), (c2 , r2 ), (c3 , r3 ) ∈ SPals(w[1 : i−1])such that c1 = c2 + d = c3 + 2d for some d > 0 (See also Fig. 2). By mirroringw[2c2 − i] w.r.t. c3 , we get w[2c2 − i] = w[2c3 − (2c2 − i)] = w[2(c3 − c2 ) + i] =w[i−2d]. Similarly by mirroring w[2c1 −i] w.r.t. c2 , w[2c1 −i] = w[2c2 −(2c1 −i)] =w[2(c2 − c1 ) + i] = w[i − 2d]. Then we get w[2c1 − i] = w[i − 2d] = w[2c2 − i].
By Lemma 4, |MC (i)| = O(log i). Since the number of forbidden characters foreach position i is at most |MC (i)|, we conclude that O(log n) distinct characters
are suﬃcient in total.
utSince Algorithm 2 always computes a string over a minimum alphabet, a bit
vector of size O(log n) is actually enough for maintaining the forbidden characters for each position i of the output string.

5

Conclusions and Future WorkIn this paper we studied the problem of counting the number of distinct sets ofmaximal palindromes, and that of ﬁnding a string from a given set of maximal

Counting and Verifying Maximal Palindromes

11

palindromes. For the ﬁrst problem, we showed the exact number for an alphabetof size at most 3. We also showed that there exists an algorithm that enumerates
all pal-canonical strings for an alphabet of size at most 3, which runs in linear
time in the output size. These results follow from the close relationship between
maximal palindromes and parameterized pattern matching for alphabets of size
at most 3. For the second problem, we presented a linear time algorithm thatﬁnds the lexicographically smallest string over a minimum alphabet.
Our future work includes the followings.
1. Counting the number of pal-canonical strings for an alphabet of arbitrarysize.
2. Enumerating all distinct sets of maximal palindromes for an alphabet ofarbitrary size.
3. Finding a string that has a given set of maximal palindromes and contains
exactly k characters, where k is a predeﬁned parameter.

References
1. Allouche, J.P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity.
Theoretical Computer Science 292(1), 9–31 (2003)
2. Anisiu, M.C., Anisiu, V., Kása, Z.: Total palindrome complexity of ﬁnite words.
Discrete Mathematics 310(1), 109–114 (2010)
3. Apostolico, A., Breslauer, D., Galil, Z.: Optimal parallel algorithms for periods,
palindromes and squares. In: Proc. ICALP 1992. LNCS, vol. 623, pp. 296–307(1992)
4. Apostolico, A., Breslauer, D., Galil, Z.: Parallel detection of all palindromes in astring. Theoretical Computer Science 141, 163–173 (1995)
5. Baker, B.S.: Parameterized pattern matching: Algorithms and applications. Journal of Computer and System Sciences 52(1), 28–42 (1996)
6. Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs
and arrays. In: Proc. MFCS 2003. LNCS, vol. 2747, pp. 208–217 (2003)
7. Breslauer, D., Galil, Z.: Finding all periods and initial palindromes of a string inparallel. Algorithmica 14(4), 355–366 (1995)
8. Clément, J., Crochemore, M., Rindone, G.: Reverse engineering preﬁx tables. In:
Proc. STACS 2009. pp. 289–300 (2009)
9. Crochemore, M., Iliopoulos, C., Pissis, S., Tischler, G.: Cover array string reconstruction. In: Proc. CPM 2010. LNCS, vol. 6129, pp. 251–259 (2010)
10. Currie, J.D.: Palindrome positions in ternary square-free words. Theoretical Computer Science 396(1-3), 254–257 (2008)
11. Droubay, X.: Palindromes in the Fibonacci word. Information Processing Letters
55(4), 217–221 (1995)
12. Droubay, X., Pirillo, G.: Palindromes and Sturmian words. Theoretical Computer
Science 223(1-2), 73–85 (1999)
13. Duval, J.P., Lecroq, T., Lefebvre, A.: Eﬃcient validation and construction of border
arrays and validation of string matching automata. RAIRO - Theoretical Informatics and Applications 43(2), 281–297 (2009)14. Duval, J.P., Lecroq, T., Lefevre, A.: Border array on bounded alphabet. Journalof Automata, Languages and Combinatorics 10(1), 51–60 (2005)

12

Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda

15. Duval, J.P., Lefebvre, A.: Words over an ordered alphabet and suﬃx permutations.
Theoretical Informatics and Applications 36, 249–259 (2002)
16. Franek, F., Gao, S., Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying
a border array in linear time. J. Comb. Math. and Comb. Comp. 42, 223–236(2002)
17. Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Eﬃcient algorithms
for Lempel-Ziv encoding. In: Proc. SWAT 1996. LNCS, vol. 1097, pp. 392–403.
Springer-Verlag (1996)
18. Gawrychowski, P., Jez, A., Jez, L.: Validating the Knuth-Morris-Pratt failure function, fast and online. In: Proc. CSR 2010. LNCS, vol. 6072, pp. 132–143 (2010)
19. Glen, A.: Occurrences of palindromes in characteristic Sturmian words. TheoreticalComputer Science 352(1), 31–46 (2006)
20. Gusﬁeld, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University
Press, New York (1997)
21. Hsu, P.H., Chen, K.Y., Chao, K.M.: Finding all approximate gapped palindromes.
In: Proc. ISAAC 2009. LNCS, vol. 5878, pp. 1084–1093 (2009)
22. I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting parameterized border arrays
for a binary alphabet. In: Proc. LATA 2009. LNCS, vol. 5457, pp. 422–433 (2009)
23. I, T., Inenaga, S., Bannai, H., Takeda, M.: Verifying a parameterized border arrayin O(n1.5 ) time. In: Proc. CPM 2010. LNCS, vol. 6129, pp. 238–250 (2010)
24. Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J.
Comput. 6(2), 323–350 (1977)
25. Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. Theoretical Computer Science 410(51), 5365–5373 (2009)
26. de Luca, A., Luca, A.D.: Palindromes in Sturmian words. In: Proc. DLT 2005.
LNCS, vol. 3572, pp. 199–208 (2005)
27. Manacher, G.: A new linear-time “On-Line” algorithm for ﬁnding the smallest
initial palindrome of a string. Journal of the ACM 22(3), 346–351 (1975)
28. Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto,K.: Eﬃcient algorithms to compute compressed longest common substrings andcompressed palindromes. Theoretical Computer Science 410(8–10), 900–913 (2009)
29. Moore, D., Smyth, W.F., Miller, D.: Counting distinct strings. Algorithmica 23(1),1–13 (1999)
30. Porto, A.H.L., Barbosa, V.C.: Finding approximate palindromes in strings. Pattern
Recognition 35(11), 2581–2591 (2002)
31. Schürmann, K.B., Stoye, J.: Counting suﬃx arrays and strings. Theoretical Computer Science 395(2-1), 220–234 (2008)