Computing All Distinct Squares in Linear Time for Integer
Alphabets
Hideo Bannai1 , Shunsuke Inenaga1 , and Dominik Köppl2

arXiv:1610.03421v2 [cs.DS] 20 Feb 2017

1

Department of Informatics, Kyushu University, Japan,
inenaga@inf.kyushu-u.ac.jp, bannai@inf.kyushu-u.ac.jp
2
Department of Computer Science, TU Dortmund, Germany,
dominik.koeppl@tu-dortmund.de
February 21, 2017

Abstract
Given a string on an integer alphabet, we present an algorithm that computes the set of all distinct
squares belonging to this string in time linear to the string length. As an application, we show how
to compute the tree topology of the minimal augmented suffix tree in linear time. Asides from that,
we elaborate an algorithm computing the longest previous table in a succinct representation using
compressed working space.

1

Introduction

A square is a string of the form SS, where S is some non-empty string. It is well-known that a string of
length n contains at most n2 /4 squares. This bound is the number of all squares, i.e., we count multiple
occurrences of the same square, too. If we consider the number of all distinct squares, i.e., we count
exactly one occurrence of each square, then it becomes linear in n: The first linear upper bound was
given by Fraenkel and Simpson [17] who proved that a string of length n contains at most 2n distinct
squares. Later, Ilie [25] showed the slightly improved bound of 2n − Θ(lg n). Recently, Deza et al. [9]
refined this bound to ⌊11n/6⌋. In the light of these results one may wonder whether future results will
“converge” to the upper bound of n: The distinct square conjecture [17, 26] is that a string of length n
contains at most n distinct squares; this number is known to be independent of the alphabet size [33].
However, there still is a big gap between the best known bound and the conjecture. While studying a
combinatorial problem like this, it is natural to think about ways to actually compute the exact number.
This article focuses on a computational problem on distinct squares, namely, we wish to compute
(a compact representation of) the set of all distinct squares in a given string. Gusfield and Stoye [22]
tackled this problem with an algorithm running in O(nσT ) time, where σT denotes the number of different
characters contained in the input text T of length n. Although its running time is optimal O(n) for a

constant alphabet, it becomes O n2 for a large alphabet since σT can be as large as O(n).

We present an algorithm (Sec. 4) that computes this set in O(n) time for a given string of length n
over an integer alphabet of size nO(1) . Like Gusfield and Stoye, we can use the computed set to decorate

1

the suffix tree with all squares (Sec. 6). As an application, we provide an algorithm that computes
the tree topology of the minimal augmented suffix tree [1] in linear time (Sec. 7). The fastest known
algorithm computing this tree topology takes O(n lg n) time [4].
For our approach, we additionally need the longest previous factor table [18, 7]. As a side result of
independent interest, we show in Sec. 3 how to store this table in 2n + o(n) bits, and give an algorithm
that computes it using compressed working space.

2

Definitions

Our computational model is the word RAM model with word size Ω(lg n) for some natural number n.
Let Σ denote an integer alphabet of size σ = |Σ| = nO(1) . An element w in Σ∗ is called a string, and |w|
denotes its length. We denote the i-th character of w with w[i], for 1 ≤ i ≤ |w|. When w is represented
by the concatenation of x, y, z ∈ Σ∗ , i.e., w = xyz, then x, y and z are called a prefix, substring and
suffix of w, respectively. For any 1 ≤ i ≤ j ≤ |w|, let w[i..j] denote the substring of w that begins at
position i and ends at position j in w.
The longest common prefix (LCP) of two strings is the longest prefix shared by both strings.
The longest common extension (LCE) query asks for the longest common prefix of two suffixes of
the same string. The time for an LCE query is denoted by tLCE .
A factorization of a string T is a sequence of non-empty substrings of T such that the concatenations
of the substrings is T . Each substring is called a factor.
In the rest of this paper, we take a string T of length n > 0, and call it the text. We assume that
T [n] = $ is a special character that appears nowhere else in T , so that no suffix of T is a prefix of
another suffix of T . We further assume that T is read-only; accessing a character costs constant time.
We sometimes need the reverse of T , which is given by the concatenation T [n − 1] · · · T [1] · T [n] =
T [n − 1] · · · T [1]$.
The suffix tree of T is the tree obtained by compacting the trie of all suffixes of T ; it has n leaves and
at most n internal nodes. The leaf corresponding to the i-th suffix is labeled with i. Each edge e stores
a string that is called the edge label of e. The string label of a node v is defined as the concatenation
of all edge labels on the path from the root to v; the string depth of a node is the length of its string
label.
SA and ISA denote the suffix array and the inverse suffix array of T , respectively [32]. The access
time to an element of SA is denoted by tSA . LCP is an array such that LCP[i] is the length of the
longest common prefix of T [SA[i]..n] and T [SA[i − 1]..n] for i = 2, . . . , n. For our convenience, we define
LCP[1] := 0.
A range minimum query (RMQ) asks for the smallest value in an integer array for a given range.
There are data structures that can answer an RMQ on an integer array of length n in constant time while
taking 2n+o(n) bits of space [15]. An LCE query for the suffixes T [s..n] and T [t..n] can be answered with
an RMQ data structure on LCP with the range [min(ISA[s], ISA[t]) + 1.. max(ISA[s], ISA[t])] in constant
time.
A bit vector is a string on a binary alphabet. A select query on a bit vector asks the position of
the i-th ‘0’ or ‘1’ in the bit vector. There is a data structure that can be built in O(n) time with O(n)
bits of working space such that it takes o(n) bits on top of the bit vector, and can answer a select query
in constant time [5].
We identify occurrences of substrings with their position and length in the text, i.e., if x is a substring

2

i

1

2

3

4

5

6

7

8

9

10

11

12

T

a

b

a

b

a

a

a

b

a

b

a

$

SA

12

11

5

6

9

3

7

1

10

4

8

2

LCP

0

0

1

2

1

3

3

5

0

2

2

4

PLCP

5

4

3

2

1

2

3

2

1

0

0

0

LPF

0

0

3

2

1

2

5

4

3

2

1

0

Figure 1:
The
arrays SA, LCP,
PLCP and LPF
of the running
example.

of T , then there is a 1 ≤ i ≤ n and a 0 ≤ ℓ ≤ n − i + 1 such that T [i..i + ℓ − 1] = x. In the
following, we will represent the occurrences of substrings by tuples of position and length. When storing
these tuples in a set, we call the set distinct, if there are no two tuples (i, ℓ) and (i′ , ℓ) such that
T [i..i + ℓ − 1] = T [i′ ..i′ + ℓ − 1]. A special kind of substring is a square: A square is a string of the form
SS for S ∈ Σ+ ; we call S and |S| the root and the period of the square SS, respectively. Like with
substrings, we can generate a set containing some occurrences of squares. A set of all distinct squares
is a distinct set of occurrences of squares that is maximal under inclusion.
To compute a set of all distinct squares is the main focus of this paper. We will tackle this problem
theoretically in Sec. 4, and practically in Sec. 5. Finally, we give two applications of this problem in
Sec. 6 and Sec. 7. But before all that, we start with the study of the LPF array needed for our approach
computing all distinct squares:

3

A Compact Representation of the LPF Array

The longest previous factor table LPF of T is formally defined as
LPF[j] := max {ℓ | there exists an i ∈ [1..j − 1] such that T [i, i + ℓ − 1] = T [j, j + ℓ − 1]} .
It is useful for computing the Lempel-Ziv factorization of T = f1 · · · fz , which is defined as fi =
Pi−1
T [k..k + max(1, LPF[k])] with k := j=1 |fj | + 1 for 1 ≤ i ≤ z.
0 0 3 2 1 2 5 4 3 2 1 0

In the following, we will use the text T = ababaaababa$ as our running example whose LPF array is
represented by the small numbers above the characters. The Lempel-Ziv factorization of T is given by
1

2

3

4

5

6

a|b|aba|aa|baba|$, where the small numbers denote the factor indices, and the vertical bars denote the
factor borders. Fig. 1 shows SA, LPF and other used array data structures of our running example.
Corollary 3.1. Given LPF, we can compute the Lempel-Ziv factorization in O(n) time. If the factorization consists of z factors, the factorization can be represented by an array of z lg n bits, where the x-th
entry stores the beginning of the x-th factor.
Alternatively, it can be represented by a bit vector of length n in which we mark the factor beginnings.
A select data structure on top of the bit vector can return the length and the position of a factor in
constant time.
Since we will need LPF in Sec. 4, we are interested in the time and space bounds for computing LPF.
We start with the (to the best of our knowledge) state of the art algorithm with respect to time and
space requirements.
Lemma 3.2 ([8, Theorem 1]). Given SA and LCP, we can compute LPF in O(ntSA ) time. Besides the
output space of n lg n bits, we only need constant working space.

3

Apart from this algorithm, we are only aware of some practical improvements [36, 28].
Let us consider the size of LCP needed in Lem. 3.2. Sadakane [37] showed a 2n + o(n)-bits representation of LCP. Thereto he stores the array PLCP defined as PLCP[SA[i]] = LCP[i] in a bit vector in the
following way (also described in [13]): Since PLCP[1]+ 1, PLCP[2]+ 2, . . . , PLCP[n]+ n is a non-decreasing
sequence with 1 ≤ PLCP[1] + 1 ≤ PLCP[n] + n = n (PLCP[i] ≤ n − i since the terminal $ is a unique
character in T ) the values I[1] := PLCP[1] and I[i] := PLCP[i] − PLCP[i − 1] + 1 (2 ≤ i ≤ n) are nonnegative. By writing I[i] in the unary code 0I[i] 1 to a bit vector S subsequently for each 2 ≤ i ≤ n, we
Pn
can compute PLCP[i] = select1 (S, i) − 2i and LCP[i] = select1 (S, SA[i]) − 2SA[i]. Moreover, i=1 I[i] ≤ n
and therefore S is of length at most 2n.
By using Sadakane’s LCP-representation, we get LPF with the algorithm of Crochemore et al. [8] in
the following time and space bounds:
Corollary 3.3. Having SA and LCP stored in n lg n bits (this allows tSA = O(1)) and 2n + o(n) bits,
respectively, we can compute LPF with O(lg n) additional bits of working space (not counting the space
for LPF) in O(n) time.
By plugging in a suffix array construction algorithm like the in-place construction algorithm by Li
et al. [31], we get the bounds shown in Fig. 2 (since we can build LCP in-place after having SA [23]).
Although this result seems compelling, this approach stores SA and LPF in plain arrays (the former
for getting constant time access). In the following, we will show that the LPF array can be stored more
compactly. We start with a new representation of LPF, for which we use the same trick as for PLCP due
to the following property (which is crucial for squeezing PLCP into 2n + o(n) bits).
Lemma 3.4. n − j ≥ LPF[j] ≥ LPF[j − 1] − 1 for 2 ≤ j ≤ n.
Proof. There is an i with 1 ≤ i < j − 1 such that T [i..i + LPF[j − 1] − 1] = T [j − 1..j − 1 + LPF[j − 1] − 1].
Hence T [i + 1..i + LPF[j − 1] − 1] = T [j..j − 1 + LPF[j − 1] − 1].
We conclude that the sequence LPF[1] + 1, LPF[2] + 2, . . . , LPF[n] + n is non-decreasing with 1 ≤
LPF[1] + 1 ≤ LPF[n] + n ≤ n. We immediately get:
Corollary 3.5. LPF can be represented by a bit vector with a select data structure such that accessing
an LPF value can be performed in constant time. The data structures use 2n + o(n) bits.
To get a better working space bound, we have to come up with a new algorithm since the algorithm
of Lem. 3.2 creates a plain array to get constant time random write-access for computing the entries of
LPF. To this end, we present two algorithms that compute LPF in this representation with the aid of the
suffix tree. The two algorithms are derivatives of the algorithms [30, 16] that compute the Lempel-Ziv

factorization, either in O(n lg lg σ) time using O(n lg σ) bits, or in O n/ǫ2 time using (1+ǫ)n lg n+O(n)

bits, for a constant 0 < ǫ ≤ 1. The current bottleneck of both algorithms is the suffix tree implementation

with respect to space and time. Due to current achievements [35, 31], the algorithms now run in O(n)
time using O(n lg σ) bits, or in O(n/ǫ) time using (1 + ǫ)n lg n + O(n) bits, respectively.
We aim at building the LPF-representation of Cor. 3.5 directly such that we do not need to allocate
the plain LPF array using n lg n bits in the first place. To this end we create a bit vector of length 2n
and store the LPF values in it successively. In more detail, we follow the description of the Lempel-Ziv
factorization algorithms presented in [30, 16]. There, the algorithms are divided into several passes. In
each pass we successively visit leaves in text order (determined by the labels of the leaves). To compute
LPF, we only have to do a single pass. Similarly to the first passes of the two Lempel-Ziv algorithms,
4

algorithm

time

working space

|LPF|

Lem. 3.2,[8]

O(ntSA )

|SA| + |LCP| + O(lg n)

n lg n

Cor. 3.3,[31, 23]

O(n)

n lg n + 2n + O(lg n)

n lg n

Lem. 3.6,[30]

O(n/ǫ)

(1 + ǫ)n lg n + O(n)

2n + o(n)

Lem. 3.6,[16]

O(ntSA )

O(n lg σ)

2n + o(n)

Figure 2: Algorithms
computing
LPF;
space is counted in
bits.
The output
space |LPF| is not
considered as working
space. 0 < ǫ ≤ 1 is a
constant.

we use a bit vector BV to mark already visited internal nodes. On visiting a leaf we climb up the tree
until reaching the root or an already marked node. In the former case (we climbed up to the root) we
output zero. In the latter case, we output the string depth of the marked node. By doing so, we have
computed LPF[1..j] after having processed the leaf with label j.
Lemma 3.6. We can compute LPF in O(ntSA ) time with O(n lg σ) bits of working space, or in O(n/ǫ)
time using (1 + ǫ)n lg n + O(n) bits of working space, for a constant 0 < ǫ ≤ 1. Both variants include
the space of the output in their working spaces.
Proof. Computing the string depth of a node needs access to an RMQ data structure of LCP, and an
access to SA. Both accesses can be emulated by the compressed suffix array in tSA time, given that we
have computed PLCP in the above representation.

4

Computing the Set of All Distinct Squares

Given a string T , our goal is to compute all distinct squares of T . Thereto we return a set of pairs, where
each pair (s, ℓ) consists of a starting position s and a length ℓ such that T [s..s + ℓ − 1] is the leftmost
occurrence of a square. The size of this set is linear due to
Lemma 4.1 (Fraenkel and Simpson [17]). A string of length n can contain at most 2n distinct squares.
We follow the approach of Gusfield and Stoye [22]. Their idea is to compute a set of squares (the set
stores pairs of position and length like described in Sec. 2)1 with which they can generate all distinct
squares. They call this set of squares a leftmost covering set. A leftmost covering set obeys the
property that every square of the text can be constructed by right-rotating a square of this set. A
square (k, ℓ) is constructed by right-rotating a square (i, ℓ) with i ≤ k iff each tuple (i + j, ℓ) with
1 ≤ j ≤ k − i represents a square T [i + j..i + ℓ + j − 1] = T [i + j..i + ℓ − 1]T [i..i + j − 1].
The set of the leftmost occurrences of all squares is a set of all distinct squares. Unfortunately, the
leftmost covering set computed in [22] is not necessarily a set of all distinct squares since (a) it does not
have to be distinct, and (b) a square might be missing that can be constructed by right-rotating a square
of the computed leftmost covering set.
For illustration, the squares of our running example T = ababaaababa$ are highlighted with bars.
The set of all squares is {(1, 4), (2, 4), (5, 2), (6, 2), (7, 4), (8, 4)}. If we take the leftmost occurrences of
all squares, we get {(1, 4), (2, 4), (5, 2)}; this set comprises all squares marked by the solid bars, i.e., the
dotted bars correspond to occurrences of squares that are not leftmost. In this example, the dotted
bars form the set {(6, 2), (7, 4), (8, 4)}, which is a set of all distinct squares. A leftmost covering set is
{(1, 4), (5, 2)}.
1 It differs to the set we want to compute by the fact that they allow, among others, occurrences of the same square in
their set.

5

q
ℓL ℓR ℓ ℓR
L
fx

p

q
ℓL
fx+1

fx−1

ℓR ℓ
p

L

ℓR
fx

Figure 3: Search for squares on Lempel-Ziv borders. The left image corresponds to squares of type
Lem. 4.2(a), the right image to the type Lem. 4.2(b). Given two adjacent factors, we determine a
position q that is p positions away from the border (the direction is determined by the type of square
we want to search for). By two LCE queries we can determine the lengths ℓL and ℓR that indicate the
presence of a square if ℓL + ℓR ≥ p.
Our goal is to compute the set of all leftmost occurrences directly by modifying the algorithm of [22].
To this end, we briefly review how their approach works: They compute their leftmost covering set by
examining the borders between all Lempel-Ziv factors f1 · · · fz = T . That is because of
Lemma 4.2 ([22, Theorem 5]). The leftmost occurrence of a square T [i..i + 2p − 1] touches at least two
Lempel-Ziv factors. Let fx be the factor that contains the center of the square i + p − 1. Then either
(a) the square has its left end (position i) inside fx and its right end (position i + 2p − 1) inside fx+1 ,
or
(b) the left end of the square extends into fx−1 (or even further left). The right end can be contained
inside fx or fx+1 .
Having a data structure for computing LCE queries on the text and on its inverse, they can probe
at the borders of two consecutive factors whether there is a square. Roughly speaking, they have to
check at most |fx | + |fx+1 | many periods at the borders of every two consecutive factors fx and fx+1
Pz
due to the above lemma. This gives x=1 tLCE (|fx | + |fx+1 |) = O(ntLCE ) time, during which they can

compute a leftmost covering set L. Fig. 3 visualizes how the checks are done. Applying the algorithm
on our running example will yield the set L = {(1, 4), (5, 2), (7, 4)}. To transform this set into a set of

all distinct squares, their algorithm runs the so-called Phase II that uses the suffix tree. It begins with
computing the locations of the squares belonging to a subset L′ ⊆ L in the suffix tree in O(n) time. This
subset L′ is still guaranteed to be a leftmost covering set. Finally, their algorithm computes all distinct
squares of the text by right-rotating the squares in L′ . In their algorithm, the right-rotations are done
by suffix link walks over the suffix tree. Their running time analysis is based on the fact that each node
has at most σT incoming suffix links, where σT denotes the number of different characters occurring in
the text T . Given that the number of distinct squares is linear, Phase II runs in O(nσT ) time.
In the following, we will present our modification of the above sketched algorithm. To speed up
the computation, we discard the idea of using the suffix links for right-rotating squares (i.e., we skip
Phase II completely). Instead, we compute a list of all distinct squares directly. To this end, we show
a modification of the sketched algorithm such that it outputs this list sorted first by the lengths (of the
squares), and second by the starting position.
First, we want to show that we can change the original algorithm to output its leftmost covering
set in the above described order. To this end, we iterate over all possible periods, and search not
yet reported squares at all Lempel-Ziv borders, for each period. To achieve linear running time, we
want to skip a factor fx when the period becomes longer than |fx | + |fx+1 |. We can do this with an
array Z of z lg z bits that is zero initialized. When the period p becomes longer than |fx | + |fx+1 |, we
write Z[x] ← min {y > x : |fy | + |fy+1 | ≥ p} such that Z[x] refers to the next factor whose length is
6

sufficiently large. By doing so, if Z[x] 6= 0, we can skip all factors fy with y ∈ [x..Z[x] − 1] in constant
time. This allows us running the modified algorithm still in linear time.
We have to show that the modified algorithm still computes the same set. To this end, let us fix
the period p (over which we iterate in the outer loop). By [22, Lemma 7], processing squares satisfying
Lem. 4.2(a) before processing squares satisfying Lem. 4.2(b) (all squares have the same period p) produces
the desired output for period p.
Finally, we show the modification that computes all distinct squares (instead of the original leftmost
covering set). On a high level, we use an RMQ data structure on LPF to filter already found squares. The
filtered squares are used to determine the leftmost occurrences of all squares by right-rotation. In more
detail, we modify Algorithm 1 of [22] by filtering the squares in the following way (see Algorithm 1): For
each period p, we use a bit vector B marking the beginning positions of all found squares with period p.
On reporting a square, we additionally mark its starting position in B. By doing so, an invariant of the
algorithm below is that all right-rotated squares of a marked square are already reported.
Let us assume that we are searching for the leftmost occurrences of all squares whose periods are
equal to p. Given the starting position s of a square returned by [22, Algorithm 1], we consider the
square (s, 2p) and its right-rotations as candidates of our list: If B[s] = 1, then this square and its
right-rotations have already been reported. Otherwise, we report (s, 2p) if LPF[s] < 2p. In order to
find the leftmost occurrences of all not yet reported right-rotated squares efficiently, we first compute
the rightmost position e of the repetition of period p containing the square (s, 2p) by an LCE query.
Second, we check the interval I := [s + 1.. min(s + p − 1, e − 2p + 1)] for the starting positions of the
squares whose LPF values are less than 2p. To this end, we perform an RMQ query on LPF to find the
position j whose LPF value is minimal in I. If j > 2p, then all squares with period p in the considered
range have already been found, i.e., there is no leftmost occurrence of a square with the period p in this
range. Otherwise, we report (j, 2p) and recursively search for the text position with the minimal LPF
value within the intervals [s + 1..j − 1] and [j + 1.. min(s + p − 1, e − 2p + 1)]. In overall, the time of
the recursion is bounded by twice of the number of distinct squares starting in the interval I, since a
recursion step terminates if it could not report any square.
Theorem 4.3. Given an LCE data structure with tLCE access time and LPF, we can compute all distinct
squares in O(ntLCE + occ) = O(ntLCE ) time, where occ is the number of distinct squares.
Proof. We show that the returned list is the list of all distinct squares. No square occurs in the list
twice since we only report the occurrence of a square (i, ℓ) if LPF[i] < ℓ. Assume that there is a square
missing in the list; let (i, ℓ) be its leftmost occurrence. There is a square (j, ℓ) reported by the (original)
algorithm [22] such that i − ℓ/2 < j ≤ i and right-rotating (j, ℓ) yields (i, ℓ). Since we right-rotate all
found squares, we obviously have reported (j, ℓ).
The occ term in the running time is dominated by the ntLCE term due to Lem. 4.1.

5

Practical Evaluation

We have implemented the algorithm computing the leftmost occurrences of all squares in C++11 [29]. The
primary focus was on the execution time, rather than on a small memory footprint: We have deliberately
chosen plain 32-bit integer arrays for storing all array data structures like SA, LCP and LPF. These data
structures are constructed as follows: First, we generate SA with divsufsort [34]. Subsequently, we
generate LCP with the Φ-algorithm [27], and LPF with the simple algorithm of [8, Proposition 1]. Finally,
we use the bit vector class and the RMQ data structure provided by the sdsl-lite library [20]. In practice,
7

collection
pc-dblp.xml
pc-dna
pc-english
pc-proteins
pc-sources
pcr-cere
pcr-einstein.en
pcr-kernel
pcr-para

σ

maxi LCP[i]

avgLCP

z

maxx |fx |

maxx |fx fx+1 |

|occ|

time

97
17
226
26
231
6
125
161
6

1084
97,979
987,770
45,704
307,871
175,655
935,920
2,755,550
72,544

44
60
9390
278
373
3541
45,983
149,872
2268

7,035,342
13,970,040
13,971,134
20,875,097
11,542,200
1,446,793
49,575
774,532
1,926,563

1060
97,966
987,766
45,703
307,871
175,643
906,995
2,755,550
70,680

1265
97,982
1,094,108
67,809
307,884
185,362
1,634,034
2,755,556
73,735

7412
132,594
13,408
3,108,339
339,818
47,081
18,192,737
9258
37,391

70
310
2639
245
792
535
3953
6608
265

Table 1: Practical evaluation of the algorithm computing all distinct squares on the datasets described in
Sec. 5. Execution time is in seconds. It is the median of several conducted experiments, whose variance
in time was small. We needed approx. 5.73 GB of RAM for each instance. The expression avgLCP is the
average of all LCP values, and z is the number of Lempel-Ziv factors.
it makes sense to use an RMQ only for very large LCP values and periods (i.e., RMQs on LPF) due to
its long execution time. For small values, we naively compared characters, or scanned LPF linearly.
We ran the algorithm on all 200MiB collections of the Pizza&Chili Corpus [12]. The Pizza&Chili
Corpus is divided in a real text corpus with the prefix pc, and in a repetitive corpus with the prefix pcr. The experiments were conducted on a machine with 32 GB of RAM and an Intel Xeon
R

R

CPU E3-1271 v3. The operating system was a 64-bit version of Ubuntu Linux 14.04 with the kernel
version 3.13. We used a single execution thread for the experiments. The source code was compiled
using the GNU compiler g++ 6.2.0 with the compile flags -O3 -march=native -DNDEBUG.
Table 1 shows the running times of the algorithm on the described datasets. It looks like that
large factors tend to slow down the computation, since the algorithm has to check all periods up to
maxx (|fx | + |fx+1 |). This seems to have more impact on the running time than the number of LempelZiv factors z.

6

Decorating the Suffix Tree with All Squares

Gusfield and Stoye described a representation of the set of all distinct squares by a decoration of the
suffix tree, like the highlighted nodes (additionally annotated with its respective square) shown in the
suffix tree of our running example below. This representation asks for a set of tuples of the form (node,
length) such that each square T [i..i + ℓ − 1] is represented by a tuple (v, ℓ), where v is the highest node
whose string label has T [i..i + ℓ − 1] as a (not necessarily proper) prefix.
We show that we can compute this set of tuples
1
in linear time by applying the Phase II algorithm dea
$
b
scribed in Sec. 4 to our computed set of all distinct
12
3
a
a
$
b
5,aa
squares. The Phase II algorithm takes a list Li storing
11 5
14
a
a b
$ a
b
squares starting at text position i, for each 1 ≤ i ≤ n.
5 6
8
10 4
a
$ a
b
Each of these lists has to be sorted in descending order
17,baba
9 3
17
a
$ a
with respect to the squares’ lengths. It is easy to adapt
11,abab
11
8 2
$ a
our algorithm to produce these lists: On reporting a
7 1
square (i, ℓ), we insert it at the front of Li . By doing so, we can fill the lists without sorting, since we
iterate over the period length in the outer loop, while we iterate over all Lempel-Ziv factors in the inner
loop.
Finally, we can conduct Phase II. In the original version, the goal of Phase II was to decorate the suffix
tree with the endpoints of a subset of the original leftmost covering set. We will show that performing
8

exactly the same operations with the set of the leftmost occurrences of all squares will decorate the suffix
tree with all squares directly. In more detail, we first augment the suffix tree leaf having label i with the
list Li , for each 1 ≤ i ≤ n. Subsequently, we follow Gusfield and Stoye [22] by processing every node of
the suffix tree with a bottom-up traversal. During this traversal we propagate the lists of squares from
the leaves up to the root: An internal node u inherits the list of the child whose subtree contains the
leaf with the smallest label among all leaves in the subtree rooted at u. If the edge to the parent node
contains the ending position of one or more squares in the list (these candidates are stored at the front
of the list), we decorate the edge with these squares, and pop them off from the list. By [22, Theorem
8], there is no square of the set L′ (defined in Sec. 4) neglected during the bottom-top traversal. The
same holds if we exchange L′ with our computed set of all distinct squares:
Lemma 6.1. By feeding the algorithm of Phase II with the above constructed lists Li containing the
leftmost occurrences of the squares starting at the text position i, it will decorate the suffix tree with all
distinct squares.
Proof. We adapt the algorithm of Sec. 4 to build the lists Li . These lists contain the leftmost occurrences
of all squares. In the following we show that no square is left out during the bottom-up traversal. Let us
take a suffix tree node u with its children v and w. Without loss of generality, assume that the smallest
label among all leaves contained in the subtree of v is smaller than the label of every leaf contained
in w’s subtree. For the sake of contradiction, assume that the list of w contains the occurrence of a
square (i, ℓ) at the time when we pass the list of v to its parent u. The length ℓ is smaller than v’s string
depth, otherwise it would already have been popped off from the list. But since v’s subtree contains a
leaf whose label j is the smallest among all labels contained in the subtree of w, the square occurs before
at T [j..j + ℓ − 1] = T [i..i + ℓ − 1], a contradiction to the distinctness.
This concludes the correctness of the modified algorithm. We immediately get:
Theorem 6.2. Given LPF, an LCE data structure on the reversed text, and the suffix tree of T , we can
decorate the suffix tree with all squares of the text in O(ntLCE ) time. Asides from these data structures,
we use (occ + n) lg n + z lg z + min(n + o(n) , z lg n) + O(lg n) bits of working space.
Proof. We need (occ + n) lg n bits for storing the lists Li (occ lg n bits for storing the lengths of all
squares in an integer array, and n lg n bits for the pointers to the first element of each list). An LCE
query on the text can be answered by the string depth of a lowest common ancestor in the suffix tree;
most representations can answer string depth and lowest ancestor queries in constant time. The array Z
uses z lg z bits. The Lempel-Ziv factors are represented as in Cor. 3.1.
Corollary 6.3. We can compute the suffix tree and decorate it with all squares of the text in O(n/ǫ)
time using (3n + occ + 2nǫ) lg n + z lg z + O(n) bits, for a constant 0 < ǫ ≤ 1.
Proof. We use Lem. 3.6 to store SA, ISA, LCP, and LPF in (1 + ǫ)n lg n + O(n) bits. Subsequently, we
build an RMQ data structure on LCP such that LCE queries can be answered in constant time. We
additionally need the suffix array, its inverse, and the LCP array (with an RMQ data structure) of the
reversed text to answer LCE queries on the reversed text. Finally, we equip LPF with an RMQ data
structure for the right-rotations.
The values in the lists (i.e., the lengths of the squares starting at a specific position) can be stored in
Pn
Elias-Fano coding [11, 10]. If the list Li stores mi elements, then 2occ + i=1 (mi ⌈lg(n/mi )⌉) + o(occ)

bits are needed to represent the content of all lists. It is easy to implement the popping of the first
9

value from a list with this representation, given that we store an offset value and a pointer to the current
beginning of each list.
As an application, we consider the common squares problem: Given a set of non-empty strings with
a total length n, we want to find all squares that occur in every string in O(n) time. We solve this
problem by first decorating the generalized suffix tree built on all strings with the distinct squares of all
strings. Subsequently, we apply the O(n) time solution of Hui [24] that annotates each internal suffix
tree node v with the number of strings that contain v’s string label. This solves our problem since we
can simply report all squares corresponding to nodes whose string labels are found in all strings. This
also solves the problem asking for the longest common square of all strings in O(n) time, analogously to
the longest common substring problem [21].
Finally, the last section is dedicated to another application of our suffix tree decoration:

7

Computing the Tree Topology of the MAST in Linear Time
A modification of the suffix tree is the minimal aug-

$
12

a
$
11 15
a b
5 6

a
73

71

b
a
14
4

mented suffix tree (MAST) [1]. This tree can answer the number of the non-overlapping occurrences of

b
a substring in T . To this end, it adds some nodes on
4
a
$ a
b
the unary paths of the suffix tree, and augments each
28
10 4
a
$ a
b
internal node with the number of the non-overlapping
9 3
17
2
a
$ a
occurrences of its string label, like in the left tree (the
11
2
8 2
a
$
leaves are shown with their suffix number, each leaf rep7 1
resents a substring that occurs exactly once). The newly created nodes obey the property that the stored
numbers of the MAST nodes on the path from a leaf to the root are strictly increasing. Given a pattern
of length m, the MAST can answer the number of the non-overlapping occurrences of the pattern in
O(m) time. To this end, we traverse the MAST from the root downwards while reading the pattern from
the edge labels. If there is a mismatch, the pattern cannot be found in the text. Otherwise, we end at
reading the label of an edge (u, v); let u be v’s parent. Then the node v is the highest node whose string
label has the pattern as a (not necessarily strict) prefix. By returning the number stored in v we are
done, since this number is the number of non-overlapping occurrences of the pattern in the text. The
MAST can be built in O(n lg n) time [4].
In this section, we show how to compute the tree topology of the MAST in linear time. The topology
of the MAST differs to the suffix tree topology by the fact that the root of each square is the string
label of a MAST node. Our goal is to compute a list storing the information about where to insert the
missing nodes. The list stores tuples consisting of a node v and a length ℓ; we use this information later
to create a new node w splitting the edge (u, v) into (u, w) and (w, v), where u is the (former) parent
of v. We will label (w, v) with the last ℓ characters and (u, v) with the rest of the characters of the edge
label of (u, v).
To this end, we explore the suffix tree with a top-down traversal while locating the roots of the squares
in the order of their lengths. To locate the roots of the squares in linear time we use two data structures.
The first one is a semi-dynamic lowest marked ancestor data structure [19]. It allows marking a node
and querying for the lowest marked ancestor of a node in constant amortized time. We will use it to
mark the area in the suffix tree that has already been processed for finding the roots of the squares.
The second data structure is the list of tuples of the form (node, length) computed in Sec. 6, where

10

each tuple (v, ℓ) consists of the length ℓ of a square T [i..i + ℓ − 1] and the highest suffix tree node v whose
string label has T [i..i + ℓ − 1] as a (not necessarily proper) prefix. We sort this list, which we now call L,
with respect to the square lengths with a linear time integer sorting algorithm.
Finally, we explain the algorithm locating the roots of all squares. We successively process all tuples
of L, starting with the shortest square length. Given a tuple of L containing the node v and the length ℓ,
we want to split an edge on the path from the root to v and insert a new node whose string depth is
ℓ/2. To this end, we compute the lowest marked ancestor u of v. If u’s string depth is smaller than ℓ/2,
we mark all descendants of u whose string depths are smaller than ℓ/2, and additionally the children
of those nodes (this can be done by a DFS or a BFS). If we query for the lowest marked ancestor of u
again, we get an ancestor w whose string depth is at least ℓ/2, and whose parent has a string depth less
than ℓ/2. We report w and the subtraction of ℓ/2 from w’s string depth (if ℓ/2 is equal to the string
depth of w, then w’s string label is equal to the root of v’s string label, i.e., we do not have to report it).
If the suffix tree has a pointer-based representation, it is easy to add the new nodes by splitting each
edge (u, v), where v is a node contained in the output list.
Theorem 7.1. We can compute the tree topology of the MAST in linear time using linear number of
words.
Proof. By using the semi-dynamic lowest marked ancestor data structure, we visit a node as many times
as we have to insert nodes on the edge to its parent, plus one. This gives O(n + 2occ) = O(n) time.

Open Problems
It is left open to compute the number of the non-overlapping occurrences of the string labels of the
MAST nodes in linear time. Since RMQ data structures are practically slow, we wonder whether we can
avoid the use of any RMQ without loosing linear running time.
subsection*Acknowledgements This work was mainly done during a visit at the Kyushu University
in Japan, supported by the Japan Society for the Promotion of Science (JSPS). We thank Thomas
Schwentick for the question whether we can run our algorithm online, for which we provided a solution
in Appendix B.

References
[1] A. Apostolico and F. P. Preparata. Data structures and algorithms for the string statistics problem.
Algorithmica, 15(5):481–494, 1996.
[2] P. Beame and F. E. Fich. Optimal bounds for the predecessor problem and related problems. J.
Comput. Syst. Sci., 65(1):38–72, 2002.
[3] A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. I. Seiferas. The smallest
automaton recognizing the subwords of a text. Theor. Comput. Sci., 40:31–55, 1985.
[4] G. Brodal, R. Lyngsø, A. Östlin, and C. Pedersen. Solving the string statistics problem in time
O(n log n). In Automata, Languages and Programming, volume 2380 of LNCS, pages 728–739.
Springer, 2002.
[5] D. R. Clark. Compact Pat Trees. PhD thesis, University of Waterloo, Canada, 1996.
[6] R. Cole and R. Hariharan. Dynamic LCA queries on trees. SIAM J. Comput., 34(4):894–923, 2005.
11

[7] M. Crochemore and L. Ilie. Computing longest previous factor in linear time and applications. Inf.
Process. Lett., 106(2):75–80, 2008.
[8] M. Crochemore, L. Ilie, C. S. Iliopoulos, M. Kubica, W. Rytter, and T. Walen. LPF computation
revisited. In Proc. IWOCA, pages 158–169, 2009.
[9] A. Deza, F. Franek, and A. Thierry. How many double squares can a string contain? Discrete
Applied Mathematics, 180:52–69, 2015.
[10] P. Elias. Efficient storage and retrieval by content and address of static files. Journal of the ACM,
21:246–260, 1974.
[11] R. M. Fano. On the number of bits required to implement an associative memory. Memorandum
61, Computer Structures Group, Project MAC, 1971.
[12] P.

Ferragina

and

G.

Navarro.

The

Pizza

&

Chili

Corpus.

Available

at

http://pizzachili.di.unipi.it and http://pizzachili.dcc.uchile.cl, 2005.
[13] J. Fischer. Wee LCP. Inform. Process. Lett., 110(8–9):317–320, 2010.
[14] J. Fischer. Inducing the LCP-array. In Proc. WADS, volume 6844 of LNCS, pages 374–385. Springer,
2011.
[15] J. Fischer and V. Heun. Space efficient preprocessing schemes for range minimum queries on static
arrays. SIAM J. Comput., 40(2):465–492, 2011.
[16] J. Fischer, T. I, and D. Köppl. Lempel-Ziv computation in small space (LZ-CISS). In Proc. CPM,
volume 9133 of LNCS, pages 172–184. Springer, 2015.
[17] A. S. Fraenkel and J. Simpson. How many squares can a string contain? J. Comb. Theory, Ser. A,
82(1):112–120, 1998.
[18] F. Franek, J. Holub, W. F. Smyth, and X. Xiao. Computing quasi suffix arrays. Journal of Automata,
Languages and Combinatorics, 8(4):593–606, 2003.
[19] H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. J.
Comput. Syst. Sci., 30(2):209–221, 1985.
[20] S. Gog, T. Beller, A. Moffat, and M. Petri. From theory to practice: Plug and play with succinct
data structures. In Proc. SEA, volume 8504 of LNCS, pages 326–337, 2014.
[21] D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.
[22] D. Gusfield and J. Stoye. Linear time algorithms for finding and representing all the tandem repeats
in a string. J. Comput. Syst. Sci., 69(4):525–546, 2004.
[23] W.-K. Hon and K. Sadakane. Space-economical algorithms for finding maximal unique matches. In
Proc. CPM, volume 2373 of LNCS, pages 144–152. Springer, 2002.
[24] L. C. K. Hui. Color set size problem with application to string matching. In Proc. CPM, volume
644 of LNCS, pages 230–243. Springer, 1992.
[25] L. Ilie. A note on the number of squares in a word. Theor. Comput. Sci., 380(3):373–376, 2007.

12

[26] N. Jonoska, F. Manea, and S. Seki. A stronger square conjecture on binary words. In Proc. SOFSEM
2014, volume 8327 of LNCS, pages 339–350. Springer, 2014.
[27] J. Kärkkäinen, G. Manzini, and S. J. Puglisi. Permuted longest-common-prefix array. In Proc.
CPM, volume 5577 of LNCS, pages 181–192. Springer, 2009.
[28] J. Kärkkäinen, D. Kempa, and S. J. Puglisi. Linear time Lempel-Ziv factorization: Simple, fast,
small. In Proc. CPM, volume 7922 of LNCS, pages 189–200. Springer, 2013.
[29] D.

Köppl.

Computing

all

distinct

squares

efficiently.

Available

at

https://github.com/koeppl/distinct_squares, 2017.
[30] D. Köppl and K. Sadakane. Lempel-Ziv computation in compressed space (LZ-CICS). In Proc.
DCC, pages 3–12. IEEE Computer Society, 2016.
[31] Z. Li, J. Li, and H. Huo. Optimal in-place suffix sorting. ArXiv CoRR, abs/1610.08305, 2016.
[32] U. Manber and E. W. Myers. Suffix arrays: A new method for on-line string searches. SIAM J.
Comput., 22(5):935–948, 1993.
[33] F. Manea and S. Seki. Square-density increasing mappings. In Proc. WORDS 2015, volume 9304
of LNCS, pages 160–169. Springer, 2015.
[34] Y. Mori. divsufsort. Available at https://github.com/y-256/libdivsufsort, 2015.
[35] J. Munro, G. Navarro, and Y. Nekrich. Space-efficient construction of compressed indexes in deterministic linear time. In Proc. SODA, pages 408–424. SIAM, 2017.
[36] E. Ohlebusch and S. Gog. Lempel-Ziv factorization revisited. In Proc. CPM, volume 6661 of LNCS,
pages 15–26. Springer, 2011.
[37] K. Sadakane. Compressed suffix trees with full functionality. Theory Comput. Syst, 41(4):589–607,
2007.
[38] Y. Ueki, Diptarama, M. Kurihara, Y. Matsuoka, K. Narisawa, R. Yoshinaka, H. Bannai, S. Inenaga,
and A. Shinohara. Longest common subsequence in at least k length order-isomorphic substrings.
In Proc. SOFSEM, volume 10139 of LNCS, pages 363–374. Springer, 2017.
[39] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995.
[40] P. Weiner. Linear pattern matching algorithms. In Proc. Annual Symp. on Switching and Automata
Theory, pages 1–11. IEEE Computer Society, 1973.

13

A

Observations

In [22, Line 6 of Algorithm 1b], the condition start + k < h1 has to be changed to start + k ≤ h1 .
Otherwise, the algorithm would find in T = abaabab$ only the square aa, but not abaaba.

B

Online Variant

In this section, we consider the online setting, where new characters are appended to the end of the text T .
Given the text T [1..i] up to position i with the Lempel-Ziv factorization f1 · · · fy = T , we consider computing the set of all distinct squares of f1 · · · fy−2 , i.e., up to the last two
factors. For this set- 
 Lempel-Ziv

p
2
ting, we show that we can compute the set of all distinct squares in O n min lg lg n/ lg lg lg n, lg n/ lg lg n
time using O(n) words of space. To this end, we adapt the algorithm of Theorem 4.3 to the online setting.
We need an algorithm computing LPF online, and a semi-dynamic LCE data structure (answering LCE
queries on the text and on the reversed text while supporting appending characters to the text).
The main idea of our solution is to build suffix trees with two online suffix tree construction algorithms.
The first is Ukkonen’s algorithm that computes the suffix tree online in O(ntnav ) time [39], where tnav is
the time for inserting a node and navigating (in particular, selecting the child on the edge starting with a
specific character). We can adapt this algorithm to compute LPF online: Assume that we have computed
the suffix tree of T [1..i − 1]. The algorithm processes the new character T [i] by (1) taking the suffix links
of the current suffix tree, and (2) adding new leaves where a branching occurs. On adding a new leaf with
suffix number i, we additionally set LPF[i] to the string depth of its parent. By doing so, we can update
the LPF values in time linear to the update time of the suffix tree. We build the semi-dynamic RMQ
data structure of Fischer [14] (or of [38] if n is known beforehand) on top of LPF. This data structure
takes O(n) words and can perform query and appending operations in constant amortized time.
The second suffix tree construction algorithm is a modified version [3] of Weiner’s algorithm [40] that
builds the suffix tree in the reversed order of Ukkonen’s algorithm in O(ntnav ) time. Since Weiner’s
algorithm incrementally constructs the suffix tree of a given text from right to left, we can adapt this
algorithm to compute the suffix tree of the reversed
text
nav ) time.

 online in O(ntp

2
To get a suffix tree construction time of O n min lg lg n/ lg lg lg n, lg n/ lg lg n , we use the pre-

decessor data structure of Beame and Fich [2]. We create a predecessor
children 
 datastructure to store the
p
2
of each suffix tree node, such that we get the navigation time tnav = O min lg lg n/ lg lg lg n, lg n/ lg lg n
for both suffix trees. We also create a predecessor data structure to store the out-going suffix links of
each node of the suffix tree constructed by Weiner’s algorithm. Overall, these take a total of O(n) words

of space.
Finally, our last ingredient is a dynamic lowest common ancestor data structure with O(n) words
that performs querying and modification operations in constant time [6]. The lowest common ancestor
of two suffix tree leaves with the labels i and j is the node whose string depth is equal to the longest
common extension of T [i..] and T [j..], where T [i..] denotes the i-th suffix (up to the last position that is
available in the online setting). Building this data structure on the suffix tree of the text T and on the
suffix tree of the reversed text allows us to compute LCE queries in both directions in constant time.
We adapt the algorithm of Sec. 4 by switching the order of the loops (again). The algorithm first
fixes a Lempel-Ziv factor fx and then searches for squares with a period between one and |fx | + |fx+1 |.
Unfortunately, we would need an extra bit vector for each period so that we can track all found leftmost occurrences. Instead, we use the predecessor data structure of [2] storing the found occurrences
of squares as pairs of starting positions and lengths. These pairs can be stored in lexicographic or14

der (first sorted by starting position, then by length). The predecessor data structure will contain at
most
takes O(occ)
= O(n) words of space. An insertion and or a search costs us
 occ
 elements, hence p
O min lg2 lg n/ lg lg lg n, lg n/ lg lg n
time.

Let us assume that we have computed the set for T [1..i − 1], and that the Lempel-Ziv factorization of T [1..i − 1] is f1 · · · fy . If appending a new character T [i] will result in a new factor fy+1 , we

check for squares of type Lem. 4.2(a) and Lem. 4.2(b) at the borders of fy−1 . Duplicates are filtered
by the predecessor data structure storing all already reported leftmost occurrences. The algorithm
outputs only the leftmost occurrences with the aid of LPF, whose entries are fixed up to the last
two factors (this is sufficient since we search for the starting position of the leftmost occurrence of a
square
with type Lem.
|f1 · · · fy−1
|], including right-rotations). In overall, we need

 4.2(a) only in T [1..
p
time.
O (|fy−1 | + |fy |) min lg2 lg n/ lg lg lg n, lg n/ lg lg n
The current bottleneck of the online algorithm is the predecessor data structure in terms of the
running time. Future integer dictionary data structures can improve the overall performance of this
algorithm.

C

Algorithm Execution with one Step at a Time

In this section, we process the running example T = ababaaababa$ with the algorithm devised in Sec. 4
step by step. SA, LCP, PLCP, and LPF are given in the table below:

1

2

i

1

2

3

4

5

6

7

8

9

10 11 12

T

a

b

a

b

a

a

a

b

a

b

a

$

SA

12 11

5

6

9

3

7

1

10

4

8

2

LCP

0

0

1

2

1

3

3

5

0

2

2

4

PLCP 5

4

3

2

1

2

3

2

1

0

0

0

LPF

0

0

3

2

1

2

5

4

3

2

1

0

LZ

f1

f2

3

4

f3
5

f4

f5

f6

6

The text T = a—b—aba—aa—baba—$ = f1 · · · f6 is factorized in six Lempel-Ziv factors. We call
T [1 + |f1 · · · fi−1 |] (first position of the i-th factor) and T [1 + |f1 · · · fi |] (position after the i-th factor) the
left border and the right border of fi , respectively. The idea of the algorithm is to check the presence
of a square at a factor border and at an offset value q of the border with LCE queries. q is either the
addition of p to the left border, or the subtraction of p from the right border.
The algorithm finds the leftmost occurrences of all squares in the order (first) of their lengths and (second)
of their starting positions. We start with the period p = 1 and try to detect squares at each Lempel-Ziv
factor border. To this end, we create a bit vector B marking all found squares with period p. A square
of this period is found at the right border of f3 . It is of type Lem. 4.2(a), since its starting position is
in f3 . To find it, we take the right border b = 6 of f3 , and the position q := b − p = 5. We perform
an LCE query at b and q in the forward and backward direction. Only the forward query returns the
non-zero value of one. But this is sufficient to find the square aa of period one. Its LPF value is smaller
than 2p = 2, so it is the leftmost occurrence. It is not yet marked in B, thus we have not yet reported
it. Right-rotations are not necessary for period 1. Having found all squares with period 1, we clear B.
Next, we search for squares with period 2. We find a square of type Lem. 4.2(b) at the left border b = 2
of f2 . To this end, we perform an LCE query starting from b and q := b + p = 4 in both directions. Both
15

LCE queries show that T [1..5] is a repetition with period p = 2. Thus we know that T [1..4] is a square.
It is not yet marked in B, and has an LPF value smaller than 2p = 4, i.e., it is a not yet reported leftmost
occurrence. On finding a leftmost occurrence of a square, we right-rotate it, and report all right-rotations
whose LPF values are below 2p. This is the case for T [2..5], which is the leftmost occurrence of the square
baba.
After some unsuccessful checks at the next factor borders, we come to factor f5 and search for a
square of type Lem. 4.2(b). Two LCE queries in both directions at the left border b = 8 of f5 and
q := b + p = 10 reveal that T [7..11] is a repetition of period 2. The substring T [7..10] is a square, but its
LPF value is 5(≥ 2p), i.e., we have already reported this square. Although we have already reported it,
some right-rotation of it might not have been reported yet (see Appendix D for an example). This time,
all right-rotations (i.e., T [8..12]) have an LPF value ≥ 2p, i.e., there is no leftmost occurrence of a square
of period 2 found by right-rotations. In overall, we have found and reported the leftmost occurrences of
all squares once.

D

Need for RMQ on LPF

In Sec. 4, we perform the right-rotations of a square (s, 2p) with an RMQ on the interval I := [s +
1.. min(s + p − 1, e − 2p + 1)], where e is the last position of the maximal repetition of period p that
contains the square. Instead of an RMQ, we can linearly scan all LPF values in I, giving O(p) = O(n)
time. We cannot do better since the LPF values can be arbitrary. For instance, consider the text
T = abaaabaababaaabaaa$. The text aligned with LPF is shown in the table below.
i

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19

T

a

b

a

a

a

b

a

a

b

a

b

a

a

a

b

a

a

a

$

LPF

0

0

1

2

4

3

4

3

2

8

7

6

5

5

4

3

2

1

0

The square abaaabaa has two occurrences starting at the positions 1 and 10. The square baaabaaa at
position 11 is found by right-rotating the occurrence of abaaabaa at position 10. It is found by a linear
scan over LPF or an RMQ on LPF. A slight modification of this example can change the LPF values
around this occurrence. This shows that we cannot perform a shortcut in general (like stopping the
search when the LPF value is at least twice as large as p).

16

E

More Evaluation
collection

1MiB

10MiB

50MiB

100MiB

200MiB

pc-dblp.xml
pc-dna

0.2
0.3

3
3

16
23

33
56

70
310

pc-english
pc-proteins

0.2
0.3

5
4

42
25

500
74

2639
245

pc-sources
pcr-cere

0.2
0.6

3
6

31
30

286
79

792
535

pcr-einstein.en
pcr-kernel

0.4
0.2

12
8

83
233

1419
1274

3953
6608

pcr-para

0.4

4

26

98

265

Table 2: Running times in seconds, evaluated on different input sizes. We took prefixes of 1MiB, 10MiB,
and 100MiB of all collections.

F

Pseudo Code

17

Algorithm 1: Modified Algorithm 1 of [22]
1

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

29
30
31
32
33
34

35

b(f ) denotes the left end of a factor f = T [b(f )..b(f ) + |f | − 1], lcp and lcs compute the LCE in T
and the LCE in the reverse of T (mirroring the input indices by i 7→ n − i for 1 ≤ i ≤ n − 1),
respectively.
Let f1 , . . . , fz be the factors of the Lempel-Ziv factorization
fz+1 ← T [n]
// dummy factor
Function recursive-rotate(s : starting position, e: ending position)
m ← LPF.RMQ[s..e]
if m > 2p then return
report(m, 2p) and B[m] ← 1
recursive-rotate(s,m − 1) and recursive-rotate(m + 1,e)
Function right-rotate(s : starting position of square, p: period of square)
if B[s] = 1 then return
if LPF[s] < 2p then report(s, 2p) and B[s] ← 1
ℓ ← lcp(s, s + p)
recursive-rotate(s + 1, s + p − 1, s + ℓ − p)
Z ← array of size z lg z bits, zero initialized
m ← max(|f1 | + |f2 | , . . . , |fz−1 | + |fz |)
for p = 1, . . . , m do
B ← bit vector of length n, zero initialized
for x = 1, . . . , z do
if |fx | + |fx+1 | < p then
y←x
while |fy | + |fy+1 | < p do
if Z[y] 6= 0 then y ← Z[y]
else incr y
Z[x] ← y and x ← y
if |fx | ≥ p then // probe for squares satisfying Lem. 4.2(a)
q ← b(fx+1 ) − p
ℓR ← lcp(b(fx+1 ), q) and ℓL ← lcs(b(fx+1 ) − 1, q − 1)
if ℓR + ℓL ≥ p and ℓR > 0 then // found a square of length 2p with its right
end in fx+1
s ← max(q − ℓL , q − p + 1) // square starts at s
right-rotate(s, p)
q ← b(fx ) + p // probe for squares satisfying Lem. 4.2(b)
ℓR ← lcp(b(fx ), q) and ℓL ← lcs(b(fx ) − 1, q − 1)
s ← max(b(fx ) − ℓL , b(fx ) − p + 1) // square starts in a factor preceding fx
if ℓR + ℓL ≥ p and ℓR > 0 and s + p ≤ b(fx+1 ) and ℓL > 0 then // found a square of
length 2p whose center is in fx
right-rotate(s, p)

18

