# Substring Complexity in Sublinear Space

Giulia Bernardini  University of Milan - Bicocca, Italy and CWI, Amsterdam,
The Netherlands
<EMAIL_ADDRESS>Gabriele Fici  Dipartimento di Matematica e
Informatica, University of Palermo, Italy
<EMAIL_ADDRESS>Paweł Gawrychowski  Institute of Computer Science,
University of Wrocław, Poland
<EMAIL_ADDRESS>Solon P. Pissis  CWI and Vrije Universiteit, Amsterdam,
The Netherlands
<EMAIL_ADDRESS>
###### Abstract

Shannon’s entropy is a definitive lower bound for statistical compression.
Unfortunately, no such clear measure exists for the compressibility of
repetitive strings. Thus, ad-hoc measures are employed to estimate the
repetitiveness of strings, e.g., the size $z$ of the Lempel–Ziv parse or the
number $r$ of equal-letter runs of the Burrows-Wheeler transform. A more
recent one is the size $\gamma$ of a smallest string attractor. A string
attractor of a string $T$ is a set of positions of $T$ capturing the
occurrences of all the substrings of $T$. Unfortunately, Kempa and Prezza
[STOC 2018] showed that computing $\gamma$ is NP-hard. Kociumaka et al. [LATIN
2020] considered a new measure of compressibility that is based on the
function $S_{T}$ counting the cardinalities of the sets of substrings of each
length of $T$, also known as the substring complexity. This new measure is
defined as $\delta=\sup\\{S_{T}(k)/k,k\geq 1\\}$ and lower bounds all the
relevant ad-hoc measures previously considered. In particular,
$\delta\leq\gamma$ always holds and $\delta$ can be computed in
$\mathcal{O}(n)$ time using $\Omega(n)$ working space. Kociumaka et al. showed
that if $\delta$ is given, one can construct an
$\mathcal{O}(\delta\log\frac{n}{\delta})$-sized representation of $T$
supporting efficient direct access and efficient pattern matching queries on
$T$. Given that for highly compressible strings, $\delta$ is significantly
smaller than $n$, it is natural to pose the following question: _Can we
compute $\delta$ efficiently using sublinear working space?_

It is straightforward to show that any algorithm computing $\delta$ using
$\mathcal{O}(b)$ space requires $\Omega(n^{2-o(1)}/b)$ time through a
reduction from the element distinctness problem [Yao, SIAM J. Comput. 1994].
We thus wanted to investigate whether we can indeed match this lower bound. We
address this algorithmic challenge by showing:

  * •

An $\mathcal{O}(n^{3}/b^{2})$-time and $\mathcal{O}(b)$-space algorithm to
compute $\delta$, for any $b\in[1,n]$.

  * •

An $\tilde{\mathcal{O}}(n^{2}/b)$-time111The $\tilde{\mathcal{O}}(f)$ notation
denotes $\mathcal{O}(f\cdot\text{polylog}(f))$. and $\mathcal{O}(b)$-space
algorithm to compute $\delta$, for any $b\in[n^{2/3},n]$. This gives an
$\tilde{\mathcal{O}}(n^{1+\epsilon})$-time and
$\mathcal{O}(n^{1-\epsilon})$-space algorithm to compute $\delta$, for any
$0<\epsilon\leq 1/3$.

Our algorithms in fact compute $S_{T}(k)$ for all $k$, within the same
complexities, which may be of independent interest.

##  1 Introduction

We are currently witnessing our world drowning in data. These datasets are
generated by a large gamut of applications, namely databases, web
applications, genome sequencing projects, scientific computations, sensors,
e-mail, entertainment and others. The biggest challenge for academia and the
industry is thus to develop theoretical and practical methods for processing
datasets efficiently.

Compressed data representations that can be directly used in compressed form
have a central role in this challenge [54]. Indeed, much of the currently
fastest-growing data is highly repetitive; this in turn enables space
reductions of orders of magnitude [29]. Prominent examples of such data
include genome, versioned text and software repositories collections. A common
characteristic is that each element in a collection is very similar to every
other element in the same collection.

Since a significant amount of this data is sequential, a considerable amount
of algorithmic research has been devoted to text indexes over the past decades
[61, 52, 24, 39, 25, 36, 38, 5, 19, 53, 41, 29]. String processing
applications (see [37, 1] for comprehensive reviews) require fast access to
the substrings of the input string. These applications rely on such text
indexes, which typically arrange the string suffixes lexicographically in an
ordered tree [61] or in an ordered array [52].

This significant amount of research has resulted in compressed text indexes
which support fast pattern searching functionality in space close the the
statistical entropy of the text collection. The problem, however, is that this
kind of entropy is unable to capture repetitiveness [48, 51]. In order to
achieve orders-of-magnitude space reductions, one thus needs to resort to
other compression methods, such as Lempel-Ziv (LZ) [64], grammar compression
[43] or run-length compressed Burrows-Wheeler transform (BWT) [29], to name a
few; see [29] for a comprehensive review.

Unlike Shannon’s entropy, which is a definitive lower bound for statistical
compression, no such clear measure exists for the compressibility of
repetitive text, unfortunately. Other than Kolmogorov’s complexity [46], which
is not computable, repetitiveness can be measured in ad-hoc terms, which are
based on what the underlying compressors may achieve. A list of such measures
on a string $T$ include: the number $z$ of phrases produced by the LZ parsing
of $T$; the size $g$ of the smallest grammar generating $T$; and the number
$r$ of maximal equal-letter runs in the BWT of $T$.

An improvement to this situation is the recent introduction of the concept of
string attractor [42]. An attractor $\Gamma$ is a set of positions over
$[1,n]$ such that any substring of $T$ has an occurrence covering a position
in $\Gamma$. The size $\gamma$ of a smallest attractor asymptotically lower
bounds all the repetitiveness measures listed above, and others (see [44] for
a comprehensive list). Unfortunately, using indexes based on $\gamma$ comes
also with some challenges. Other the fact that computing $\gamma$ is NP-hard
[42], it is not clear whether $\gamma$ is the definitive measure of
repetitiveness. In particular, we do not know whether one can always represent
$T$ in $\mathcal{O}(\gamma)$ space (machine words). This motivated
Christiansen et al. to consider a new measure $\delta$ of compressibility,
initially introduced in the area of string compression by Raskhodnikova et al.
[58], and for which $\delta\leq\gamma$ always holds [14].

######  Definition 1 ([14]).

Let $T$ be a string and $S_{T}(k)$ its substring complexity, i.e., the
function that counts the number of distinct substrings of length $k$ of $T$,
for each $k$. The normalized substring complexity of $T$ is the function
$S_{T}(k)/k$ and we set $\delta=\sup\\{S_{T}(k)/k,k\geq 1\\}$ its supremum.

Christiansen et al. also showed that $\delta$ can be computed in
$\mathcal{O}(n)$ time using $\Omega(n)$ working space. Very recently,
Kociumaka et al. showed that $\delta$ can also be asymptotically strictly
smaller than $\gamma$: for every length $n$ and every value $\delta\geq 2$,
there exists a string with $\gamma=\Omega(\delta\log\frac{n}{\delta})$ [44].
Moreover, Kociumaka et al. developed a representation of $T$ of size
$\mathcal{O}(\delta\log\frac{n}{\delta})$, which is worst-case optimal in
terms of $\delta$ and allows for accessing any $T[i]$ in time
$\mathcal{O}(\log\frac{n}{\delta})$ per $i$ and for finding all occ
occurrences of any pattern $P[1\mathinner{.\,.}m]$ in $T$ in time
$\mathcal{O}(m\log n+\textit{occ}\cdot\log^{\epsilon}n)$, for any constant
$\epsilon>0$. However, $\delta$ must be known to construct this
representation. Given that for highly compressible strings, $\delta$ is
significantly smaller than $n$, it is natural to pose the following question:

Can we compute $\delta$ efficiently using sublinear working space?

#### Related Work.

The standard approach for showing space-time trade-off lower bounds for
problems answered in polynomial time has been to analyze their complexity on
(multi-way) branching programs. In this model, the input is stored in read-
only memory, the output in write-only memory, and neither is counted towards
the space used by any algorithm. This model is powerful enough to simulate
both Turing machines and standard RAM models that are unit-cost with respect
to time and log-cost with respect to space. It was introduced by Borodin and
Cook, who used it to prove that any multi-way branching program requires a
time-space product of $\Omega(n^{2}/\log n)$ to sort $n$ integers in the range
$[1,n^{2}]$ [7] (see also [3]). Unfortunately, the techniques by Borodin and
Cook [7] yield only trivial bounds for problems with single outputs.

String algorithms that use sublinear space have been extensively studied over
the past decades [30, 21, 56, 9, 60, 8, 45, 15, 27, 16, 18, 35, 34, 33, 32,
17, 31, 2, 55, 12, 57, 47]. The perhaps most relevant problem to our work is
the classic longest common substring of two strings. Formally, given two
strings $X$ and $Y$ of total length $n$, the _longest common substring_ (LCS)
problem consists in computing a longest string occurring as a substring of
both $X$ and $Y$. The LCS problem was conjectured by Knuth to require
$\Omega(n\log n)$ time. This conjecture was disproved by Weiner who, in his
seminal paper on suffix tree construction [61], showed how to solve the LCS
problem in $\mathcal{O}(n)$ time for constant-sized alphabets. Farach showed
that the same problem can be solved in the optimal $\mathcal{O}(n)$ time for
polynomially-sized alphabets [24]. A straightforward space-time trade-off
lower bound of $\mathcal{O}(b)$ space and $\mathcal{O}(n^{2}/b)$ time for the
LCS problem can be derived from the problem of checking whether the length of
an LCS is $0$ or not; i.e., deciding if $X$ and $Y$ have a common letter or
not. Thus, in some sense, the LCS problem can be seen as a generalization of
the element distinctness problem: given $n$ elements over a domain $D$, decide
whether all $n$ elements are distinct.

On the upper bound side, Starikovskaya and Vildhøj showed that for any
$b\in[n^{2/3},n]$, the LCS problem can be solved in
$\tilde{\mathcal{O}}(n^{2}/b)$ time and $\mathcal{O}(b)$ space [60]. In [45],
Kociumaka et al. gave an $\mathcal{O}(n^{2}/b)$-time algorithm to find an LCS
for any $b\in[1,n]$. Kociumaka et al. additionally provided a lower bound for
the LCS problem, which states that any deterministic multi-way branching
program that uses $b\leq\frac{n}{\log n}$ space must take
$\Omega(n\sqrt{\log(n/(b\log n))/\log\log(n/(b\log n))})$ time. This lower
bound implies that the classic linear-time solution for this problem [61, 24]
is optimal in the sense that we cannot hope for an $\mathcal{O}(n)$-time
algorithm using $o(n/\log n)$ space. Unfortunately, however, we do not know if
the $\mathcal{O}(b)$-space and $\mathcal{O}(n^{2}/b)$-time trade-off is
generally the best possible for the LCS problem. For instance, for the element
distinctness problem, Beame et al. showed that there exists a
$\tilde{\mathcal{O}}(n^{3/2}/\sqrt{b})$-time algorithm [4]. It is thus a big
open problem to answer whether the LCS problem can be solved asymptotically
faster than $\mathcal{O}(n^{2}/b)$ using $\mathcal{O}(b)$ space. Towards this
direction, very recently, Ben-Nun et al. exploited the intuition suggesting
that an LCS of $X$ and $Y$ can be computed more efficiently when its length
$L$ is large [55] (see also [13]). The authors showed an algorithm which runs
in $\tilde{\mathcal{O}}(\frac{n^{2}}{L\cdot b}+n)$ time, for any $b\in[1,n]$,
using $\mathcal{O}(b)$ space. Still, a straightforward lower bound for the
aforementioned problem is in $\Omega(\frac{n^{2}}{L^{2}\cdot b}+n)$ time when
$\mathcal{O}(b)$ space is used; it seems that further insight is required to
match this space-time trade-off lower bound.

#### Our Results and Techniques.

Our goal is to efficiently compute $\delta$ using $\mathcal{O}(b)$ space. As a
preliminary step towards this algorithmic challenge, we show the following
theorem.

######  Theorem 1.

Given a string $T$ of length $n$, we can compute
$\delta=\sup\\{S_{T}(k)/k,k\geq 1\\}$ in $\mathcal{O}(n^{3}/b^{2})$ time using
$\mathcal{O}(b)$ space, for any $b\in[1,n]$.

It is straightforward to show that any comparison-based branching program to
compute $\delta$ using $\mathcal{O}(b)$ space requires $\Omega(n^{2-o(1)}/b)$
time through a reduction from the element distinctness problem [63]. By Yao’s
lemma, this lower bound also applies to randomized branching programs [63].
This suggests that a natural intermediate step towards fully understanding the
computation complexity of computing $\delta$ in small space should be
designing an $\tilde{\mathcal{O}}(n^{2}/b)$-time algorithm using
$\mathcal{O}(b)$ space (not necessarily comparison-based).

The natural approach for computing $\delta$ is through computing all values of
$S_{T}(k)$. It is unclear to us if a more direct approach exists, in
particular this is the idea behind the $\mathcal{O}(n)$-time computation of
$\delta$ using $\Omega(n)$ space [14]. Under this plausible assumption,
computing $S_{T}(k)$, for all $k$ one-by-one, is a more general problem than
computing the length $L$ of an LCS of $X$ and $Y$, as an algorithm computing
$S_{T}(k)$ can be used to compute $L$ within the same complexities. This
follows by the following argument: we compute $S_{X}(k)$, $S_{Y}(k)$, and
$S_{X\\#Y}(k)$ (where $\\#$ is a special letter that does not occur in $X$ or
in $Y$) in parallel, and set $L$ equal to the largest $k$ such that
$S_{X}(k)+S_{Y}(k)>S_{X\\#Y}(k)-k$. As the best known time upper bound for the
very basic question of computing LCS in $\mathcal{O}(b)$ space remains to be
$\mathcal{O}(n^{2}/b)$, this further motivates the algorithmic challenge of
designing an algorithm with such bounds for computing $\delta$. We address it
by proving the following theorem.

######  Theorem 2.

Given a string $T$ of length $n$, we can compute
$\delta=\sup\\{S_{T}(k)/k,k\geq 1\\}$ in $\tilde{\mathcal{O}}(n^{2}/b)$ time
using $\mathcal{O}(b)$ space, for any $b\in[n^{2/3},n]$.

Our algorithms compute $S_{T}(k)$, for all $k$, within the same complexities.
To arrive at Theorem 1, we split the computation of the values $S_{T}(k)$ in
$n/b$ phases: in each phase, we restrict to substrings whose length is in a
range of size $b$. In turn, in each phase we process the substrings that start
within a range of $b$ positions of $T$ at a time, proceeding from left to
right. With this scheme, we process in $\mathcal{O}(n)$ time each of the $n/b$
blocks of positions of $T$ in each of the $n/b$ phases, obtaining a time
complexity of $\mathcal{O}(n^{3}/b^{2})$. For sufficiently large values of
$b$, we are able to process all of the substrings of a single phase at once
rather than process the positions of $T$ in batches, saving a factor of $n/b$.
This is made possible by showing that a representation of all the occurrences
of all the substrings of a phase can be packed in $\mathcal{O}(b)$ space if
$b$ is large enough and by carefully processing such occurrences in different
ways depending on their period. Note that Theorem 2 in particular implies an
$\tilde{\mathcal{O}}(n^{1+\epsilon})$-time and
$\mathcal{O}(n^{1-\epsilon})$-space algorithm to compute $\delta$, for any
$0<\epsilon\leq 1/3$.

#### Substring Complexity from the Combinatorial Point of View.

The knowledge of the whole substring complexity of a string can also be used
to find other regularities. To mention a few, we have the following
straightforward implications in sublinear working space:

  * •

$T$ has a substring of length $k$ repeating in $T$ if and only if
$S_{T}(k)<n-k+1$. This yields, for instance, the length $r$ of the longest
repeated substring of $T$ (also known as the repetition index of $T$) [61]. It
is worth noticing that $S_{T}(k+1)=S_{T}(k)-1$ for every $k>r$ [22] and that
$r$ tends to $\log_{|\Sigma|}n$ as $n$ tends to infinity under a Bernoulli
i.i.d. model [26].

  * •

A string $S$ is called a minimal absent word of $T$ if $S$ does not occur in
$T$ but all proper substrings of $S$ occur in $T$. The length $\ell$ of a
longest minimal absent word of $T$ is equal to $2+r$ [26]. This quantity is
important because if two strings $X$ and $Y$ have the same set of distinct
substrings up to length $\ell$, then $X=Y$ [26, 11]. Moreover, the length of a
shortest absent word [62] of $T$ over alphabet $\Sigma$ is equal to the
smallest $k$ such that $S_{T}(k)<|\Sigma|^{k}$.

The substring complexity function is well studied in the area of combinatorics
on words, both for finite and infinite strings. However, the normalization
$S(k)/k$ and its supremum $\delta$ have not been considered until very
recently. In [22] it is proved that the substring complexity $S_{T}(k)$ of a
string $T$ takes its maximum precisely for those values of $k$ in the interval
$[L,K]$ where $L$ (resp. $R$) is the minimum length for which no substring of
$T$ has occurrences preceded (resp. followed) by two different letters, and
one has $\sup\\{S_{T}(k),k\geq 1\\}=n+1-\max\\{L,H\\}=n+1-\max\\{R,K\\}$,
where $H$ (resp. $K$) is the length of the shortest unrepeated prefix (resp.
suffix) of $T$. But this seems to be of little help in understanding the
behaviour of the normalized substring complexity $S_{T}(k)/k$.

######  Example 1.

Let $1$, $0$, $01$, $010$, $01001$, etc. be the Fibonacci strings. For every
such string one has $S(k)/k\leq(k+1)/k\leq 2$ for every $k$, so that
$\delta=2$ for every Fibonacci string of length at least $2$.

######  Example 2 (see also [49]).

Let $0$, $01$, $0110$, $01101001$, etc. be the Thue-Morse strings (each string
in the sequence is obtained by concatenating the previous string with its
binary complement). The Thue-Morse strings are the prefixes of length a power
of $2$ of the infinite222The infinite Thue-Morse string can be defined in
several equivalent ways. One is the following: the letter in position $n$ is
the parity of $1$s in the binary expansion of the number $n$. The Fibonacci
and Thue-Morse strings are the most prominent examples of strings in several
contexts because they have a lot of combinatorial properties; see [50]. Thue-
Morse string TM.

Brlek [10] gave a formula for the substring complexity of the infinite Thue-
Morse string: $S_{\textsc{TM}}(1)=2$, $S_{\textsc{TM}}(2)=4$ and for $k\geq
3$, let $k=2^{r}+q+1$, $r\geq 0$, $0\leq q<2^{r}$; then:

$S_{\textsc{TM}}(k)=\begin{cases}6\cdot 2^{r-1}+4q\ \ \ \mbox{ if\ \ $0\leq
q\leq 2^{r-1}$};\\\ 2^{r+2}+2q\ \ \ \ \ \ \mbox{ if\ \
$2^{r-1}<q<2^{r}$}.\end{cases}$

From this formula, one easily derives that the function $S_{\textsc{TM}}(k)/k$
has a local maximum when $q=2^{r-1}$, i.e., for each $k$ of the form
$2^{r}+2^{r-1}+1$. For these values, the formula gives
$S_{\textsc{TM}}(k)/k=\dfrac{2^{r+2}+2^{r}}{2^{r}+2^{r-1}+1}$ and this is
precisely the supremum of the normalized substring complexity, i.e., the
$\delta$, of the Thue-Morse string of length $2^{r+3}$, $r\geq 0$. Since these
values form an increasing subsequence, one has that for the infinite Thue-
Morse string,
$\delta=\lim_{r\to\infty}\dfrac{2^{r+2}+2^{r}}{2^{r}+2^{r-1}+1}=10/3$ and this
value is therefore reached only asymptotically.

#### Paper Organization.

Section 2 introduces the basic definitions and notation used throughout. In
Section 3, we provide the space-time trade-off lower bound for computing
$\delta$. In Section 4, we present a simple $\mathcal{O}(n^{3}/b)$-time and
$\mathcal{O}(b)$-space algorithm, for any $b\in[1,n]$. This algorithm is
refined to run in $\mathcal{O}(n^{3}/b^{2})$ time using $\mathcal{O}(b)$
space, for any $b\in[1,n]$, in Section 5. Our main result, the
$\tilde{\mathcal{O}}(n^{2}/b)$-time and $\mathcal{O}(b)$-space algorithm, for
any $b\in[n^{2/3},n]$, is presented in Section 6.

##  2 Definitions and Notation

An alphabet $\Sigma$ is a finite set of elements called letters. We fix
throughout a string $T=T[1]T[2]\ldots T[n]$ of length $|T|=n$ over alphabet
$\Sigma=\\{1,\ldots,n^{\mathcal{O}(1)}\\}$. By $\Sigma^{*}$ we denote the set
of all strings over $\Sigma$, and by $\Sigma^{k}$ the set of all length-$k$
strings over $\Sigma$. By $\varepsilon$ we denote the _empty string_ of length
$0$. For two indices $1\leq i\leq j\leq n$, the substring
$T[i\mathinner{.\,.}j]=T[i]\ldots T[j]$ of $T$ that starts at position $i$ and
ends at position $j$ is called the _$(i,j)$ -fragment_ of $T$. A _prefix_ of
$T$ is a substring of the form $T[1\mathinner{.\,.}j]$, and a _suffix_ of $T$
is a substring of the form $T[i\mathinner{.\,.}n]$. A prefix (resp. suffix) of
a string is _proper_ if it is not equal to the string itself.

A positive integer $p$ is _a period_ of a string $T$ if $T[i]=T[j]$ whenever
$i=j\mod p$; we call _the period_ of $T$, $\textsf{per}(T)$, the smallest such
$p$. A string $T$ is said to be periodic if $\textsf{per}(T)\leq|T|/2$, and it
is called _a power_ if $|T|/\textsf{per}(T)$ is an integer greater than one.
We call the lexicographically smallest cyclic shift of
$T[1\mathinner{.\,.}\textsf{per}(T)]$ the _(Lyndon) root_ of $T$. Notice that
if $T$ is periodic, then the root of $T$ is always a fragment of $T$ (that is,
it occurs in $T$).

A _run_ with (Lyndon) root $t$ in a string $T$ is a periodic fragment
$T[i\mathinner{.\,.}j]=t[q\mathinner{.\,.}|t|]t^{\beta}t[1\mathinner{.\,.}\gamma]$,
with $q,\gamma\in[1,|t|]$ and $\beta$ a positive integer, such that both
$T[i-1\mathinner{.\,.}j]$ and $T[i\mathinner{.\,.}j+1]$, if defined, have the
smallest period larger than $|t|$; we say that $q\in[1,|t|]$ is the _offset_
of the run, and that two runs with the same root are _synchronized_ if they
have the same offset. We represent a run by means of its starting and ending
positions in $T$, its root and its offset.

We also fix a constant $c\geq 1$, a prime number
$p>\max\\{|\Sigma|,n^{c+4}\\}$, and choose $x\in\mathbb{Z}_{p}$ uniformly at
random. We define the _fingerprint_ of a substring $T[i\mathinner{.\,.}j]$ of
$T$ as $\Phi(T[i\mathinner{.\,.}j])=(T[i]+T[i+1]x+\ldots+T[j]x^{j-i})\bmod p$
(cf. [27, 40]). With probability at least $1-\frac{1}{n^{c}}$, no two
substrings of the same length have the same fingerprint.

##  3 A Space-Time Trade-Off Lower Bound

The element distinctness problem is the problem of determining whether all the
elements of an array $A$ of size $n$ are pairwise distinct. Yao showed that,
in the comparison-based branching program model, the time required to solve
the element distinctness problem using $\mathcal{O}(b)$ space is in
$\Omega(n^{2-o(1)}/b)$ [63]. We show the following lower bound for computing
$\delta$ in the same model.

######  Theorem 3.

The time required to compute $\delta$ for a string $T$ of length $n$ using
$\mathcal{O}(b)$ space is in $\Omega(n^{2-o(1)}/b)$.

###### Proof.

We reduce the element distinctness problem to computing $\delta$ in
$\mathcal{O}(n)$ time as follows.

Let $A$ be the input array for the element distinctness problem. Then set

$T=A\cdot\\#_{1}\\#_{2}\ldots\\#_{n},$

with $|T|=2n$ and $\\#_{i}\neq A[j]$, for all $i,j=1,\ldots n$. Observe that
$S_{T}(k)/k\leq n$, for all $k\geq 2$, and thus $\delta=S_{T}(1)=n+|\\{A\\}|$.
Then $A$ has a repeating element if and only if $\delta<2n$. ∎

##  4 $\mathcal{O}(n^{3}/b)$ Time Using $\mathcal{O}(b)$ Space

Let us start with a warm-up lemma.

######  Lemma 1.

$\delta$ can be computed in $\mathcal{O}(n^{3})$ time using $\mathcal{O}(1)$
space.

###### Proof.

Let us consider each $S_{T}(k)$ separately, for all $k\in[1,n]$.

Set $S_{T}(k)=0$. For all $i\in[1,n]$, we increase $S_{T}(k)$ if
$T[i\mathinner{.\,.}i+k-1]$ is the first occurrence in
$T[1\mathinner{.\,.}i+k-1]$. To perform this we check whether
$T[j\mathinner{.\,.}j+k-1]=T[i\mathinner{.\,.}i+k-1]$, for all $j\in[1,i-1]$.
We employ any linear-time constant-space pattern matching algorithm [30, 21,
9] to do this check in $\mathcal{O}(n)$ time using $\mathcal{O}(1)$ space for
a single $i$. The statement follows. ∎

In this section we generalize Lemma 1. The following straightforward
observation will be used by our algorithm.

######  Observation 1.

Let $S$ be a substring of $T$. If $S$ occurs at least twice in $T$, then every
substring of $S$ occurs at least twice in $T$; if $S$ occurs only once in $T$,
then any substring of $T$ containing $S$ as a substring occurs only once in
$T$.

#### Main Idea.

Recall that we have $\mathcal{O}(b)$ budget for space. At any phase of the
algorithm, we maintain $b$ $S_{T}(k)$ values and iterate on non-overlapping
substrings of $T$ of length $b$, which we call blocks. This gives $n/b$ phases
and $n/b$ iterations per phase, respectively. For each iteration we define a
substring $M$ of $T$, which we call anchor. The combination of a $k$ value and
a block implies a specific anchor $M$ on $T$. We search for occurrences of
this anchor in $T$ and extend each of the (at most) $n$ occurrences of $M$ in
$\mathcal{O}(b)$ time per occurrence. This gives $\mathcal{O}(n^{3}/b)$ time
and $\mathcal{O}(b)$ space.

######  Proposition 4.

$\delta$ can be computed in $\mathcal{O}(n^{3}/b)$ time using $\mathcal{O}(b)$
space for any $b\in[1,n]$.

###### Proof.

We start by decomposing $T$ into $n/b$ blocks $B_{1},B_{2},\ldots,B_{n/b}$,
each of length $b$. Our algorithm consists of $n/b$ phases. In phase $\alpha$,
for all $\alpha\in[0,1,\ldots,n/b-1]$, we compute altogether the $b$ values of
$S_{T}(k)$, for all $k\in[\alpha b+1,(\alpha+1)b]$. Let
$\mathcal{S}=\mathcal{S}[1\mathinner{.\,.}b]$ be an array of size $b$ where we
store the values of $S_{T}(k)$ corresponding to phase $\alpha$:
$\mathcal{S}[h]=S_{T}(\alpha b+h)$, for $h\in[1,b]$. At the end of phase
$\alpha$ we maintain the maximum of $\mathcal{S}[h]/(\alpha b+h)$. Clearly, at
the end of the whole procedure we can output
$\delta=\sup\\{S_{T}(k)/k~{}|~{}k\geq 1\\}$.

In what follows we describe the workings of our algorithm for a fixed phase
$\alpha$. First we set $\mathcal{S}[h]=0$, for all $h\in[1,b]$. Let $i$ be a
position on $T$. For each $k$ in the range of $\alpha$, we want to know if the
$(i,i+k-1)$-fragment of $T$ has its first occurrence in $T$ at position $i$ or
if it occurs in $T$ also at some position smaller than $i$.

We process together positions $i$ in the same block
$B_{j}=T[(j-1)b+1\mathinner{.\,.}jb]$, for every $j\in[1,n/b]$. Let $L=B_{j}$
be the block we are currently processing (inspect also Figure 1 for the
setting of our algorithm). To compute $S_{T}(k)$, we consider all of the
length-$k$ fragments with starting position $i$ in $L$, for all $k\in[\alpha
b+1,(\alpha+1)b]$. All such fragments share the same _anchor_
$M=T[jb+1\mathinner{.\,.}(j+\alpha-1)b]$ and end at position $i+k-1$, which
belongs to one of the two blocks succeeding $M$; we denote the concatenation
of these two succeeding blocks as fragment $R$. In particular, we have
$|M|=(\alpha-1)b$ and $R=B_{j+\alpha}B_{j+\alpha+1}$.

Figure 1: The main setting of our algorithm.

We will use the occurrences of $M$ in $T$ that start before its starting
position $bj+1$ as anchors for finding possible occurrences of the length-$k$
fragments starting within $L$. We search for such occurrences of $M$ with any
linear-time constant-space pattern matching algorithm [30, 21, 9]. For each
such occurrence of $M$ we then need to check the $b$ letters preceding it and
the $2b-1$ letters following it in order to determine whether it generates a
previous occurrence of some length-$k$ substring with starting position within
the block $L$: the $b$ letters preceding it because the starting position of
its other occurrence must be within block $L$; and the $2b-1$ letters
following it because $k\leq(\alpha+1)b$.

While processing $L=B_{j}=T[(j-1)b+1\mathinner{.\,.}jb]$, we also maintain an
array $\textsf{END}_{L}[1\mathinner{.\,.}b]$ of size $b$. After we have
finished processing $L$, $\textsf{END}_{L}[i]$ will store the length $r_{i}$
of the longest prefix of $R$ such that
$T[(j-1)b+i\mathinner{.\,.}(j-1)b+i+|M|+r_{i}-1]$ occurs in $T$ before
position $(j-1)b+i$ (inspect Figure 2). We compute $\textsf{END}_{L}$ as
follows. We search for all the occurrences of $M$ in
$T[1\mathinner{.\,.}(j+\alpha-1)b-1]$, from left to right. Let
$M=T[i^{\prime}\mathinner{.\,.}i^{\prime}+|M|-1]$ be one such occurrence. Let
$\ell$ be the length of the longest common suffix of $L$ and
$T[1\mathinner{.\,.}i^{\prime}-1]$; let $r$ be the length of the longest
common prefix of $R$ and $T[i^{\prime}+|M|\mathinner{.\,.}n]$. For each $i\geq
b-\ell+1$, we update $\textsf{END}_{L}[i]$ with the maximum between its
previous value $\textsf{END}_{L}[i]$ and $r$ (note that we do not update any
values if $\ell=0$). After we have processed all the found occurrences of $M$,
for each $i$ we increase by $1$ all $S_{T}(k)$ such that
$k>b-i+|M|+\textsf{END}_{L}[i]=b-i+(\alpha-1)b+\textsf{END}_{L}[i]=\alpha
b-i+\textsf{END}_{L}[i]$. This is an application of Observation 1: all these
occurrences correspond to a substring that is longer than a substring that
occurs for the first time in $T$ at position $i$.

The above procedure takes time $\mathcal{O}(\frac{n^{3}}{b})$. Indeed, there
are $\frac{n}{b}$ phases; in each phase, we consider $\frac{n}{b}$ blocks of
positions and for each block we spend $\mathcal{O}(n)$ time for pattern
matching anchor $M$; for each occurrence of the anchor, we spend
$\mathcal{O}(b)$ time for finding and updating the possible extensions, that
gives $\mathcal{O}(nb)$ time overall. We finally need $\mathcal{O}(b^{2})$
time for updating the values of $S_{T}(k)$ for all $k$’s in the range and all
positions $i$ in $L$. We thus have time
$\mathcal{O}(\frac{n}{b}\cdot\frac{n}{b}\cdot(nb+b^{2}))=\mathcal{O}(\frac{n^{3}}{b})$
overall. ∎

Figure 2: Largest $r_{i}$ such that
$U=T[(j-1)b+i\mathinner{.\,.}(j-1)b+i+|M|+r_{i}-1]$.

##  5 $\mathcal{O}(n^{3}/b^{2})$ Time Using $\mathcal{O}(b)$ Space

#### Main Idea.

In our previous solution (Proposition 4), we spent $\mathcal{O}(nb+b^{2})$
time to process the at most $n$ occurrences of a single anchor $M$ in $T$.
Here, we show that all of these occurrences can in fact be processed in
$\mathcal{O}(n)$ time. This is made possible by processing together batches of
occurrences of $M$ that are close enough in $T$. This is done by means of
answering longest common extension queries on suffix trees constructed for
certain length-$\mathcal{O}(b)$ fragments of $T$. We first provide a solution
for when $T\in\Sigma^{n}$ and $|\Sigma|=\mathcal{O}(1)$ and then generalize
our solution to large alphabets.

#### The Algorithm.

The first trick is based on the following remark: The linear-time constant-
space pattern matching algorithm (e.g., [9]) for reporting the occurrences of
$M$ reports the occurrences of $M$ in real time from left to right. Every such
occurrence $m$ of $M$ implies a block $L^{\prime}$ of length $b$ on the left
of $m$ starting at position $m-b$ and ending at position $m-1$, and a fragment
$R^{\prime}$ of length $2b$ starting at position $m+|M|$ and ending at
position $m+|M|+2b-1$. We thus need to find the longest common prefix of $R$
and $R^{\prime}$ and the longest common suffix of $L$ and $L^{\prime}$.

Let us describe the process for the longest common prefix of $R$ and
$R^{\prime}$. (The procedure for the longest common suffix of $L$ and
$L^{\prime}$ is analogous and is executed simultaneously.) We use the so-
called standard trick to construct a sequence of $n/(4b)$ suffix trees for
fragments of $T$ of length $4b$ overlapping by $2b$ positions. In fact, we
first concatenate each such fragment of length $4b$ with $R$. Constructing one
such suffix tree for a constant-sized alphabet can be done in $\mathcal{O}(b)$
time and space [24]. Recall that an occurrence $m$ of $M$ implies an
occurrence of $R^{\prime}$ at position $m+|M|$ and thus this position is part
of some fragment of length $4b$. We pre-process the $\mathcal{O}(b)$-sized
suffix tree in $\mathcal{O}(b)$ time and space to answer longest common prefix
queries in $\mathcal{O}(1)$ time per query [6]. The whole pre-processing can
thus be done in $n/(4b)\mathcal{O}(b)=\mathcal{O}(n)$ time. Thus, for any
occurrence $m$ of $M$ we can find the longest right extension (and the longest
left extension with a similar procedure) in $\mathcal{O}(1)$ time; recall that
each extension cannot be of length greater than $2b$ so we do not miss any of
them. To memorize the extensions we use an array $\textsf{END}_{L}$ of size
$b$. In particular, for each occurrence of $M$, if we have a non-empty left
extension of length $\ell$ and a right extension of length $r$, we set
$\textsf{END}_{L}[b-\ell]=\max\\{\textsf{END}_{L}[b-\ell+1],r\\}$ in
$\mathcal{O}(1)$ time. At the end of this process we sweep through
$\textsf{END}_{L}$ and set
$\textsf{END}_{L}[i]=\max\\{\textsf{END}_{L}[i-1],\textsf{END}_{L}[i]\\}$, for
all $i\in[2,b]$. This is merely an application of Observation 1: if we can
extend a position $i$ in $L$ $r$ positions on the right of $M$, then we must
be able to extend position $i+1$ in $L$ at least $r$ positions on the right of
$M$.

The second trick is needed to update all values of $S_{T}(k)$ using array
$\textsf{END}_{L}$ in $\mathcal{O}(b)$ time instead of $\mathcal{O}(b^{2})$
time. Let us define an auxiliary array $I=I[1\mathinner{.\,.}b]$ of size $b$
and initialize all of its entries to $0$; $I[h]$ will store the number of
indices $i$ in $L$ such that the shortest unique substring starting at
position $i$ is of length $\alpha b+h$. We fill in $I$ scanning
$\textsf{END}_{L}$: the shortest unique substring starting at position $i$ is
by definition of length $\alpha b-i+\textsf{END}_{L}[i]+1$, which is equal to
$\alpha b+h$ when $h=\textsf{END}_{L}[i]-i+1$. We thus increment $I[h]$ by
one. We finally increase the value of $S_{T}(\alpha b+h)$ by
$\sum_{j=1}^{h}I[j]$ for all $h=1,\ldots,b$. Thus, updating all values of
$S_{T}(k)$ is implemented in $\mathcal{O}(b)$ time.

#### Large Alphabets.

We now provide a solution when $T$ is over
$\Sigma=\\{1,\ldots,n^{\mathcal{O}(1)}\\}$. In the above algorithm we have
used the constant-sized alphabet assumption only to make sure that suffix
trees can be efficiently constructed. If the alphabet is not constant, a
suffix tree of a string can be constructed in linear time in addition to the
time required for sorting its letters [24].

Consider the case when we concatenate a fragment $F$ of length $4b$ of $T$
with fragment $R$ of length $2b$. (The procedure for $L$ is analogous.) We
consider two cases: If $b>\sqrt{n}$, we sort the letters of $R$ and $F$ in
$\mathcal{O}(b)$ time per fragment using radix sort because $n$ is polynomial
in $b$ and $|\Sigma|$ is polynomial in $n$; then, we can merge the two sorted
lists and replace the letters in $F$ and $R$ by their ranks in
$\mathcal{O}(b)$ time. Otherwise, if $b\leq\sqrt{n}$, we construct a
deterministic static dictionary for the letters of $R$ in
$\mathcal{O}(b\log^{2}\log b)$ time [59]. With each key, we associate a unique
rank from $\\{1,\ldots,2b\\}$. This dictionary uses $\mathcal{O}(b)$ space and
answers look-up queries in $\mathcal{O}(1)$ time per query. When processing a
fragment $F$ of $T$, we look up its letters using the dictionary. If a letter
is in the dictionary, we replace it in $F$ by its rank value; otherwise, we
replace it by rank $2b+1$. We can now construct the suffix tree in
$\mathcal{O}(b)$ time using $\mathcal{O}(b)$ space [24]. It should be clear
that the same bounds can be achieved for any integer alphabet using a simpler
method in which we replace the deterministic dictionary with a randomized
static dictionary such as [28]. We arrive at Theorem 1.

See 1

##  6 $\tilde{\mathcal{O}}(\frac{n^{2}}{b}$) Time Using $\mathcal{O}(b)$ Space
for $b\geq n^{2/3}$

Let $b\geq n^{2/3}$ and $c$ be any positive constant. We will process the
values of $S_{T}(k)$ for $k\leq cb$ (Section 6.1) and for $k>cb$ (Section 6.2)
in two different ways.

###  6.1 Computing $S_{T}(k)$ for Small $k$

We process together all values $k\in[1,cb]$. Like in the previous sections,
for such values of $k$ we split $T$ in $n/b$ blocks of $b$ positions and work
with each such block separately; we compute all values $S_{T}(k)$ and only
keep track of $\max_{k\leq cb}S_{T}(k)/k$ before computing $S_{T}(k)$ for all
$k>cb$.

Consider block $L=B_{j}=T[(j-1)b+1\mathinner{.\,.}jb]$. The idea is to compute
the length of the longest substring starting at each position $i$ within $L$
that occurs in $T$ to the left of $i$ by binary searching on the possible
lengths. We thus allocate an array
$\textsf{LS}_{L}=\textsf{LS}_{L}[1\mathinner{.\,.}b]$ of size $b$ so that,
after we have finished processing $L$, $\textsf{LS}_{L}[i]$ will store the
length of the longest substring starting at position $i$ in $L$ that occurs in
$T$ before position $(j-1)b+i$. We compute these values in
$\tilde{\mathcal{O}}(n)$ time as follows.

At any step of the computation, we associate to each $i\in[1,b]$ within $L$ a
range $[u_{i},v_{i}]$, and check whether the length of the longest repeated
substring starting at $i$ belongs to the first half of the range or to the
second half. We first initialize all of the ranges to $[1,cb]$. At each step,
let $m_{i}=\lfloor(u_{i}+v_{i})/2\rfloor$: we search simultaneously for
occurrences of the $b$ patterns $T[(j-1)b+i\mathinner{.\,.}(j-1)b+i+m_{i}-1]$
to the left of position $(j-1)b+i-1$ in $T$, for all $i\in[1,b]$, in
$\tilde{\mathcal{O}}(n)$ time using $\mathcal{O}(b)$ space [27]. For each $i$
in $L$, if we find an occurrence of
$T[(j-1)b+i\mathinner{.\,.}(j-1)b+i+m_{i}-1]$ we must search for longer
substrings, because we aim at finding the longest substring that occurs
before, so we make the new interval $[m_{i}+1,v_{i}]$; on the contrary, if we
do not find any previous occurrence of
$T[(j-1)b+i\mathinner{.\,.}(j-1)b+i+m_{i}-1]$, we have to look for occurrences
of shorter substrings, and thus we make the new interval $[u_{i},m_{i}]$. We
proceed this way, halving the length of the intervals at every step, until
they are all of length $1$, and we set $\textsf{LS}_{L}[i]=u_{i}=v_{i}$ for
all $i\in[i,b]$.

Once we have computed $\textsf{LS}_{L}$ for block $L$, we use it to update the
corresponding values of $S_{T}$ in $\mathcal{O}(b)$ time the same way as we
used $\textsf{END}_{L}$ in Section 5. We have $n/b$ blocks and each block is
processed in $\tilde{\mathcal{O}}(n)$ time using $\mathcal{O}(b)$ space,
yielding the following lemma, that holds for any $b\in[1,n]$.

######  Lemma 2.

$\max\limits_{k\leq cb}S_{T}(k)/k$ can be computed in
$\tilde{\mathcal{O}}(n^{2}/b)$ time using $\mathcal{O}(b)$ space, for any
$b\in[1,n]$.

###  6.2 Computing $S_{T}(k)$ for Large $k$

When $k>cb$, we process $b$ values of $S_{T}(k)$ at a time, just like we did
in Section 4. Again, consider a phase $\alpha$ and blocks
$B_{j}=T[(j-1)b+1\mathinner{.\,.}jb]$ of $b$ positions of $T$, each followed
by a fragment $M_{j}$ of length $(\alpha-1)b$, that we call the anchor of
$B_{j}$, and two subsequent blocks $R_{j}=B_{j+\alpha}B_{j+\alpha+1}$. We
still aim to use the list of occurrences of $M_{j}$ to the left of $B_{j}$ as
anchors for finding possible multiple occurrences of the length-$k$ fragments
we are processing. We will distinguish two cases, depending on whether the
period of $M_{j}$ is at most $b/2$ or it is greater, and treat them
separately. However, before going into the two cases, we provide two lemmas on
the efficient representation and computation of all anchors’ occurrences. The
first lemma focuses on the size of the representation.

######  Lemma 3.

At each phase, the total space required to store a representation of all the
occurrences of all the anchors in $T$ is $\mathcal{O}(n^{2}/b^{2})$. When
$b\geq n^{2/3}$, we have that $n^{2}/b^{2}=\mathcal{O}(b)$.

###### Proof.

The list of occurrences of a single anchor $M_{j}$ can be represented using
$\mathcal{O}(n/b)$ space: this is because, if $\textsf{per}(M_{j})>b/2$, two
occurrences of $M_{j}$ are at least $b/2$ positions apart, and thus there are
no more than $2n/b=\mathcal{O}(n/b)$ occurrences of $M_{j}$ in $T$ overall; if
$\textsf{per}(M_{j})\leq b/2$, then all occurrences of $M_{j}$ in $T$ can be
expressed as a union of $\mathcal{O}(n/|M_{j}|)$ pairwise disjoint arithmetic
progressions with difference $\textsf{per}(M_{j})$. Recall that the length of
$M_{j}$ is $(\alpha-1)b$ for a phase $\alpha$, and so the length of $M_{j}$ in
any phase of the algorithm is at least $b$. Thus, the maximum space any such
union can occupy is $\mathcal{O}(n/b)$. As there are $\mathcal{O}(n/b)$
blocks, the statement follows. ∎

In the next lemma, we show that such a representation can be computed in
$\tilde{\mathcal{O}}(n)$ time. We store the occurrences of anchors with period
greater than $b/2$ explicitly, and represent the occurrences of anchors with
period at most $b/2$ by storing a number of runs containing all of them.

######  Lemma 4.

At each phase, a representation of all the occurrences of all the anchors in
$T$ can be computed in $\tilde{\mathcal{O}}(n)$ time using
$\mathcal{O}(n^{2}/b^{2})$ space. When $b\geq n^{2/3}$, we have that
$n^{2}/b^{2}=\mathcal{O}(b)$.

###### Proof.

To identify and process the anchors such that $\textsf{per}(M)\leq b/2$, we
proceed as follows. We analyse $\mathcal{O}(b)$ positions of $T$ at a time: in
a phase $\alpha$ we consider windows of $cb$ positions, for some constant
$c<(\alpha-1)/2$, overlapping by $(c-1)b$ positions. It is well-known that we
can compute the period of one such window in $\mathcal{O}(b)$ time [20], and
we do so for each window, from left to right.

When we find that the period $p$ of some window $W_{i}$ is at most $b/2$, we
keep track of the starting position of $W_{i}$ and keep on computing the
period of the subsequent windows as long as it is equal to $p$: let $W_{r}$ be
the rightmost consecutive such window. If $(r-i+c+2)b<(\alpha-1)b$, that is,
if the fragment of $T$ spanned by $W_{i},\ldots,W_{r}$ is too short to be part
of an occurrence of some anchor with period $p$, we discard the starting
position of $W_{i}$ and move on to compute the period of $W_{r+1}$.

Otherwise, we try to extend $p$ as much as possible to the left of $W_{i}$ and
to the right of $W_{r}$: since, by construction, $W_{i-1}$ and $W_{r+1}$ have
a period different from $p$, we can do it naively in $\mathcal{O}(b)$ time.
If, within this process, we find a run $Y$ of length at least $(\alpha-1)b$,
we compute its root $t$ and the fingerprint of $t$ in $\mathcal{O}(b)$ time
[23], and store in a dictionary, indexed by the fingerprint of $t$, the
starting and ending position $(s,e)$ of $Y$ and the offset of $t$ at which $Y$
starts.

The overall time cost of this procedure is in $\mathcal{O}(n)$:
$\mathcal{O}(b)$ time for each of the $\mathcal{O}(n/b)$ windows to compute
the periods, plus $\mathcal{O}(b)$ time to compute $\mathcal{O}(n/b)$ period
extensions and roots, plus $\mathcal{O}(n/b)$ time to construct the dictionary
for the fingerprints [28]. Once we have processed the whole $T$, we scan the
pairs of $\mathcal{O}(n/b)$ positions stored in the dictionary: if a run
$T[s\mathinner{.\,.}e]$ with root $r$, includes the starting and ending
position of an anchor $M_{j}$, we store in a list associated with $M_{j}$ all
of the runs
$T[s_{i}\mathinner{.\,.}e_{i}]=r[q_{i}\mathinner{.\,.}|r|]r^{\beta_{i}}r[1\mathinner{.\,.}\gamma_{i}]$
in the dictionary that have root $r$ and such that (i) $s_{i}$ is smaller than
the starting position of $M_{j}$, that is, $s_{i}<jb$, and (ii) the run
contains at least one full occurrence of
$M_{j}=r[q_{j}\mathinner{.\,.}|r|]r^{\beta_{j}}r[1\mathinner{.\,.}\gamma_{j}]$,
that is, its length after chopping off the prefix between $q_{i}$ and $q_{j}$
is at least as long as the anchor:
$e-s-((q_{i}-q_{j})\mod|r|)\geq(\alpha-1)\cdot b$, where
$q_{j}=(jb-s+q_{i})\mod|r|$. We further decorate $M_{j}$ with the fingerprint
of the root $r$, $(s_{i},e_{i})$ and $q_{i}$. By means of Lemma 3, storing all
such lists requires $\mathcal{O}(n^{2}/b^{2})$ space.

The anchors that do not fall in any of the runs have, by construction, a
period greater than $b/2$. We employ the algorithm of [27] to search for all
of such anchors $M_{j}$ at once in $\tilde{\mathcal{O}}(n)$ time, and store a
list of (previous) occurrences for each such $M_{j}$ in
$\mathcal{O}(n^{2}/b^{2})$ space overall (cf. Lemma 3). ∎

Once we have constructed the $\mathcal{O}(n^{2}/b^{2})$-sized representation
of the $M_{j}$ occurrences by means of Lemma 4, we will employ two different
strategies to process them depending on their period.

####  per$\boldsymbol{(M_{j})>b/2}$.

The goal is now to compute, for each such anchor $M_{j}$ and each of its
occurrences $i$, the longest common suffix between $B_{j}$ and
$T[1\mathinner{.\,.}i-1]$ and the longest common prefix between $R_{j}$ and
the suffix of $T[i+|M_{j}|\mathinner{.\,.}n]$: intuitively, we want to check
how much an occurrence $i$ extends to the left and to the right. To speed up
the computation, we process all substrings of a single phase at once rather
than process the positions of $T$ in batches of size $b$.

Note that we have enough space to keep, for each $M_{j}$, an array
$\textsf{LLE}_{j}$ storing the longest left extension for each of its
occurrences and an array $\textsf{LRE}_{j}$ storing the longest right
extensions. Our strategy is thus to compute such values for all the
occurrences of all anchors together, via “binary searching” over all possible
lengths in $\log b$ steps, each requiring $\tilde{\mathcal{O}}(n)$ time. Let
us focus on computing arrays LLE (the procedure for LRE is analogous).

Similarly to what we did in Section 6.1, at each iteration of such procedure
(binary search) we need to slash the range for the length of the left
extension at each occurrence of each anchor. This corresponds to checking, at
every iteration, whether appropriate suffixes of $B_{j}$ of various lengths
occur right before the occurrences of $M_{j}$, for all $j\in[1,n/b]$. Let us
point out that this problem is fundamentally different from the regular
multiple pattern matching problem entailed by the binary search procedure of
Section 6.1, as here we need to verify some specific occurrences of each
pattern rather than checking whether they occur anywhere in a prefix of $T$.

The algorithm of [27] reports the leftmost occurrence of each pattern and
cannot be easily adapted to solve this problem. We instead tweak the problem
so that, at any time, we need to verify the occurrences at certain positions
of a set of patterns _of equal length_. We call this the MultipleValidation
problem. Formally, given a set of patterns $P_{1},\ldots,P_{s}$, each of
length $\ell$ and each associated with a list of positions over $T$, we must
verify the occurrences of each pattern at the positions of its list. We next
show that we can solve this problem efficiently.

Figure 3: The first three steps of binary search for a single occurrence
$p_{i}$ of $M$.

######  Lemma 5.

Let $P_{1},\ldots,P_{s}$ be a set of patterns, each of length $\ell$ and each
associated with a list of positions over string $T$ of length $n$, and let $N$
be the total size of the lists. The MultipleValidation problem can be solved
in $\mathcal{O}(\ell s+N+n)$ time with high probability using
$\mathcal{O}(\ell+N)$ space.

###### Proof.

We first construct in $\mathcal{O}(N)$ time an array
$\mathcal{A}=\mathcal{A}[1\mathinner{.\,.}s]$ of $s\leq N$ hash tables, such
that $\mathcal{A}[i]$ stores the list of positions associated to $P_{i}$. We
compute in $\mathcal{O}(\ell s)$ time the fingerprint $\Phi(P_{i})$ of each
$P_{i}$ and store it into a global hash table $H$ that maps fingerprints to
indexes of patterns. We then slide a window of length $\ell$ over $T$,
maintaining the fingerprint of the fragment currently in the window: at each
time, we look the current fingerprint up in $H$. If it is equal to the
fingerprint of pattern $P_{i}$, we look up the starting position of the window
into the hash table in $\mathcal{A}[i]$ and flag the position in the list, if
we find it. This requires $\mathcal{O}(n)$ time and $\mathcal{O}(\ell)$ space,
concluding the proof. ∎

Concretely, in the first iteration of binary search we need to check, for each
occurrence $i$ of each anchor $M_{j}$, whether
$T[i-b/2\mathinner{.\,.}i-1]=B_{j}[b/2+1\mathinner{.\,.}b]$ or not. We thus
have $n/b$ patterns, each of length $\ell=b/2$, where a pattern $P_{j}$ is the
second half of a block $B_{j}$ and is associated with the list of occurrences
of $M_{j}$ shifted by $b/2$ positions to the left. The next iteration consists
in checking whether the common suffix can be extended with a fragment of
$B_{j}$ of length $b/4$ at locations where we found
$B_{j}[b/2+1\mathinner{.\,.}b]$, and if it is at least $b/4$ at locations
where we did not find it. In general, at iteration $q$ we need to process the
occurrences of $\mathcal{O}(n^{2}/b^{2})$ patterns, each of length $b/2^{q}$,
in lists of overall size $\mathcal{O}(n^{2}/b^{2})=\mathcal{O}(b)$. This
implies the following corollary.

######  Corollary 5.

The MultipleValidation problem can be solved in $\mathcal{O}(n)$ time for each
of the $\log b$ steps of binary search.

The whole procedure is summarized by Algorithm 1 in pseudocode, and the
process of binary searching at a single occurrence of an anchor is illustrated
in Figure 3. Lines 4-8 of the pseudocode are devoted to creating the
appropriate instance of the MultipleValidation problem, suitably associating
sets of positions of $T$ to fragments of blocks $B_{j}$. Line 9 runs the
MultipleValidation algorithm, whose output will be used to efficiently check
the condition at Line 12. Finally, at Line 13 we increase the values of
$\textsf{LLE}_{j}$ at the locations where some patterns were found.

1 for  _all anchors $M_{j}$_ do

2 for  _all $p_{i}$ in the list of $M_{j}$_ do $\textsf{LLE}_{j}[i]\leftarrow
0$ ;

3

4 for  _$q=1,\ldots,\log b$_ do

5 Patterns$\leftarrow\emptyset$;

6 for  _all anchors $M_{j}$_ do

7 for  _all $p_{i}$ in the list of $M_{j}$_ do

8 $P\leftarrow
L[b-\textsf{LLE}_{j}[i]-b/2^{q}\mathinner{.\,.}b-\textsf{LLE}_{j}[i]]$;

9 Patterns.add{$P$};
$\textsc{List}_{P}$.add{$p_{i}-\textsf{LLE}_{j}[i]-b/2^{q}$};

10

11

12 Solve the MultipleValidation problem for Patterns;

13 for  _all anchors $M_{j}$_ do

14 for  _all $p_{j}$ in the list of $M_{j}$_ do

15 if
_$L[b-\textsf{LLE}_{j}[i]-b/2^{q}\mathinner{.\,.}b-\textsf{LLE}_{j}[i]]=T[p_{i}-\textsf{LLE}_{j}[i]-b/2^{q}\mathinner{.\,.}p_{i}-\textsf{LLE}_{j}[i]]$_
then

16 $\textsf{LLE}_{j}[i]\leftarrow\textsf{LLE}_{j}[p]+b/2^{q}$;

17

18

19

20

Algorithm 1 Binary Search Procedure

######  Remark 2.

The MultipleValidation problem assumes that all of the patterns are distinct,
a condition that in general is not met when we apply it to compute the
extensions. We can work around this issue by choosing one representative for
each group of equal patterns, and by storing for each distinct representative
$P_{i}$ the union of the list of occurrences of all the patterns equal to
$P_{i}$; we keep track of which occurrences correspond to each copy of $P_{i}$
with additional hash tables.

#### Wrapping-Up.

Once we have computed $\textsf{LLE}_{j}$ and $\textsf{LRE}_{j}$ for each
anchor $M_{j}$ with the procedure above, we use them to fill in an array
$\textsf{END}_{B_{j}}$ as described in Section 5: each value of
$\textsf{END}_{B_{j}}$ is computed in $\mathcal{O}(1)$ time from
$\textsf{LLE}_{j}$ and $\textsf{LRE}_{j}$. Again like in Section 5,
$\textsf{END}_{B_{j}}$ will be used to update the corresponding values of
$S_{T}(k)$ in $\mathcal{O}(b)$ time. By Lemma 4, to compute a representation
of all the occurrences of all the anchors of a single phase takes time
$\tilde{\mathcal{O}}(n)$ and space $\mathcal{O}(n^{2}/b^{2})$. The binary
search procedure summarized by Algorithm 1 consists of $\log b$ steps, each of
them requiring time $\mathcal{O}(n)$ by Corollary 5, thus it takes
$\tilde{\mathcal{O}}(n)$ time for each phase. We obtain the following.

######  Lemma 6.

All anchors with a period greater than $b/2$ can be processed in
$\tilde{\mathcal{O}}(n^{2}/b)$ total time using $\mathcal{O}(n^{2}/b^{2})$
space, that is $\mathcal{O}(b)$ when $b\geq n^{2/3}$.

We next show how to process the anchors with a small period.

####  per$\boldsymbol{(M_{j})\leq b/2}$.

Recall that the setting now is the following: at each phase $\alpha$ we have a
set of at most $n/b$ anchors $M_{j}=T[jb+1\mathinner{.\,.}(j+\alpha-1)b]$,
each of length $(\alpha-1)b$ and with period at most $b/2$. $B_{j}$ is the
block of $b$ positions to the left of $M_{j}$ and $R_{j}$ is the block of $2b$
positions to its right. Each anchor $M_{j}$ is associated with a list of
$\mathcal{O}(n/b)$ runs that include all of the occurrences of $M_{j}$ up to
position $jb$ in $T$, that we computed in $\tilde{\mathcal{O}}(n)$ time by
means of Lemma 4, and with the starting and ending position $(s,e)$ of the run
$T[s\mathinner{.\,.}e]=t[q\mathinner{.\,.}|t|]t^{\beta}t[1\mathinner{.\,.}\gamma]$
in which $M_{j}$ is included. For ease of presentation, we will assume that
the run $T[s\mathinner{.\,.}e]$ is trimmed so that it extends up to $b$
positions to the left of $M_{j}$ and up to $2b$ positions to its right, thus
$s\geq(j-1)b$ and $e\leq(j+\alpha+1)b$. The goal now is to compute, for each
starting position $i$ in $B_{j}$, the length of the longest substring that
starts at $i$, ends within $R_{j}$, and occurs in $T$ to the left of $i$.

Similar to what we did in the previous sections, we will compute such values
by finding, for each occurrence $p_{i}$ of each anchor $M_{j}$, the longest
common suffix between $B_{j}$ and $T[1\mathinner{.\,.}p_{i}-1]$, and the
longest common prefix between $R_{j}$ and $T[p_{i}+|M_{j}|\mathinner{.\,.}n]$,
that we call the left extension and the right extension of occurrence $p_{i}$,
respectively. Consider an anchor $M_{j}$ within a trimmed run
$T[s\mathinner{.\,.}e]=t[q\mathinner{.\,.}|t|]t^{\beta}t[1\mathinner{.\,.}\gamma]$,
and a run
$T[s_{i}\mathinner{.\,.}e_{i}]=t[q_{i}\mathinner{.\,.}|t|]t^{\beta}t[1\mathinner{.\,.}\gamma_{i}]$
in the list of $M_{j}$, as depicted in Figure 4. We will distinguish the
following four cases, and treat each of them separately.

  * •

$q_{i}\neq q$, $\gamma_{i}\neq\gamma$. We will call this kind of runs
unsynchronized.

  * •

$q_{i}=q$, $\gamma_{i}\neq\gamma$. We will call this kind of runs left-
synchronized.

  * •

$q_{i}\neq q$, $\gamma_{i}=\gamma$. We will call this kind of runs right-
synchronized.

  * •

$q_{i}=q$, $\gamma_{i}=\gamma$. We will call this kind of runs bilaterally-
synchronized.

Figure 4: A run $T[s\mathinner{.\,.}e]$ that includes an anchor $M_{j}$, and a
run $T[s_{i}\mathinner{.\,.}e_{i}]$ in the list of $M_{j}$.

Depending on which of the cases above a run
$T[s_{i}\mathinner{.\,.}e_{i}]=t[q_{i}\mathinner{.\,.}|t|]t^{\beta}t[1\mathinner{.\,.}\gamma_{i}]$
falls into, the extensions of the occurrences of $M_{j}$ in
$T[s_{i}\mathinner{.\,.}e_{i}]$ are either all fully contained in the run, or
they can possibly stretch beyond it either on the left, on the right or on
both sides. In what follows, we will only focus on runs that are distinct from
$T[s\mathinner{.\,.}e]$, because the latter can be processed separately, as
remarked at the end of the next paragraph.

#### Unsynchronized Runs.

Let $M_{j}$ be an anchor included in a trimmed run
$T[s\mathinner{.\,.}e]=t[q\mathinner{.\,.}|t|]t^{\beta}t[1\mathinner{.\,.}\gamma]$,
and let
$T[s_{i}\mathinner{.\,.}e_{i}]=t[q_{i}\mathinner{.\,.}|t|]t^{\beta_{i}}t[1\mathinner{.\,.}\gamma_{i}]$
be an unsynchronized run in the list of $M_{j}$. Let $\ell=jb-s+1$ and
$m=e-(j+\alpha-1)b$ be the length of the periodic extension of $M_{j}$ in
$B_{j}$ and $R_{j}$, respectively, so that
$M_{j}=T[s+\ell\mathinner{.\,.}s+\ell+|M_{j}|-1]$.

The first observation is that all of the occurrences of $M_{j}$ in
$T[s_{i}\mathinner{.\,.}e_{i}]$ are such that both the left and the right
extension are fully within the run. Moreover, observe that if
$T[s_{i}\mathinner{.\,.}e_{i}]$ is so long that it contains an occurrence of
the whole $T[s\mathinner{.\,.}e]$, then there exists an occurrence of $M_{j}$
in $T[s_{i}\mathinner{.\,.}e_{i}]$ such that its left and right extension are
of length $\ell$ and $m$, respectively, and any other occurrence of $M_{j}$ in
any unsynchronized run has shorter or equal extensions; inspect Figure 5.

Figure 5: An unsynchronized run $T[s_{i}\mathinner{.\,.}e_{i}]$ long enough to
contain an occurrence of $T[s\mathinner{.\,.}e]$.

For shorter unsynchronized runs, we are able to prove that we only need to
consider up to two occurrences of $M_{j}$ within each run. In what follows, we
will denote by $\textsf{LLE}(p_{i})$ and $\textsf{LRE}(p_{i})$ the substrings
that constitute the left and the right extension at position $p_{i}$,
respectively.

######  Lemma 7.

Let
$T[s_{i}\mathinner{.\,.}e_{i}]=t[q_{i}\mathinner{.\,.}|t|]t^{\beta_{i}}t[1\mathinner{.\,.}\gamma_{i}]$
be an unsynchronized run in the list of an anchor $M_{j}$. There are at most
two occurrences $p_{1},p_{2}$ of $M_{j}$ in $T[s_{i}\mathinner{.\,.}e_{i}]$
such that, given any other occurrence $p_{3}$ of $M_{j}$ in
$T[s_{i}\mathinner{.\,.}e_{i}]$, $\textsf{LLE}(p_{3})M_{j}\textsf{LRE}(p_{3})$
is either a substring of $\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$ or a
substring of $\textsf{LLE}(p_{2})M_{j}\textsf{LRE}(p_{2})$.

We can compute the length of $\textsf{LLE}(p_{1})$, $\textsf{LRE}(p_{1})$,
$\textsf{LLE}(p_{2})$ and $\textsf{LRE}(p_{2})$ in constant time per run.

Figure 6: The two relevant occurrences $p_{1}$ (left) and $p_{2}$ (right) of
an anchor $M_{j}$ in a run $T[s_{i}\mathinner{.\,.}e_{i}]$, in the case where
$|T[s_{i}\mathinner{.\,.}e_{i}]|>|T[s\mathinner{.\,.}e]|$ but
$T[s_{i}\mathinner{.\,.}e_{i}]$ does not contain a full occurrence of
$T[s\mathinner{.\,.}e]$.

###### Proof.

Let $\ell=jb-s+1$ and $m=e-(j+\alpha-1)b$ be the length of the periodic
extension of $M_{j}$ in $B_{j}$ and $R_{j}$, respectively, so that
$M_{j}=T[s+\ell\mathinner{.\,.}s+\ell+|M_{j}|-1]$: recall that we assume
$T[s\mathinner{.\,.}e]$ to be trimmed so that $\ell\leq b$ and $m\leq 2b$. Let
$s+a_{1}$ be the leftmost position of $T[s\mathinner{.\,.}e]$ such that it is
to the left of $M_{j}$ (thus $s+a_{1}\leq s+\ell$),
$T[s+a_{1}\mathinner{.\,.}e]$ is synchronized with
$T[s_{i}\mathinner{.\,.}e_{i}]$ and the prefix of
$T[s_{i}\mathinner{.\,.}e_{i}]$ occurring at $T[s+a_{1}]$ is long enough to
contain the whole $M_{j}$, that is,
$s+a_{1}+|T[s_{i}\mathinner{.\,.}e_{i}]|\geq s+\ell+|M_{j}|$. Simmetrically,
let $s_{i}+a_{2}$ be the leftmost position of $T[s_{i}\mathinner{.\,.}e_{i}]$
such that $T[s_{i}+a_{2}\mathinner{.\,.}e_{i}]$ is synchronized with
$T[s\mathinner{.\,.}e]$ and $T[s_{i}+a_{2}\mathinner{.\,.}e_{i}]$ is long
enough to include a whole occurrence of
$T[s\mathinner{.\,.}s+\ell+|M_{j}|-1]$, that is,
$s_{i}+a_{2}+\ell+|M_{j}|-1\leq e_{i}$. Notice that either $a_{1}$ or $a_{2}$
may not exist. We claim that, should they exist, $p_{1}=s_{i}+\ell-a_{1}$ and
$p_{2}=s_{i}+a_{2}+\ell$ are such that, given any other occurrence $p_{3}$ of
$M_{j}$ in $T[s_{i}\mathinner{.\,.}e_{i}]$,
$\textsf{LLE}(p_{3})M_{j}\textsf{LRE}(p_{3})$ is either a substring of
$\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$, or it is a substring of
$\textsf{LLE}(p_{2})M_{j}\textsf{LRE}(p_{2})$.

Consider the occurrence of $M_{j}$ at $p_{1}$: by construction, it is such
that the left extension coincides with the longest possible prefix of
$T[s_{i}\mathinner{.\,.}e_{i}]$ that is fully contained into the periodic
extension of $M_{j}$ in $B_{j}$. As for the right extension, either (i) the
whole $T[s_{i}\mathinner{.\,.}e_{i}]$ occurs at position $s+a_{1}$, and thus
the right extension at $p_{1}$ is of length
$|T[s_{i}+p_{1}+|M_{j}|\mathinner{.\,.}e_{i}]|$ or (ii) only a proper prefix
of $T[s_{i}\mathinner{.\,.}e_{i}]$ occurs at position $s+a_{1}$, and thus the
right extension is of length $m$; inspect Figure 6 (left) for an example of
case (ii).

In case (i), $\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$ coincides with the
whole $T[s_{i}\mathinner{.\,.}e_{i}]$, thus any occurrence $p_{3}$ of $M_{j}$
to the right of $p_{1}$ is such that either
$\textsf{LLE}(p_{3})M_{j}\textsf{LRE}(p_{3})=T[s_{i}\mathinner{.\,.}e_{i}]=\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$
or it is equal to a prefix of $T[s_{i}\mathinner{.\,.}e_{i}]$, and any
occurrence $p_{3}$ to the left of $p_{1}$ is such that
$\textsf{LLE}(p_{3})M_{j}\textsf{LRE}(p_{3})$ is equal to a suffix of
$T[s_{i}\mathinner{.\,.}e_{i}]$. In case (ii),
$\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$ coincides with
$T[s+a_{1}\mathinner{.\,.}e]$. This implies that any occurrence $p_{3}$ of
$M_{j}$ to the right of $p_{1}$ is such that either
$\textsf{LLE}(p_{3})M_{j}\textsf{LRE}(p_{3})=\textsf{LLE}(p_{2})M_{j}\textsf{LRE}(p_{2})$
or it is equal to a proper prefix of
$\textsf{LLE}(p_{2})M_{j}\textsf{LRE}(p_{2})$; and any occurrence $p_{3}$ of
$M_{j}$ to the left of $p_{1}$ is such that
$\textsf{LLE}(p_{3})M_{j}\textsf{LRE}(p_{3})$ is equal to a suffix of
$\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$.

A similar reasoning holds for the extensions at $p_{2}$. Notice that, in
general, $\textsf{LLE}(p_{1})M_{j}\textsf{LRE}(p_{1})$ is not a substring of
$\textsf{LLE}(p_{2})M_{j}\textsf{LRE}(p_{2})$, and vice-versa; inspect Figure
6 for an example.

The length of $\textsf{LLE}(p_{1})$, $\textsf{LRE}(p_{1})$,
$\textsf{LLE}(p_{2})$ and $\textsf{LRE}(p_{2})$ can be computed in constant
time with simple formulas that only depend on the length of the runs and on
the offsets at which they start. For instance, in the case where
$|T[s_{i}\mathinner{.\,.}e_{i}]|\geq|T[s\mathinner{.\,.}e]|$ but
$T[s_{i}\mathinner{.\,.}e_{i}]$ does not contain a whole occurrence of
$T[s\mathinner{.\,.}e]$ (like in Figure 6), it is easy to verify that
$|\textsf{LLE}(p_{1})|=\ell-(q_{i}-q)\mod|t|$, $|\textsf{LRE}(p_{1})|=m$,
$|\textsf{LLE}(p_{2})|=\ell$ and
$|\textsf{LRE}(p_{2})|=m-((q-q_{i})\mod|t|-|T[s_{i}\mathinner{.\,.}e_{i}]|+|T[s\mathinner{.\,.}e]|)$,
provided they are positive values. Similar formulas can be easily devised for
the case where $|T[s_{i}\mathinner{.\,.}e_{i}]|<|T[s\mathinner{.\,.}e]|$. ∎

Lemma 7 implies that the length of the extensions of all the relevant
occurrences of $M_{j}$ in all of the unsynchronized runs can be computed in
$\mathcal{O}(n/b)$ time for a single anchor $M_{j}$, and thus in
$\mathcal{O}(n^{2}/b^{2})$ total time for all of the anchors of a single
phase.

######  Remark 3.

The occurrences of $M_{j}$ to the left of position $s+\ell$ in its same run
$T[s\mathinner{.\,.}e]$ can be processed in constant time by noticing that the
only relevant occurrence is the one at position $p=s+\ell-|t|$, if it exists.

#### Left-Synchronized Runs.

In left-synchronized runs it is possible that the left extension of some
occurrence exceeds the run, that is, it can be longer than $\ell$. Actually,
the following lemma shows that this can only happen at a specific occurrence
of $M_{j}$ in each run.

Figure 7: The left extension of an occurrence of $M_{j}$ in a left-
synchronized run exceeds the periodic region. The arcs represent repetitions
of the root, the zig zag lines represent a substring that is outside the run
and is preceded by two different letters.

######  Lemma 8.

Let
$T[s_{i}\mathinner{.\,.}e_{i}]=t[q_{i}\mathinner{.\,.}|t|]t^{\beta_{i}}t[1\mathinner{.\,.}\gamma_{i}]$
be a left-synchronized run in the list of an anchor $M_{j}$. There exists an
occurrence $p$ of $M_{j}$ in $T[s_{i}\mathinner{.\,.}e_{i}]$ such that, given
any other occurrence $p^{\prime}$ of $M_{j}$ in
$T[s_{i}\mathinner{.\,.}e_{i}]$,
$\textsf{LLE}(p^{\prime})M_{j}\textsf{LRE}(p^{\prime})$ is a substring of
$\textsf{LLE}(p)M_{j}\textsf{LRE}(p)$.

We can compute the length of $\textsf{LLE}(p)$ and $\textsf{LRE}(p)$ for all
the left-synchronized runs of all anchors in $\tilde{\mathcal{O}}(n)$ total
time.

###### Proof.

We claim that the only relevant occurrence of $M_{j}$ in
$T[s_{i}\mathinner{.\,.}e_{i}]$ is the one at position $p=s+\ell$, if
$T[s_{i}\mathinner{.\,.}e_{i}]$ is long enough for such $p$ to exist, and
otherwise $p$ is the rightmost occurrence of $M_{j}$ in
$T[s_{i}\mathinner{.\,.}e_{i}]$. In the latter case, it can be readily
verified that the left extension of $p$ is shorter than $\ell$, it cannot
stretch beyond the run, and thus $T[s_{i}\mathinner{.\,.}e_{i}]$ can be
processed the same way as the unsynchronized runs. Let us therefore restrict
to the case where $T[s_{i}\mathinner{.\,.}e_{i}]$ is long enough for $p$ to be
$s+\ell$; inspect Figure 7 for an example.

By construction, $|\textsf{LLE}(p)|\geq\ell$ and any occurrence of $M_{j}$
other than $p$ has a left extension fully contained in
$T[s_{i}\mathinner{.\,.}e_{i}]$, thus it is of length at most $\ell$ and such
that it is a substring of $\textsf{LLE}(p)$. Since, by definition of left-
synchronized runs, $\gamma_{i}\neq\gamma$, the right extension of $p$ is fully
contained in the run, if
$|T[s_{i}\mathinner{.\,.}e_{i}]|\geq|T[s\mathinner{.\,.}e]|$, it coincides
with the extension of the periodicity on the right of $M_{j}$, and thus is of
length $e-(\alpha+j)b$; otherwise, if
$|T[s_{i}\mathinner{.\,.}e_{i}]|<|T[s\mathinner{.\,.}e]|$, it is of length
$|T[s\mathinner{.\,.}e]|-|T[s_{i}\mathinner{.\,.}e_{i}]|$. It is thus easy to
verify that, for any occurrence $p^{\prime}\neq p$,
$\textsf{LLE}(p^{\prime})M_{j}\textsf{LRE}(p^{\prime})$ is a substring of
$\textsf{LLE}(p)M_{j}\textsf{LRE}(p)$.

We process the left extensions of the relevant occurrence $p$ in each left-
synchronized run with the same binary search procedure we used for the anchors
with a period larger than $b/2$, and thus we obtain the claimed time
complexity. ∎

A symmetric lemma holds for the right-synchronized runs; the bilaterally-
synchronized runs may contain two relevant occurrences of $M_{j}$,
corresponding to aligning $T[s\mathinner{.\,.}e]$ at the beginning and at the
very end of $T[s_{i}\mathinner{.\,.}e_{i}]$, respectively. The extension of
both these occurrences beyond the run can again be computed with the usual
binary search procedure.

#### Wrapping-Up.

We scan the list of runs of all the anchors. By Lemma 7, we compute the pairs
of extensions for the unsynchronized runs in time $\mathcal{O}(n^{2}/b^{2})$,
and mark the other runs as left-, right- or bilaterally-synchronized. We then
process the relevant occurrences in such runs altogether for all the anchors,
much in the same way as we did for the anchors with period larger than $b/2$,
in overall $\tilde{\mathcal{O}}(n)$ time. Once we have processed all of the
runs, we use the values we obtained to fill in an array $\textsf{END}_{B_{j}}$
for one block $B_{j}$ at a time, and use it to update the values of $S_{T}(k)$
as described in Section 5. We obtain the following.

######  Lemma 9.

All anchors with a period at most $b/2$ can be processed in
$\tilde{\mathcal{O}}(n^{2}/b)$ total time using $\mathcal{O}(n^{2}/b^{2})$
space, that is $\mathcal{O}(b)$ when $b\geq n^{2/3}$.

By combining Lemmas 2, 6, and 9, we arrive at Theorem 2.

See 2

## References

  * [1] Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton, Zvi Galil, and S. Muthukrishnan.  40 years of suffix trees.  Commun. ACM, 59(4):66–73, 2016.
  * [2] Lorraine A. K. Ayad, Golnaz Badkobeh, Gabriele Fici, Alice Héliou, and Solon P. Pissis.  Constructing antidictionaries in output-sensitive space.  In Data Compression Conference, DCC 2019, Snowbird, UT, USA, March 26-29, 2019, pages 538–547, 2019.
  * [3] Paul Beame.  A general sequential time-space tradeoff for finding unique elements.  SIAM J. Comput., 20(2):270–277, 1991.
  * [4] Paul Beame, Raphaël Clifford, and Widad Machmouchi.  Element distinctness, frequency moments, and sliding windows.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 290–299, 2013.
  * [5] Djamal Belazzougui.  Linear time construction of compressed text indices in compact space.  In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 148–193, 2014.
  * [6] Michael A. Bender and Martin Farach-Colton.  The LCA problem revisited.  In LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, pages 88–94, 2000.
  * [7] Allan Borodin and Stephen A. Cook.  A time-space tradeoff for sorting on a general sequential model of computation.  SIAM J. Comput., 11(2):287–297, 1982.
  * [8] Dany Breslauer and Zvi Galil.  Real-time streaming string-matching.  ACM Trans. Algorithms, 10(4):22:1–22:12, 2014.
  * [9] Dany Breslauer, Roberto Grossi, and Filippo Mignosi.  Simple real-time constant-space string matching.  Theoret. Comput. Sci., 483:2–9, 2013.
  * [10] Srecko Brlek.  Enumeration of factors in the Thue-Morse word.  Discr. Appl. Math., 24(1-3):83–96, 1989.
  * [11] Arturo Carpi and Aldo de Luca.  Words and special factors.  Theoret. Comput. Sci., 259(1-2):145–182, 2001.
  * [12] Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat.  Approximating text-to-pattern hamming distances.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 643–656, 2020.
  * [13] Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  Linear-time algorithm for long LCF with k mismatches.  In Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China, pages 23:1–23:16, 2018.
  * [14] Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.  Optimal-time dictionary-compressed indexes.  CoRR, abs/1811.12779v6, 2020.
  * [15] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya.  Dictionary matching in a stream.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 361–372, 2015.
  * [16] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya.  The _k_ -mismatch problem revisited.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 2039–2052, 2016.
  * [17] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat.  The streaming k-mismatch problem.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1106–1125, 2019.
  * [18] Raphaël Clifford and Tatiana Starikovskaya.  Approximate hamming distance in a stream.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 20:1–20:14, 2016\.
  * [19] Richard Cole, Tsvi Kopelowitz, and Moshe Lewenstein.  Suffix trays and suffix trists: Structures for faster text indexing.  Algorithmica, 72(2):450–466, 2015.
  * [20] Maxime Crochemore, Christophe Hancart, and Thierry Lecroq.  Algorithms on strings.  Cambridge University Press, 2007.
  * [21] Maxime Crochemore and Dominique Perrin.  Two-way string matching.  J. ACM, 38(3):651–675, 1991.
  * [22] Aldo de Luca.  On the combinatorics of finite words.  Theoret. Comput. Sci., 218(1):13–39, 1999.
  * [23] Jean Pierre Duval.  Factorizing words over an ordered alphabet.  Journal of Algorithms, 4(4):363–381, 1983.
  * [24] Martin Farach.  Optimal suffix tree construction with large alphabets.  In 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997, pages 137–143, 1997\.
  * [25] Paolo Ferragina and Giovanni Manzini.  Indexing compressed text.  J. ACM, 52(4):552–581, 2005.
  * [26] Gabriele Fici, Filippo Mignosi, Antonio Restivo, and Marinella Sciortino.  Word assembly through minimal forbidden words.  Theoret. Comput. Sci., 359(1-3):214–230, 2006.
  * [27] Johannes Fischer, Travis Gagie, Pawel Gawrychowski, and Tomasz Kociumaka.  Approximating LZ77 via small-space multiple-pattern matching.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 533–544, 2015.
  * [28] Michael L. Fredman, János Komlós, and Endre Szemerédi.  Storing a sparse table with $\mathcal{O}(1)$ worst case access time.  J. ACM, 31(3):538–544, 1984.
  * [29] Travis Gagie, Gonzalo Navarro, and Nicola Prezza.  Fully functional suffix trees and optimal text searching in BWT-runs bounded space.  J. ACM, 67(1):2:1–2:54, 2020.
  * [30] Zvi Galil and Joel I. Seiferas.  Time-space-optimal string matching.  J. Comput. Syst. Sci., 26(3):280–294, 1983.
  * [31] Pawel Gawrychowski and Tatiana Starikovskaya.  Streaming dictionary matching with mismatches.  In 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy, pages 21:1–21:15, 2019.
  * [32] Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat.  The streaming k-mismatch problem: Tradeoffs between space and total time.  In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, pages 15:1–15:15, 2020.
  * [33] Shay Golan, Tsvi Kopelowitz, and Ely Porat.  Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 65:1–65:16, 2018.
  * [34] Shay Golan, Tsvi Kopelowitz, and Ely Porat.  Streaming pattern matching with d wildcards.  Algorithmica, 81(5):1988–2015, 2019.
  * [35] Shay Golan and Ely Porat.  Real-time streaming multi-pattern search for constant alphabet.  In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 41:1–41:15, 2017.
  * [36] Roberto Grossi and Jeffrey Scott Vitter.  Compressed suffix arrays and suffix trees with applications to text indexing and string matching.  SIAM J. Comput., 35(2):378–407, 2005.
  * [37] Dan Gusfield.  Algorithms on Strings, Trees, and Sequences–Computer Science and Computational Biology.  Cambridge University Press, 1997.
  * [38] Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung.  Breaking a time-and-space barrier in constructing full-text indices.  SIAM J. Comput., 38(6):2162–2178, 2009.
  * [39] Juha Kärkkäinen, Peter Sanders, and Stefan Burkhardt.  Linear work suffix array construction.  J. ACM, 53(6):918–936, 2006.
  * [40] Richard M Karp and Michael O Rabin.  Efficient randomized pattern-matching algorithms.  IBM journal of research and development, 31(2):249–260, 1987.
  * [41] Dominik Kempa and Tomasz Kociumaka.  String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 756–767, 2019.
  * [42] Dominik Kempa and Nicola Prezza.  At the roots of dictionary compression: string attractors.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 827–840, 2018.
  * [43] John C. Kieffer and En-Hui Yang.  Grammar-based codes: a new class of universal lossless source codes.  IEEE Trans. Inf. Theory, 46(3):737–754, 2000.
  * [44] Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.  Towards a definitive measure of repetitiveness.  In Proc. 14th Latin American Symposium on Theoretical Informatics (LATIN), 2020.  To appear.
  * [45] Tomasz Kociumaka, Tatiana Starikovskaya, and Hjalte Wedel Vildhøj.  Sublinear space algorithms for the longest common substring problem.  In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 605–617, 2014.
  * [46] Andrei N. Kolmogorov.  Three approaches to the quantitative definition of information.  International Journal of Computer Mathematics, 2(1–4):157–168, 1968.
  * [47] Dmitry Kosolobov, Daniel Valenzuela, Gonzalo Navarro, and Simon J. Puglisi.  Lempel–Ziv-like parsing in small space.  Algorithmica, to appear.
  * [48] Sebastian Kreft and Gonzalo Navarro.  On compressing and indexing repetitive sequences.  Theoret. Comput. Sci., 483:115–133, 2013.
  * [49] Kanaru Kutsukake, Takuya Matsumoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  On repetitiveness measures of Thue-Morse words.  CoRR, abs/2005.09524, 2020.
  * [50] M. Lothaire.  Algebraic Combinatorics on Words.  Cambridge University Press, Cambridge, U.K., 2002.
  * [51] Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki.  Storage and retrieval of highly repetitive sequence collections.  J. Comput. Biol., 17(3):281–308, 2010.
  * [52] Udi Manber and Eugene W. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM J. Comput., 22(5):935–948, 1993.
  * [53] J. Ian Munro, Gonzalo Navarro, and Yakov Nekrich.  Space-efficient construction of compressed indexes in deterministic linear time.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 408–424, 2017.
  * [54] Gonzalo Navarro.  Compact Data Structures - A Practical Approach.  Cambridge University Press, 2016.
  * [55] Stav Ben Nun, Shay Golan, Tomasz Kociumaka, and Matan Kraus.  Time-space tradeoffs for finding a long common substring.  In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, pages 5:1–5:14, 2020.
  * [56] Benny Porat and Ely Porat.  Exact and approximate pattern matching in the streaming model.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 315–323, 2009.
  * [57] Jakub Radoszewski and Tatiana Starikovskaya.  Streaming _k_ -mismatch with error correcting and applications.  Inf. Comput., 271:104513, 2020.
  * [58] Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, and Adam D. Smith.  Sublinear algorithms for approximating string compressibility.  Algorithmica, 65(3):685–709, 2013.
  * [59] Milan Ružić.  Constructing efficient dictionaries in close to sorting time.  In Automata, Languages and Programming, ICALP 2008, Part I, volume 5125 of LNCS, pages 84–95. Springer, 2008.
  * [60] Tatiana Starikovskaya and Hjalte Wedel Vildhøj.  Time-space trade-offs for the longest common substring problem.  In Combinatorial Pattern Matching, 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013. Proceedings, pages 223–234, 2013\.
  * [61] Peter Weiner.  Linear pattern matching algorithms.  In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11, 1973.
  * [62] Zong-Da Wu, Tao Jiang, and Wu-Jie Su.  Efficient computation of shortest absent words in a genomic sequence.  Inf. Process. Lett., 110(14-15):596–601, 2010.
  * [63] Andrew Chi-Chih Yao.  Near-optimal time-space tradeoff for element distinctness.  SIAM J. Comput., 23(5):966–975, 1994.
  * [64] Jacob Ziv and Abraham Lempel.  A universal algorithm for sequential data compression.  IEEE Trans. Inf. Theory, 23(3):337–343, 1977.