arXiv:1609.03000v2 [] 22 Mar 2018

Computing longest single-arm-gapped palindromes
in a string
Shintaro Narisada1 , Diptarama1 , Kazuyuki Narisawa1 , Shunsuke Inenaga2 , and
Ayumi Shinohara1
1 Graduate

School of Information Sciences, Tohoku University, Japan
{shintaro narisada, diptarama}@shino.ecei.tohoku.ac.jp
{narisawa, ayumi}@ecei.tohoku.ac.jp
2 Department of Informatics, Kyushu University, Japan
inenaga@inf.kyushu-u.ac.jp

Abstract
In this paper, we introduce new types of approximate palindromes called singlearm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left
or right arm, which is in the form of either wgucuR wR or wucuR gwR , where w and
u are non-empty strings, wR and uR are respectively the reversed strings of w and u,
g is a gap, and c is either a single character or the empty string. We classify SAGPs
into two groups: those which have ucuR as a maximal palindrome (type-1), and
the others (type-2). We propose several algorithms to compute type-1 SAGPs with
longest arms occurring in a given string, based on suffix arrays. Then, we propose
a linear-time algorithm to compute all type-1 SAGPs with longest arms, based
on suffix trees. Also, we show how to compute type-2 SAGPs with longest arms
in linear time. We also perform some preliminary experiments to show practical
performances of the proposed methods.

1

Introduction

A palindrome is a string that reads the same forward and backward. Discovering palindromic structures in strings is a classical, yet important task in combinatorics on words
and string algorithmics (e.g., see [4, 8, 13, 1]). A natural extension to palindromes is
to allow for a gap between the left and right arms of palindromes. Namely, a string
x is called a gapped palindrome if x = wgwR for some strings w, g with |w| ≥ 1 and
|g| ≥ 0. Finding gapped palindromes has applications in bioinformatics, such as finding
secondary structures of RNA sequences called hairpins [9]. If we further allow for another gap inside either arm, then such a palindrome can be written as wg2 ug1 uR wR or
wug1 uR g2 wR for some strings w, g1 , g2 , u with |u| ≥ 1, |g1 | ≥ 0, |g2 | ≥ 0, and |w| ≥ 1.
These types of palindromes characterize hairpins with bulges in RNA sequences, known
to occur frequently in the secondary structures of RNA sequences [15]. Notice that the
special case where |g1 | ≤ 1 and |g2 | = 0 corresponds to usual palindromes, and the
special case where |g1 | ≥ 2 and |g2 | = 0 corresponds to gapped palindromes.
1

In this paper, we consider a new class of generalized palindromes where |g1 | ≤ 1 and
|g2 | ≥ 1, i.e., palindromes with gaps inside one of its arms. We call such palindromes
as single-arm-gapped palindromes (SAGPs). For instance, string abb|ca|cb|bc|bba is an
SAGP of this kind, taking w = abb, g1 = ε (the empty string), g2 = ca, and u = cb.
We are interested in occurrences of SAGPs as substrings of a given string T . For
simplicity, we will concentrate on SAGPs with |g1 | = 0 containing a gap in their left
arms. However, slight modification of all the results proposed in this paper can easily
be applied to all the other cases. For any occurrence of an SAGP wguuR wR beginning
at position b in T , the position b + |wgu| − 1 is called the pivot of the occurrence of
this SAGP. This paper proposes various algorithms to solve the problem of computing
longest SAGPs for every pivot in a given string T of length n. We classify longest
SAGPs into two groups: those which have uuR as a maximal palindrome (type-1 ), and
the others (type-2 ). Firstly, we show a naı̈ve O(n2 )-time algorithm for computing type-1
longest SAGPs. Secondly, we present a simple but practical O(n2 )-time algorithm for
computing type-1 longest SAGPs based on simple scans over the suffix array [14]. We
also show that the running time of this algorithm can be improved by using a dynamic
predecessor/successor data structure. If we employ the van Emde Boas tree [16], we
achieve O((n + occ 1 ) log log n)-time solution, where occ 1 is the number of type-1 longest
SAGPs to output. Finally, we present an O(n + occ 1 )-time solution based on the suffix
tree [17]. For type-2 longest SAGPs, we show an O(n+occ 2 )-time algorithm, where occ 2
is the number of type-2 longest SAGPs to output. Combining the last two results, we
obtain an optimal O(n + occ)-time algorithm for computing all longest SAGPs, where
occ is the number of outputs.
We performed preliminary experiments to compare practical performances of our
algorithms for finding type-1 longest SAGPs; the naı̈ve algorithm, the O(n2 )-time suffix
array based algorithm, and the improved suffix array based algorithm with several kinds
of predecessor/successor data structures.
All proofs omitted due to lack of space can be found in Appendix.
Related work. For a fixed gap length d, one can find all gapped palindromes wgwR
with |g| = d in the input string T of length n in O(n) time [9]. Kolpakov and
Kucherov [12] showed an O(n + L)-time algorithm to compute long-armed palindromes
in T , which are gapped palindromes wgwR such that |w| ≥ |g|. Here, L denotes the number of outputs. They also showed how to compute, in O(n + L) time, length-constrained
palindromes which are gapped palindromes wgwR such that the gap length |g| is in
a predefined range. Recently, Fujishige et al. [6] proposed online algorithms to compute long-armed palindromes and length-constrained palindromes from a given string
T . A gapped palindrome wgwR is an α-gapped palindrome, if |wg| ≤ α|w| for α ≥ 1.
Gawrychowski et al. [7] showed that the maximum number of α-gapped palindromes
occurring in a string of length n is at most 28αn + 7n. Since long-armed palindromes
are 2-gapped palindromes for α = 2, L = O(n) and thus Kolpakov and Kucherov’s
algorithm runs in O(n) time. Gawrychowski et al. [7] also proposed an O(αn)-time
algorithm to compute all α-gapped palindromes in a given string for any predefined
α ≥ 1. We emphasize that none of the above algorithms can directly be applied to
computing SAGPs.

2

2

Preliminaries

Let Σ = {1, . . . , σ} be an integer alphabet of size σ. An element of Σ∗ is called a string.
For any string w, |w| denotes the length of w. The empty string is denoted by ε. Let
Σ+ = Σ∗ − {ε}. For any 1 ≤ i ≤ |w|, w[i] denotes the i-th symbol of w. For a string
w = xyz, strings x, y, and z are called a prefix, substring, and suffix of w, respectively.
The substring of w that begins at position i and ends at position j is denoted by w[i..j]
for 1 ≤ i ≤ j ≤ |w|, i.e., w[i..j] = w[i] · · · w[j]. For j > i, let w[i..j] = ε for convenience.
For two strings X and Y , let lcp(X, Y ) denote the length of the longest common prefix
of X and Y .
For any string x, let xR denote the reversed string of x, i.e. xR = x[|x|] · · · x[1].
A string p is called a palindrome if p = pR . Let T be any string of length n. Let
p = T [b..e] be a palindromic substring of T . The position i = ⌊ b+e
2 ⌋ is called the center
of this palindromic substring p. The palindromic substring p is said to be the maximal
palindrome centered at i iff there are no longer palindromes than p centered at i, namely,
T [b − 1] 6= T [e + 1], b = 1, or e = n.
A string x is called a single-arm-gapped palindrome (SAGP) if x is in the form
of either wgucuR wR or wucuR gwR , with some non-empty strings w, g, u ∈ Σ+ and
c ∈ Σ ∪ {ε}. For simplicity and ease of explanations, in what follows we consider only
SAGPs whose left arms contain gaps and c = ε, namely, those of form wguuR wR .
But our algorithms to follow can easily be modified to compute other forms of SAGPs
occurring in a string as well.
Let b be the beginning position of an occurrence of a SAGP wguuR wR in T , namely
T [b..b + 2|wu| + |g| − 1] = wguuR wR . The position i = b + |wgu| − 1 is called the pivot of
this occurrence of the SAGP. This position i is also the center of the palindrome uuR .
An SAGP wguuR wR for pivot i in string T is represented by a quadruple (i, |w|, |g|, |u|)
of integers. In what follows, we will identify the quadruple (i, |w|, |g|, |u|) with the
corresponding SAGP wguuR wR for pivot i.
For any SAGP x = wguuR wR , let armlen(x) denote the length of the arm of x,
namely, armlen(x) = |wu|. A substring SAGP y = wguuR wR for pivot i in a string
T is said to be a longest SAGP for pivot i, if for any SAGP y ′ for pivot i in T ,
armlen(y) ≥ armlen(y ′ ).
Notice that there can be different choices of u and w for the longest SAGPs at the
same pivot. For instance, consider string ccabcabbace. Then, (7, 1, 3, 2) = c|abc|ab|ba|c
and (7, 2, 3, 1) = ca|bca|b|b|ac are both longest SAGPs (with arm length |wu| = 3) for
the same pivot 7, where the underlines represent the gaps. Of all longest SAGPs for each
pivot i, we regard those that have longest palindromes uuR centered at i as canonical
longest SAGPs for pivot i. In the above example, (7, 1, 3, 2) = c|abc|ab|ba|c is a canonical longest SAGP for pivot 7, while (7, 2, 3, 1) = ca|bca|b|b|ac is not. Let SAGP (T ) be
the set of canonical longest SAGPs for all pivots in T . In this paper, we present several
algorithms to compute SAGP (T ).
For an input string T of length n over an integer alphabet of size σ = nO(1) , we
perform standard preprocessing which replaces all characters in T with integers from
range [1, n]. Namely, we radix sort the original characters in T , and replace each original
character by its rank in the sorted order. Since the original integer alphabet is of size
nO(1) , the radix sort can be implemented with O(1) number of bucket sorts, taking
3

O(n) total time. Thus, whenever we speak of a string T over an integer alphabet of size
nO(1) , one can regard T as a string over an integer alphabet of size n.
Tools: Suppose a string T ends with a unique character that does not appear elsewhere
in T . The suffix tree [17] of a string T , denoted by STree(T ), is a path-compressed trie
which represents all suffixes of T . Then, STree(T ) can be defined as an edge-labelled
rooted tree such that (1) Every internal node is branching; (2) The out-going edges of
every internal node begin with mutually distinct characters; (3) Each edge is labelled
by a non-empty substring of T ; (4) For each suffix s of T , there is a unique leaf such
that the path from the root to the leaf spells out s. It follows from the above definition
of STree(T ) that if n = |T | then the number of nodes and edges in STree(T ) is O(n).
By representing every edge label X by a pair (i, j) of integers such that X = T [i..j],
STree(T ) can be represented with O(n) space. For a given string T of length n over an
integer alphabet of size σ = nO(1) , STree(T ) can be constructed in O(n) time [5]. For
each node v in STree(T ), let str (v) denote the string spelled out from the root to v.
According to Property (4), we sometimes identify each position i in string T with the
leaf which represents the corresponding suffix T [i..n].
Suppose the unique character at the end of string T is the lexicographically smallest
in Σ. The suffix array [14] of string T of length n, denoted SAT , is an array of size
n such that SAT [i] = j iff T [j..n] is the ith lexicographically smallest suffix of T for
1 ≤ i ≤ n. The reversed suffix array of T , denoted SA−1
T , is an array of size n such
[SA
[i]]
=
i
for
1
≤
i
≤
n.
The
longest
common
prefix array of T , denoted
that SA−1
T
T
LCP T , is an array of size n such that LCP T [1] = −1 and LCP T [i] = lcp(T [SAT [i −
1]..n], T [SAT [i]..n]) for 2 ≤ i ≤ n. The arrays SAT , SA−1
T , and LCP T for a given string
O(1)
T of length n over an integer alphabet of size σ = n
can be constructed in O(n)
time [10, 11].
For a rooted tree T , the lowest common ancestor LCAT (u, v) of two nodes u and v
in T is the deepest node in T which has u and v as its descendants. It is known that
after a linear-time preprocessing on the input tree, querying LCAT (u, v) for any two
nodes u, v can be answered in constant time [2].
Consider a rooted tree T where each node is either marked or unmarked. For any
node v in T , let NMAT (v) denote the deepest marked ancestor of v. There exists a
linear-space algorithm which marks any unmarked node and returns NMAT (v) for any
node v in amortized O(1) time [18].
Let A be an integer array of size n. A range minimum query RMQ A (i, j) of a given
pair (i, j) of indices (1 ≤ i ≤ j ≤ n) asks an index k in range [i, j] which stores the
minimum value in A[i..j]. After O(n)-time preprocessing on A, RMQ A (i, j) can be
answered in O(1) time for any given pair (i, j) of indices [2].
Let S be a set of m integers from universe [1, n], where n fits in a single machine
word. A predecessor (resp. successor) query for a given integer x to S asks the largest
(resp. smallest) value in S that is smaller (resp. larger) than x. Let u(m, n), q(m, n)
and s(m, n) denote the time for updates (insertion/deletion) of elements, the time for
predecessor/successor queries, and the space of a dynamic predecessor/successor data
structure. Using a standard balanced binary search tree, we have u(m, n) = q(m, n) =
O(log m) time and s(n, m) = O(m) space. The Y-fast trie [19] achieves u(m, n) =
q(m, n) = O(log log m) expected time and s(n, m) = O(m) space, while the van Emde

4

Boas tree [16] does u(m, n) = q(m, n) = O(log log m) worst-case time and s(n, m) =
O(n) space.

3

Algorithms for computing canonical longest SAGPs

In this section, we present several algorithms to compute the set SAGP (T ) of canonical
longest SAGPs for all pivots in a given string T .
A position i in string T is said to be of type-1 if there exists a SAGP wguuR wR
such that uuR is the maximal palindrome centered at position i, and is said to be of
type-2 otherwise. For example, consider T = baaabaabaacbaabaabac of length 20.
Position 13 of T is of type-1, since there are canonical longest SAGPs (13, 4, 4, 2) =
abaa|baac|ba|ab|aaba and (13, 4, 1, 2) = abaa|c|ba|ab|aaba for pivot 13, where ba|ab is
the maximal palindrome centered at position 13. On the other hand, Position 6 of T is
of type-2; the maximal palindrome centered at position 6 is aaba|abaa but there are no
SAGPs in the form of wgaaba|abaawR for pivot 6. The canonical longest SAGPs for
pivot 6 is (6, 1, 1, 3) = a|a|aba|aba|a.
Let Pos 1 (T ) and Pos 2 (T ) be the sets of type-1 and type-2 positions in T , respectively. Let SAGP (T, i) be the subset of S
SAGP (T ) whose elements are canonical
longest
SAGPs for pivot i. Let SAGP 1 (T ) = i∈Pos 1 (T ) SAGP(T, i) and SAGP 2 (T ) =
S
i∈Pos 2 (T ) SAGP (T, i). Clearly SAGP 1 (T ) ∪ SAGP 2 (T ) = SAGP (T ) and SAGP 1 (T ) ∩
SAGP 2 (T ) = ∅. The following lemma gives an useful property to characterize the type-1
positions of T .
Lemma 1. Let i be any type-1 position of a string T of length n. Then, a SAGP
wguuR wR is a canonical longest SAGP for pivot i iff uuR is the maximal palindrome
centered at i and wR is the longest non-empty prefix of T [i + |uR | + 1..n] such that w
occurs at least once in T [1..i − |u| − 1].
We define two arrays Pals and LMost as follows:
Pals[i] = {r | T [i − r + 1..i + r] is a maximal palindrome in T for pivot i}.
LMost[c] = min{i | T [i] = c} for c ∈ Σ.
By Lemma 1, a position i in T is of type-1 iff LMost[i + Pals[i] + 1] < i − Pals[i].
Lemma 2. Given a string T of length n over an integer alphabet of size nO(1) , we can
determine whether each position i of T is of type-1 or type-2 in a total of O(n) time
and space.
By Lemma 1 and Lemma 2, we can consider an algorithm to compute SAGP (T )
by computing SAGP 1 (T ) and SAGP 2 (T ) separately, as shown in Algorithm 1. In this
algorithm, we also construct an auxiliary array NextPos defined by NextPos[i] = min{j |
i < j, T [i] = T [j]} for each 1 ≤ i ≤ n, which will be used in Section 3.2.
Lemma 3. Algorithm 1 correctly computes SAGP (T ).
In the following subsections, we present algorithms to compute SAGP 1 (T ) and
SAGP 2 (T ) respectively, assuming that the arrays Pals, LMost and NextPos have already been computed.
5

Algorithm 1: computing SAGP (T )
Input: string T of length n
Output: SAGP (T )
1 compute Pals;
/* Algorithm 3 in Appendix */
2 for i = n downto 1 do
3
c = T [i]; NextPos[i] = LMost[c]; LMost[c] = i;
4
5
6
7
8
9
10

for i = 1 to n do
if LMost[i + Pals[i] + 1] < i − Pals[i] then
Pos 1 (T ) = Pos 1 (T ) ∪ {i};
/* position i is of type-1 */
else
Pos 2 (T ) = Pos 2 (T ) ∪ {i};
/* position i is of type-2 */
compute SAGP 1 (T );
compute SAGP 2 (T );

3.1

/* Section 3.1 */
/* Section 3.2 */

Computing SAGP 1 (T ) for type-1 positions

In what follows, we present several algorithms corresponding to the line 9 in Algorithm 1.
Lemma 1 allows us greedy strategies to compute the longest prefix wR of T [i + Pals[i] +
1..n] such that w occurs in T [1..i − Pals[i] − 1].
Naı̈ve quadratic-time algorithm with RMQs.
Let T ′ = T $T R #. We construct the suffix array SAT ′ , the reversed suffix array SA−1
T′ ,
′
′
and the LCP array LCP T for T .
For each Pals[i] in T , for each gap size G = 1, . . . , i − Pals[i] − 1, we compute
W = lcp(T [1..i − Pals[i] − G]R , T [i + Pals[i] + 1..n]) in O(1) time by an RMQ on the
LCP array LCP T ′ . Then, the gap sizes G with largest values of W give all longest
SAGPs for pivot i. Since we test O(n) gap sizes for every pivot i, it takes a total of
O(n2 ) time to compute SAGP 1 (T ). The working space of this method is O(n).
Simple quadratic-time algorithm based on suffix array.
′
R
′
Given a string T , we construct SAT ′ , SA−1
T ′ , and LCP T for string T = T $T # as in the
previous subsection. Further, for each position n + 2 ≤ j ≤ 2n + 1 in the reversed part
T R of T ′ = T $T R #, let op(j) denote its “original” position in the string T , namely, let
op(j) = 2n − j + 2. Let e be any entry of SAT ′ such that SAT ′ [e] ≥ n + 2. We associate
each such entry of SAT ′ with op(SAT ′ [e]).
Let SAT ′ [k] = i + Pals[i] + 1, namely, the kth entry of SAT ′ corresponds to the
suffix T [i + Pals[i] + 1..n] of T . Now, the task is to find the longest prefix wR of
T [i + Pals[i] + 1..n] such that w occurs completely inside T [1..i − Pals[i] − 1]. Let
b = i − Pals[i] + 1, namely, b is the beginning position of the maximal palindrome uuR
centered at i. We can find w for any maximal SAGP wguuR wR for pivot i by traversing
SAT ′ from the kth entry forward and backward, until we encounter the nearest entries
p < k and q > k on SAT ′ such that op(SAT ′ [p]) < b − 1 and op(SAT ′ [q]) < b − 1, if they

6

exist. The size W of w is equal to
max{min{LCP T ′ [p + 1], . . . , LCP T ′ [k]}, min{LCP T ′ [k + 1], . . . , LCP T ′ [q]}}.

(1)

Assume w.l.o.g. that p gives a larger lcp value with k, i.e. W = min{LCP T ′ [p +
1], . . . , LCP T ′ [k]}. Let s be the largest entry of SAT ′ such that s < p and LCP T ′ [s+1] <
W . Then, any entry t of SAT ′ such that s < t ≤ p+1 and op(SAT ′ [t]) < b−1 corresponds
to an occurrence of a longest SAGP for pivot i, with gap size b − op(SAT ′ [t]) − 1. We
output longest SAGP (i, W, b − op(SAT ′ [t]) − 1, |u|) for each such t. The case where q
gives a larger lcp value with k, or p and q give the same lcp values with k can be treated
similarly.
We find p and s by simply traversing SAT ′ from k. Since the distance from k to s
is O(n), the above algorithm takes O(n2 ) time. The working space is O(n).
Algorithm based on suffix array and predecessor/successor queries.
Let occ 1 = |SAGP 1 (T )|. For any position r in T , we say that the entry j of SAT ′ is
active w.r.t. r iff op(SAT ′ [j]) < r − 1. Let Active(r) denote the set of active entries of
SAT ′ for position r, namely, Active(r) = {j | op(SAT ′ [j]) < r − 1}.
Let t1 = p, and let t2 , . . . , th be the decreasing sequence of entries of SAT ′ which
correspond to the occurrences of longest SAGPs for pivot i. Notice that for all 1 ≤ ℓ ≤ h
we have op(SAT ′ [tℓ ]) < b − 1 and hence tℓ ∈ Active(b), where b = i − |u| + 1. Then,
finding t1 reduces to a predecessor query for k in Active(b). Also, finding tℓ for 2 ≤ ℓ ≤ h
reduces to a predecessor query for tℓ−1 in Active(b).
To effectively use the above observation, we compute an array U of size n from P als
such that U [b] stores a list of all maximal palindromes in T which begin at position b if
they exist, and U [b] is nil otherwise. U can be computed in O(n) time e.g., by bucket
sort. After computing U , we process b = 1, . . . , n in increasing order. Assume that when
we process a certain value of b, we have maintained a dynamic predecessor/successor
query data structure for Active(b). The key is that the same set Active(b) can be used
to compute the longest SAGPs for every element in U [b], and hence we can use the
same predecessor/successor data structure for all of them. After processing all elements
in U [b], we insert all elements of Active(b − 1) \ Active(b) to the predecessor/successor
data structure. Each element to insert can be easily found in constant time.
Since we perform O(n + occ 1 ) predecessor/successor queries and O(n) insertion operations in total, we obtain the following theorem.
Theorem 1. Given a string T of size n over an integer alphabet of size σ = nO(1) , we
can compute SAGP 1 (T ) in O(n(u(n, n)+q(n, n))+occ 1 ·q(n, n)) time with O(n+s(n, n))
space by using the suffix array and a predecessor/successor data structure, where occ 1 =
|SAGP 1 (T )|.
Since every element of Active(b) for any b is in range [1, 2n + 2], we can employ
the van Emde Boas tree [16] as the dynamic predecessor/successor data structure using
O(n) total space. Thus we obtain the following theorem.
Theorem 2. Given a string T of size n over an integer alphabet of size σ = nO(1) ,
we can compute SAGP 1 (T ) in O((n + occ 1 ) log log n) time and O(n) space by using the
suffix array and the van Emde Boas tree, where occ 1 = |SAGP 1 (T )|.
7

Optimal-time algorithm based on suffix tree.
In this subsection, we show that the problem can be solved in optimal time and space, using the following three suffix trees regarding the input string T . Let T1 = STree(T $T R #)
for string T $T R # of length 2n + 2, and T2 = STree(T R #) of length n + 1. These suffix
trees T1 and T2 are static, and thus can be constructed offline, in O(n) time for an
integer alphabet. We also maintain a growing suffix tree T2′ = STree(T R [k..n])#) for
decreasing k = n, . . . , 1.
Lemma 4. Given T2 = STree(T R #), we can maintain T2′ = STree(T R [k..n]#) for
decreasing k = n, . . . , 1 incrementally, in O(n) total time for an integer alphabet of size
nO(1) .
Theorem 3. Given a string T of length n over an integer alphabet of size σ = nO(1) ,
we can compute SAGP 1 (T ) in optimal O(n + occ 1 ) time and O(n) space by using suffix
trees, where occ 1 = |SAGP 1 (T )|.
Proof. We first compute the array U . Consider an arbitrary fixed b, and let uuR be a
maximal palindrome stored in U [b] whose center is i = b+|u|−1. Assume that we have a
growing suffix tree T2′ for string T R [n−b+1..n]# which corresponds to the prefix T [1..b]
of T of size b. We use a similar strategy as the suffix array based algorithms. For each
position 2n − b + 2 ≤ j ≤ 2n + 1 in string T ′ = T $T R #, 1 ≤ op(j) ≤ b − 2. We maintain
the NMA data structure over the suffix tree T1 for string T ′ so that all the ancestors of
the leaves whose corresponding suffixes start at positions 2n − b + 2 ≤ j ≤ 2n + 1 are
marked, and any other nodes in T1 remain unmarked at this step.
As in the suffix-array based algorithms, the task is to find the longest prefix wR of
T [i + |uR | + 1..n] such that w occurs completely inside T [1..b − 2] = T [1..i − |u| − 1].
In so doing, we perform an NMA query from the leaf i + |uR | + 1 of T1 , and let v be
the answer to the NMA query. By the way how we have maintained the NMA data
structure, it follows that str (v) = wR .
To obtain the occurrences of w in T [1..b − 2], we switch to T2′ , and traverse the
subtree rooted at v. Then, for any leaf ℓ in the subtree, (i, |str (v)|, b − op(ℓ), |u|) is a
canonical longest SAGP for pivot i (see also Fig. 10 in Appendix).
After processing all the maximal palindromes in U [b], we mark all unmarked ancestors of the leaf 2n−b of T1 in a bottom-up manner, until we encounter the lowest ancestor
that is already marked. This operation is a preprocessing for the maximal palindromes
in U [b + 1], as we will be interested in the positions between 1 and op(2n − b) = b − 1
in T . In this preprocessing, each unmarked node is marked at most once, and each
marked node will remain marked. In addition, we update the growing suffix tree T2′ by
inserting the new leaf for T R [n − b..n]#.
We analyze the time complexity of this algorithm. Since all maximal palindromes in
U [b] begin at position b in T , we can use the same set of marked nodes on T1 for all of
those in U [b]. Thus, the total cost to update the NMA data structure for all b’s is linear
in the number of unmarked nodes that later become marked, which is O(n) overall. The
cost for traversing the subtree of T2′ to find the occurrences of w can be charged to the
number of canonical longest SAGPs to output for each pivot, thus it takes O(occ 1 ) time
for all pivots. Updating the growing suffix tree T2′ takes overall O(n) time by Lemma 4.
8

What remains is how to efficiently link the new internal node introduced in the growing
suffix tree T2′ , to its corresponding node in the static suffix tree T1 for string T ′ . This
can be done in O(1) time using a similar technique based on LCA queries on T1 , as in
the proof of Lemma 4. Summing up all the above costs, we obtain O(n + occ 1 ) optimal
running time and O(n) working space.

3.2

Computing SAGP 2 (T ) for type-2 positions

In this subsection, we present an algorithm to compute SAGP 2 (T ) in a given string T ,
corresponding to the line 10 in Algorithm 1.
Lemma 5. Every (not necessarily longest) SAGP for pivot i must end at one of the
positions between i + 2 and i + Pals[i].
Lemma 6. For any type-2 position i in string T , if wguuR wR is a canonical longest
SAGP for pivot i, then |w| = 1.
For every type-2 position i in T , let u = T [i..i+ Pals[i]]. By Lemma 6, any canonical
longest SAGP is of the form cguuR c for c ∈ Σ. For each 2 ≤ k ≤ Pals[i], let ck = uR [k],
R
and let uR
k be the proper prefix of u of length k − 1. Now, observe that the largest
value of k for which LMost[ck ] ≤ i − |uk | − 1 corresponds to a canonical longest SAGP
for pivot i, namely, ck gk uk uR
k ck is a canonical longest SAGP for pivot i, where gk =
T [LMost[ck ]+1..i−|uk |]. In order to efficiently find the largest value of such, we consider
a function findR(t, i) defined by
findR(t, i) = min{r | t ≤ r < i, T [l] = T [r] for 1 ≤ ∃l < r} ∪ {+∞}.
Lemma 7. For any type-2 position i in T , quadruple (i, 1, r − LMost[T [r]], i − r) represents a canonical longest SAGP for pivot i, where r = findR(i − Pals[i] + 1, i) 6= ∞.
Moreover, its gap is the longest among all the canonical longest SAGPs for pivot i.
By Lemma 7, we can compute a canonical longest SAGP for any type-2 pivot i in
O(1) time, assuming that the function findR(t, i) returns a value in O(1) time. We
define an array FindR of size n by
FindR[t] = min{r | t ≤ r, T [l] = T [r] for 1 ≤ ∃l < r} ∪ {+∞},

(2)

for 1 ≤ t ≤ n. If the array FindR has already been computed, then findR(t, i) can be
obtained in O(1) time by findR(t, i) = FindR[t] if FindR[t] < i, and +∞ otherwise.
Algorithm 2 shows a pseudo-code to compute FindR. Table 2 in Appendix shows
an example.
Lemma 8. Algorithm 2 correctly computes the array FindR in O(n) time and space.
By Lemma 8, we can compute SAGP 2 (T ) for type-2 positions as follows.
Theorem 4. Given a string T of length n over an integer alphabet of size nO(1) , we can
compute SAGP 2 (T ) in O(n + occ 2 ) time and O(n) space, where occ 2 = |SAGP 2 (T )|.

9

Algorithm 2: constructing the array FindR
Input: string T of length n
Output: array FindR of size n
1 Let Occ 1 and Occ 2 be arrays of size ΣT initialized by +∞;
2 Let FindR be an arrays of size n, and let Stack be an empty stack;
3 min in = +∞;
4 for i = n downto 1 do
5
c = T [i]; Occ 2 [c] = Occ 1 [c]; Occ 1 [c] = i;
6
min in = min{min in , Occ 2 [c]};
7
Stack .push(i);
8
while Stack is not empty and LMost[T [Stack .top]] ≥ i do Stack .pop();
9
min out = Stack .top if Stack is not empty else +∞;
10
FindR[i] = min{min in , min out }

Proof. For a given T , we first compute the array FindR by Algorithm 2. By Lemma 7,
we can get a canonical longest SAGP x1 = (i, 1, |g1 |, Pals[i] − r) if Pals[i] − r ≥ 1, in
O(1) time by referring to LMost and FindR. Note that x1 is the one whose gap |g1 |
is the longest. Let b1 = i − Pals[i] + r − |g1 | be the beginning position of x1 in T .
Then the next shorter canonical longest SAGP for the same pivot i begins at position
b2 = NextPos[b1 ]. By repeating this process bj+1 = NextPos[bj ] while the gap size
|gj | = i − Pals[i] + r − bj is positive, we obtain all the canonical longest SAGPs for
pivot i. Overall, we can compute all canonical longest SAGPs for all pivots in T in
O(n + occ 2 ) time. The space requirement is clearly O(n).
We now have the main theorem from Theorem 3, Lemma 2, Lemma 3, and Theorem 4
as follows.
Theorem 5. Given a string T of length n over an integer alphabet of size nO(1) , Algorithm 1 can compute SAGP (T ) in optimal O(n + occ) time and O(n) space, where
occ = |SAGP (T )|.

4

Experiments

In this section, we show some experimental results which compare performance of
our algorithms for computing SAGP 1 (T ). We implemented the naı̈ve quadratic-time
algorithm (Naı̈ve), the simple quadratic-time algorithm which traverses suffix arrays
(Traverse), and three versions of the algorithm based on suffix array and predecessor/successor data structure, each employing red-black trees (RB tree), Y-fast tries
(Y-fast trie), and van Emde Boas trees1 (vEB tree), as the predecessor/successor data
structure.
We implemented all these algorithms with Visual C++ 12.0 (2013), and performed
all experiments on a PC (Intel c Xeon CPU W3565 3.2GHz, 12GB of memory) running
1
We
modified
a
van
Emde
Boas
tree
implementation
https://code.google.com/archive/p/libveb/ so it works with Visual C++.

10

from

on Windows 7 Professional. In each problem, we generated a string randomly and got
the average time for ten times attempts.
Table 1: Running times (in milli-sec.) on randomly generated strings of length 10000,
50000, and 100000 with |Σ| = 10.
n
10000
50000
100000

Naı̈ve
247.2
7661.0
32933.2

Traverse
3.8
18.6
38.7

RB tree
6.3
37.2
80.3

vEB tree
85.7
128.9
191.9

Y-fast trie
11.7
62.6
133.7

We tested all programs on strings of lengths 10000, 50000, and 100000, all from an
alphabet of size |Σ| = 10. Table 1 shows the results . From Table 1, we can confirm
that Traverse is the fastest, while Naı̈ve is by far the slowest. We further tested the
algorithms on larger strings with |Σ| = 10. In this comparison, we excluded Naı̈ve as it
is too slow. The results are shown in Fig. 1. As one can see, Traverse was the fastest
for all lengths. We also conducted the same experiments varying alphabet sizes as 2, 4,
and 20, and obtained similar results as the case of alphabet size 10.
To verify why Traverse runs fastest, we measured the average numbers of suffix array
entries which are traversed, per pivot and output (i.e., canonical longest SAGP). Fig. 2
shows the result. We can observe that although in theory O(n) entries can be traversed
per pivot and output for a string of length n, in both cases the actual number is far
less than O(n) and grows very slowly as n increases. This seems to be the main reason
why Traverse is faster than RB tree, vEB tree, and Y-fast trie which use sophisticated
but also complicated predecessor/successor data structures.
300

Traverse
RB tree
vEB tree
Y-fast trie

30000
25000
20000

# of traversed entries

Running times [ms]

35000

15000
10000
5000
0
1

2

3

4

5

6

7

8

per pivot
per output

250
200
150
100
50
0

9 10

1

6

2

3

4

5

6

7

8

9

10

6

Text length [×10 ]

Text length [×10 ]

Figure 1: Running times (in milli-sec.) on
randomly generated strings of length from
1000000 to 10000000 with |Σ| = 10.

Figure 2: Average numbers of traversed
entries of suffix array per pivot and per
output on randomly generated strings.

References
[1] A. Apostolico, D. Breslauer, and Z. Galil. Parallel detection of all palindromes in
a string. Theor. Comput. Sci., 141(1&2):163–173, 1995.
[2] M. A. Bender and M. Farach-Colton. The LCA problem revisited. In LATIN,
pages 88–94, 2000.
11

[3] M. Crochemore, L. Ilie, C. S. Iliopoulos, M. Kubica, W. Rytter, and T. Walen.
Computing the longest previous factor. Eur. J. Comb., 34(1):15–26, 2013.
[4] X. Droubay and G. Pirillo. Palindromes and Sturmian words. Theor. Comput.
Sci., 223(1-2):73–85, 1999.
[5] M. Farach-Colton, P. Ferragina, and S. Muthukrishnan. On the sorting-complexity
of suffix tree construction. J. ACM, 47(6):987–1011, 2000.
[6] Y. Fujishige, M. Nakamura, S. Inenaga, H. Bannai, and M. Takeda. Finding gapped
palindromes online. In IWOCA 2016, 2016. To appear.
[7] P. Gawrychowski, T. I, S. Inenaga, D. Köppl, and F. Manea. Efficiently finding all
maximal α-gapped repeats. In STACS 2016, pages 39:1–39:14, 2016.
[8] A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni. Palindromic richness. Eur. J.
Comb., 30(2):510–531, 2009.
[9] D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University
Press, 1997.
[10] J. Kärkkäinen, P. Sanders, and S. Burkhardt. Linear work suffix array construction.
J. ACM, 53(6):918–936, 2006.
[11] T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Linear-time longestcommon-prefix computation in suffix arrays and its applications. In CPM 2001,
pages 181–192, 2001.
[12] R. Kolpakov and G. Kucherov. Searching for gapped palindromes. Theor. Comput.
Sci., 410(51):5365–5373, 2009.
[13] G. K. Manacher. A new linear-time on-line algorithm for finding the smallest initial
palindrome of a string. J. ACM, 22(3):346–351, 1975.
[14] U. Manber and E. W. Myers. Suffix arrays: A new method for on-line string
searches. SIAM J. Comput., 22(5):935–948, 1993.
[15] Y.-Z. Shi, F.-H. Wang, Y.-Y. Wu, and Z.-J. Tan. A coarse-grained model with
implicit salt for RNAs: Predicting 3D structure, stability and salt effect. The
Journal of Chemical Physics, 141(10), 2014.
[16] P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In
FOCS, pages 75–84, 1975.
[17] P. Weiner. Linear pattern matching algorithms. In 14th Annual Symposium on
Switching and Automata Theory, pages 1–11, 1973.
[18] J. Westbrook. Fast incremental planarity testing. In ICALP, pages 342–353, 1992.
[19] D. E. Willard. Log-logarithmic worst-case range queries are possible in space Θ(N ).
Information Processing Letters, 17:81–84, 1983.

12

Appendix
A

Proofs

Here, we present proofs that are omitted due to lack of space.

A.1

Proof of Lemma 1

Proof. (⇒) Assume on the contrary that uuR is not the maximal palindrome centered
at i, and let xuuR xR be the maximal palindrome centered at position i with |x| ≥ 1.
If wR = xR , then since position i is of type-1, there must be a SAGP w′ g′ xuuR xR w′R
with |w′ | ≥ 1 for pivot i, but this contradicts that wguuR wR is a longest SAGP for
pivot i. Hence xR is a proper prefix of wR . See Fig. 3. Let xR w′′R = wR . Since w′′R
is a non-empty suffix of wR , w′′ is a non-empty prefix of w. This implies that there
exists a SAGP w′′ g′′ xuuR xR w′′R for pivot i. However, this contradicts that wguuR wR
is a canonical longest SAGP for pivot i. Consequently, uuR is the maximal palindrome
centered at i, and now it immediately follows that wR is the longest non-empty prefix
of T [i + |uR | + 1..n] such that w occurs at least once in T [1..i − |u| − 1].

Figure 3: Illustration for a necessary condition for a canonical longest SAGP (proof of
(⇒) for Lemma 1): wguuR wR is a canonical longest SAGP for pivot i. For the same
pivot i, there cannot exist a SAGP w′′ g′′ xuuR xR w′′R where xuuR xR is the maximal
palindrome centered at i and w′′ is a prefix of w, since it contradicts that wguuR wR is
a canonical longest SAGP for i.
(⇐) First, we show that wguuR wR is a longest SAGP for pivot i. See Fig. 4. Let
be any proper suffix of u, and assume on the contrary that there exists a SAGP
w′ g′ u′ u′R w′R for pivot i such that |w′ u′ | > |wu|. Since |u′ | < |u|, the occurrence of
wR at position i + |uR | is completely contained in the occurrence of w′R at position
i + |u′R |. This implies that any occurrence of w′ to the left of u′ u′R completely contains
an occurrence of w, reflected from the occurrence of wR in w′R . However, the character a
that immediately precedes the occurrence of w in w′ must be distinct from the character
b that immediately follows wR , namely a 6= b. This contradicts that w′ g ′ u′ u′R w′R is a
SAGP for pivot i. Hence, wguuR wR is a longest SAGP for pivot i. Since uuR is the
maximal palindrome centered at i, we cannot extend u to its left nor uR to its right for
the same center i. Thus, wguuR wR is a canonical longest SAGP for pivot i.
u′

13

Figure 4: Illustration for a sufficient condition for a canonical longest SAGP (proof of
(⇐) for Lemma 1): uuR is the maximal palindrome centered at i and wR is the longest
prefix of T [i + |uR wR | + 1..n] such that w occurs at least once in T [1..i − |u| − 1], and
thus c 6= b. Then, there cannot exist a longer SAGP w′ g′ u′ u′R w′R for the same pivot i,
since a 6= b.

A.2

Proof of Lemma 2

Proof. let uuR be the maximal palindrome centered at i. Observe that, by Lemma 1, i
is a type-1 position iff the character a = T [i + |uR | + 1] which immediately follows uR
occurs in T [1..i − |u| − 1]. Recall that |uR | = |u| = Pals[i]. Let ΣT be the set of distinct
characters occurring in T . We construct an array LMost of size |ΣT | such that for
each 1 ≤ j ≤ |ΣT |, LMost[j] stores the leftmost occurrence of the lexicographically jth
character in T . Using the above observation and the array LMost, we can determine in
O(1) time whether a given position i of T is of type-1 or type-2 by LMost[i+Pals[i]+1] <
i − Pals[i]. We can sort the characters in ΣT in O(n) by constructing SAT in O(n) time
and space.

A.3

Proof of Lemma 3

Proof. In line 1, we firstly compute an array Pals. Pals[i] stores radius r of maximal
palindrome centered at i. We can compute Pals in O(n) time and space applying
Manacher’s algorithm [13]. We show how to compute Pals in Algorithm 3.
In the first for-loop, we construct auxiliary arrays LMost and NextPos. The correctness of the computation of these arrays is obvious. We use NextPos when computing
SAGP 2 . In line 6, since we correctly determine which each position of T is of type-1
or type-2 by Lemma 2, we must compute Pos 1 (T ) and Pos 2 (T ) in the second forloop. Therefore, by referring each element of Pos 1 (T ) and Pos 2 (T ) respectively, we can
compute SAGP 1 (T ) and SAGP 2 (T ), namely SAGP (T ).

A.4

Proof of Lemma 4

Proof. We also use SAT R # and SA−1 in our algorithm, and throughout this proof we
abbreviate SAT R # as SA and SA−1
as SA−1 for simplicity. Let PLV and NLV be
T R#
arrays of size n + 1 each, such that for every 1 ≤ j ≤ n + 1,
PLV [j] = max({j ′ | 1 ≤ j ′ < j, SA[j ′ ] > SA[j]} ∪ {−∞}),
NLV [j] = min({j ′ | j < j ′ ≤ n + 1, SA[j ′ ] > SA[j]} ∪ {∞}).
14

Algorithm 3: computing Pals
/* proposed by Manacher [13] */
Input: string T of length n
Output: Pals /*Pals[i] stores the maximal even palindrome for pivot i*/
1 Pals[0] = 0;
2 i = 2; c = 1; r = 0;
3 while c ≤ n do
4
j = 2 ∗ c − j + 1;
5
while T [i] = T [j] do
6
i + +; j − −; r + +;
7
8
9
10
11
12
13
14
15
16

Pals[c] = r;
d = 1;
while d ≤ r do
rl = Pals[c − d];
if rl = r − d then break;
Pals[c + d] = min{r − d, rl };
d + +;
if d > r then i + +; r = 0;
else r = rl ;
c = c + d;

Intuitively, PLV [j] and NLV [j] indicate the entries of SA that correspond to the lexicographically closest suffixes to the left and to the right of the suffix T R [SA[j]..n]#
which occur positions larger than b, respectively. If such entries do not exist, then let
PLV [j] = −∞ and NLV [j] = ∞. See Fig. 5 for concrete examples of PLV and NLV
arrays.
Suppose we have constructed T2′ = STree(T R [k + 1..n]#) up to position k + 1, and
we wish to update it with the new character T R [k] at position k. What is required here
is to insert a new leaf corresponding to the suffix T R [k..n]# to the suffix tree. If we use
a variant of Weiner’s algorithm [17], we can do this in O(log σ) (amortized) time, but
this becomes O(log n) for integer alphabets of size σ = nO(1) , and thus it is not enough
for our goal. To achieve O(1) update time per character, we utilize the power of the
full suffix tree T2 = STree(T R #) and three arrays SA, SA−1 , PLV , and NLV .
In what follows, we focus on the case where PLV [SA−1 [k]] 6= −∞ and NLV [SA−1 [k]]
6= ∞. The case where PLV [SA−1 [k]] = ∞ or NLV [SA−1 [k]] = ∞ is simpler and can
be treated similarly. An key observation is that there is a one-to-one correspondence
between every leaf of STree(T R [k + 1..n]#) and an entry of SA which stores a position
in T R # which is larger than k. Hence, SA[PLV [SA−1 [k]]] and SA[NLV [SA−1 [k]]] will
be, respectively, the left and right neighboring leaves of the new leaf k in the updated
suffix tree STree(T R [k..n]#).
Given the new position k, we access SA[SA−1 [k]] which stores the kth suffix T R [k..n]#.
Then we compute the following values L and R:
L = lcp((T R #)[SA[PLV [SA−1 [k]]..n + 1]], (T R #)[k..n + 1]),
R = lcp((T R #)[k..n + 1], (T R #)[SA[NLV [SA−1 [k]]..n + 1]]).
15

Figure 5: Illustration for the proof of Lemma 4. Consider string T = ccabaabc. Here,
we illustrate incremental construction of the growing suffix tree T2′ for its reversed
string T R # = cbaabacc#. Assume we have constructed T2′ = STree(T R [5..8]#) =
STree(bacc#), and we are to insert a new leaf for the next suffix T R [4..8]# = abacc#
starting at position 4 in T R #. SA−1 [4] = 3, hence we focus on the suffixes of
T R # starting at positions SA[PLV [3]] = SA[1] = 9 and SA[NLV [3]] = SA[4] = 6.
Since lcp(T R [9..8]#, T R [4..8]#) = lcp(#, abacc#) = 0 < lcp(T R [4..8]#, T R [6..8]#) =
lcp(abacc#, acc#) = 1, we split the incoming edge of the leaf SA[4] = 6 and insert the
new leaf SA[3] = 4 as the left neighbor of the leaf 6.
Depending on the values of L and R, we have the following three cases.
• If L > R, then leaf SA[PLV [SA−1 [k]]] will be the left neighbor of the new
leaf b in the updated suffix tree. Thus, we split the in-coming edge to leaf
SA[PLV [SA−1 [k]]] accordingly, and insert the new leaf k.
• If L < R, then leaf SA[NLV [SA−1 [k]]] will be the right neighbor of leaf k in the
updated suffix tree. Thus, we split the in-coming edge to leaf SA[NLV [SA−1 [k]]]
accordingly, and insert the new leaf k.
• If L = R, then leaf SA[PLV [SA−1 [k]]] will be the left neighbor of the new leaf
k and SA[NLV [SA−1 [k]]] will be the right neighbor of leaf k in the updated suffix tree. Thus, we simply insert the new leaf as a child of the parent of leaves
SA[PLV [SA−1 [k]]] and SA[NLV [SA−1 [k]]].
We then associate the new leaf k with the SA−1 [k]-th entry of SA so that later, we can
access to this leaf from SA[SA−1 [k]] in O(1) time. See Fig. 5 for a concrete example on
how we insert a new leaf to the growing suffix tree.
Let us analyze the efficiency of our algorithm. Given SA, PLV [j] and NLV can be
constructed in O(n) time [3]. Then, given a position k in string T R #, we can access the
16

leaves SA[PLV [SA−1 [k]]] and SA[NLV [SA−1 [k]]] of the full suffix tree T2 = STree(T R #)
in O(1) time using SA, SA−1 , PLV , and NLV arrays. The values of L and R can be
computed in O(1) time by two LCA queries on the full suffix tree T2 . In each of the
three cases above, it takes O(1) to insert the new leaf (Notice that we do not have to
maintain balanced search trees for branching nodes, since the leaves are sorted by being
associated with the corresponding entries of SA). Thus, it takes O(1) time to insert a
new leaf to the growing suffix tree T2′ . This completes the proof.

A.5

Proof of Lemma 5

Figure 6: Illustration for Lemma 5.
Proof. See Fig. 6. By definition, it is clear that any SAGP for pivot i must end at
position i + 2 or after that. Now, assume on the contrary that there exists a SAGP
w′ g′ u′ u′R w′R for pivot i such that i + |u′R w′R | > i + |uR | (it ends after position i + |uR |).
Recall that since i is a type-2 position, we have |u′ | < |u|. Let wR be the suffix of w′R
of size |u′R w′R | − |uR |. Then, there exists a SAGP wguuR wR for pivot i where |g| = |g′ |
and uuR is the maximal palindrome centered at i. However, this contradicts that i is a
type-2 position. Hence, any SAGP for pivot i must end at position i + |uR | or before
that.

A.6

Proof of Lemma 6

Figure 7: Illustration for Lemma 6.
R
Proof. Let x1 = w1 g1 u1 uR
1 w1 be a canonical longest SAGP for pivot i, and on the
contrary, suppose that |w1 | ≥ 2. See also Fig 7. Then we can rewrite w1 = w2 w1′ for
two non-empty strings w2 and w1′ . Let uuR be the maximal palindrome centered at i.

17

R
R
Since the position i is type-2, uR
1 w1 is a prefix of u by Lemma 5, so that w1 u1 is a
′
suffix of u. Moreover, let u2 = w1 u1 and g2 be a string satisfying g2 w1′ = w1′ g1 . Then
R R
′
′
R
′
R ′R R
R ′R R
x2 = w2 g2 u2 uR
2 w2 = w2 g2 w1 u1 u2 w2 = w2 g2 w1 u1 u1 w1 w2 = w2 w1 g1 u1 u1 w1 w2 =
′R R
R R
w1 g1 u1 uR
1 w1 w2 = w1 g1 u1 u1 w1 = x1 , that shows x2 is also a SAGP for pivot i.
Because armlen(x2 ) = |w2 u2 | = |w1 u1 | = armlen(x1 ), x2 is also a longest SAGP for
pivot i. Because u2 = w1′ u1 and w1′ 6= ε, we have |u2 | < |u1 |, which contradicts that x1
is a canonical longest SAGP for pivot i.

A.7

Proof of Lemma 7

Figure 8: Illustration for Lemma 7.
Proof. See Fig. 8. Let t be the beginning position of u in T , namely, t = i − |u| + 1.
Let r = findR(t, i) < ∞, and let c = T [r]. Then by definition of findR(t, i), there exists
1 ≤ l < r satisfying T [l] = c. Therefore, x = (i, 1, r − l, i − r) is a SAGP for pivot i.
Moreover, x is canonical longest SAGP because r is minimized, so that |u1 | = i − r is
maximized while |w| is always 1. Recall that LMost[c] is the leftmost position l satisfying
T [l] = c. Hence, the gap size of the canonical longest SAGP (i, 1, r − LMost[T [r]], i − r)
is the longest.

A.8

Proof of Lemma 8

Proof. The correctness of the computation of LMost and NextPos is obvious. Let
min in [t] (resp. min out [t]) be the value of min in (reps. min out ) when i = t in the second
for-loop. We will verify the following loop invariants
min out [t] = min{r | t ≤ r, T [l] = T [r] for 1 ≤ ∃l < t} ∪ {+∞},

(3)

min in [t] = min{r | t ≤ r, T [l] = T [r] for t ≤ ∃l < r} ∪ {+∞},

(4)

which immediately imply Eq. (2), because FindR[t] = min{min out [t], min in [t]} in the
last line. Eq. (4) is derived from the loop invariants
Occ 1 [c] = min{j | T [j] = c, t ≤ j} ∪ {+∞},
Occ 2 [c] = min{j | T [j] = c, Occ 1 [c] < j} ∪ {+∞},

18

for any c ∈ ΣT . On the other hand, Eq. (3) can be rewritten as
min out [t] = min{r | t ≤ r, c = T [r] for some c ∈ ΣT with LMost[c] < t} ∪ {+∞}
= min{r | t ≤ r, LMost [T [r]] < t} ∪ {+∞}
= min{r | LMost[T [r]] < t ≤ r} ∪ {+∞},
and the Stack always keeps the values {r | LMost[T [r]] < t ≤ r} in increasing order
from top to bottom. Thus, Stack .top returns the minimum value among them. The
total running time is O(n), because in the Stack , each element i is pushed at most
once.

19

B

Examples

Here we present several examples for how our algorithms compute SAGP 1 (T ) for a
given string.
Consider string T = acacabaabca and T ′ = acacabaabca$acbaabacaca#, namely,
T = T $T R #. First, we compute Pals and the array U . Assume we are now processing
position b = 6 in T , then U [6] = {(6, 9)}, where (6, 9) represents the maximal palindrome
T [6..9] = baab. Thus we consider pivot i = b + ⌈(9 − 6 + 1)/2⌉ − 1 = 7. We have
determined that the position 7 is of type-1 position in constant time, using Lemma 2.

B.1

Example for suffix array based algorithms

First, we show an example for the algorithm based on the suffix array, and its improved
version with predecessor/successor queries.
We construct the suffix array SAT ′ , the reversed suffix array SA−1
T ′ , and the LCP
′
′
array LCP T for T . In Fig 9, we show these arrays.

′
Figure 9: SAT ′ , LCP T ′ and SA−1
T ′ for string T = acacabaabca$acbaabacaca#.

Let k be the integer such that SAT ′ [k] = i + ⌈(9 − 6 + 1)/2⌉ + 1 = 7 + 3 = 10, namely
k = 19. This can be obtained from SA−1 [10] = 19 (See also Fig 9). To compute the
longest w, we traverse SAT ′ [19] forward and backward, until we encounter the nearest
entries p < k and q > k on SAT ′ such that op(SAT ′ [p]) < 5 and op(SAT ′ [q]) < 5. Note
that these are equivalent to predecessor/successor queries for 19, respectively. Then, we
can find p = 10 and q = 20. Then, the size W of w is computed by
W = max{min{LCP T ′ [11], . . . , LCP T ′ [19]}, min{LCP T ′ [20], . . . , LCP T ′ [20]}},
and we obtain W = 2. In this case, q = 20 gives a larger lcp value with k = 19. Thus,
we output a canonical longest SAGPs (7, 2, 3, 2) = ac|aca|ba|ab|ca. We further traverse
SAT ′ from the 20th entry backward as long as successive entries s fulfill LCP T ′ [s + 1] ≥
W . Then, we find s = 22, thus we output a canonical longest SAGPs (7, 2, 1, 2) =
ac|a|ba|ab|ca. We further traverse SAT ′ from the 17th entry backward, finally we reach
the 24th entry of SAT ′ , which is the last enty of the suffix array. Therefore, we finish
the process for position b = 7.

B.2

Example for suffix tree based algorithm

Next, we show an example for the linear-time algorithm based on the suffix tree.

20

We first construct the suffix tree T1 = STree(T $T R #). Suppose that we have
constructed T2′ = STree(T R [8..11]#) and marked all ancestors of every leaf v such that
19 < v ≤ 24 in T1 . In Fig. 10, we show interesting parts of T1 and T2′ .
To compute the longest w, we perform an NMA query from the leaf i + |uR | + 1 = 10
of T1 . As can be seen in Fig. 10, we obtain the nearest marked node v = NMAT1 (10).
Thus, we know that wR = ca. Next, we switch from the node v of T1 to its corresponding
node v ′ of T2′ using a link between them. Then, we traverse the subtree rooted at v ′
and obtain all occurrences of wR , namely wR = T R [10..11] = T R [8..9] = ca at positions
10 and 8 in the reversed string T R #. Since op(10) = 2 and op(8) = 4, we obtain the
canonical longest SAGPs (7, 2, 3, 2) = ac|aca|ba|ab|ca. and (7, 2, 1, 2) = ac|a|ba|ab|ca
for pivot 7.

Figure 10: Showing interesting parts of T1 = STree(T ′ ) and T2′ = STree(T R [8..11]#),
where T = acacabaabca, T R = acbaabacaca and T ′ = acacabaabca$acbaabacaca#.
In T1 , we represent the marked internal nodes by black circles, the unmarked internal
nodes by white circles, and the leaves by squares in which the numbers denote the
beginning positions of the corresponding suffixes in the string. The dotted line represents
the link between the node for string c in T1 and that in T2′ .

Table 2: Arrays LMost, NextPos, and FindR for a string T = dbbaacbcbad. For the
sake of understanding, we also provide the values of min out and min in in the i-th loop
of Algorithm 2. These values are computed from right to left.

a
b
c
d

LMost
4
2
6
1

T
NextPos
min out
min in
FindR

1 2
d b
11 3
∞ 11
3 3
3 3

3
b
7
3
5
3

21

4
a
5
7
5
5

5
a
10
5
8
5

6
c
8
7
8
7

7
b
9
7
9
7

8 9 10 11
c b a d
∞ ∞ ∞ ∞
8 9 10 11
∞ ∞ ∞ ∞
8 9 10 11

