Reichman University and University of Haifa,
Israelitai.bone@biu.ac.ilhttps://orcid.org/0009-0007-8895-4069supported by
Israel Science Foundation grant 810/21. Reichman University and University of
Haifa, Israelgolansh1@biu.ac.ilhttps://orcid.org/0000-0001-8357-2802supported
by Israel Science Foundation grant 810/21. Bar Ilan University,
Israelshur@datalab.cs.biu.ac.ilhttps://orcid.org/0000-0002-7812-3399supported
by the ERC grant MPM under the EU’s Horizon 2020 Research and Innovation
Programme (grant no. 683064) and by the State of Israel through the Center for
Absorption in Science of the Ministry of Aliyah and Immigration. Jane Open
Access and Joan R. Public [500]Theory of computation Pattern matching

# String 2-Covers with No Length Restrictions

Itai Boneh  Shay Golan  Arseny Shur

###### Abstract

A $\lambda$-cover of a string $S$ is a set of strings
$\\{C_{i}\\}_{1}^{\lambda}$ such that every index in $S$ is contained in an
occurrence of at least one string $C_{i}$. The existence of a $1$-cover
defines a well-known class of quasi-periodic strings. Quasi-periodicity can be
decided in linear time, and all $1$-covers of a string can be reported in
linear time plus the size of the output. Since in general it is NP-complete to
decide whether a string has a $\lambda$-cover, the natural next step is the
development of efficient algorithms for $2$-covers. Radoszewski and
Straszyński [ESA 2020] analysed the particular case where the strings in a
$2$-cover must be of the same length. They provided an algorithm that reports
all such $2$-covers of $S$ in time near-linear in $|S|$ and in the size of the
output.

In this work, we consider $2$-covers in full generality. Since every
length-$n$ string has $\Omega(n^{2})$ trivial $2$-covers (every prefix and
suffix of total length at least $n$ constitute such a $2$-cover), we state the
reporting problem as follows: given a string $S$ and a number $m$, report all
$2$-covers $\\{C_{1},C_{2}\\}$ of $S$ with length $|C_{1}|+|C_{2}|$ upper
bounded by $m$. We present an $\tilde{O}(n+\mathsf{output})$ time algorithm
solving this problem, with $\mathsf{output}$ being the size of the output.
This algorithm admits a simpler modification that finds a $2$-cover of minimum
length. We also provide an $\tilde{O}(n)$ time construction of a $2$-cover
oracle which, given two substrings $C_{1},C_{2}$ of $S$, reports in poly-
logarithmic time whether $\\{C_{1},C_{2}\\}$ is a $2$-cover of $S$.

###### keywords:

Quasi-periodicity, String cover, Range query

###### category:

##  1 Introduction

For a string $S$, the substring $C$ of $S$ is a cover of $S$ if every index of
$S$ is covered by an occurrence of $C$. Since the introduction of covers by
Apostolico and Ehrenfeucht [4], many algorithms have been developed for
finding covers or variations of covers of a given string. [4] presented an
$O(n\log^{2}n)$ time algorithm for finding all covers of an input string of
length $n$. It was shown by Moore and Smyth [23, 24] that all covers of a
string can be reported in $O(n)$ time. Smyth [28] further extended this result
by showing that the covers of all prefixes of $S$ can be computed in $O(n)$
time. Further works on covers and variants of cover include [1, 19, 7, 2, 3,
16, 6, 25].

A natural generalization of a cover is a $\lambda$-cover. A set of strings
$\\{C_{1},C_{2},\ldots,C_{\lambda}\\}$ is a $\lambda$-cover of $S$ if every
index in $S$ is covered by an occurrence of $C_{i}$ for some $i\in[\lambda]$.
The notion of $\lambda$-covers was introduced by Guo, Zhang and Iliopoulos
[17, 30], who proposed an $O(n^{2})$ time algorithm for computing all
$\lambda$-covers of a string $S$ over a constant size alphabet for a given
$\lambda$. The running time analysis of their algorithm was later found to be
faulty by Czajka and Radoszewski [11], who showed that it has an exponential
worst-case running time. Cole et al. [9] justified the lack of a polynomial
algorithm for computing all $\lambda$-covers by proving that the problem is
NP-complete.

In this work, we focus on $2$-covers. Radoszewski and Straszyński [26] have
considered a special case of “balanced” $2$-covers, where the two strings
composing the $2$-cover have equal length. They proposed an
$\tilde{O}(n+\mathsf{output})$-time algorithm reporting all balanced
$2$-covers of a given length-$n$ string $S$. They also provide two versions of
this algorithm, one of which finds a balanced $2$-cover of each possible
length and the other determines the shortest balanced $2$-cover of $S$; both
versions work in $\tilde{O}(n)$ time.

Designing efficient algorithms for the same problems on $2$-covers in the
general case is posed in [26] as an open problem.

For a $2$-cover $\\{C_{1},C_{2}\\}$, its _length_ is $|C_{1}|+|C_{2}|$.
Following the open problem of Radoszewski and Straszyński, we specify the
following problems for $2$-covers in the general case:

  * •

All_2-covers$(S,m)$: for a string $S$, report all $2$-covers of length at most
$m$;

  * •

Shortest_2-cover$(S)$: for a string $S$, find a $2$-cover of minimum length;

  * •

2-cover_Oracle$(S)$: for a string $S$, build a data structure that answers the
queries of the form “do given two substrings of $S$ constitute a $2$-cover of
$S$?”

Note that every length-$n$ string $S$ trivially has $\Omega(n^{2})$
$2$-covers. E. g., if $C_{1}$ is a prefix of $S$, $C_{2}$ is a suffix of $S$,
and $|C_{1}|+|C_{2}|\geq n$, then $\\{C_{1},C_{2}\\}$ is a $2$-cover of $S$.
The length restriction made in the above formulation of the All_2-covers
problem allows one to consider instances with smaller outputs, thus returning
the running times of type $\tilde{O}(n+\mathsf{output})$ into the game.

##### Our contribution.

In this work, we solve the three above problems in near linear time.

######  Theorem 1.1.

There exists an algorithm that solves _All_2-covers $(S,m)$_ in
$O(n\log^{5}n+\mathsf{output}\cdot\log^{3}n)$ time.

######  Theorem 1.2.

There exists an algorithm that solves _Shortest_2-cover $(S)$_ in
$O(n\log^{4}n)$ time.

######  Theorem 1.3.

There exists an algorithm that solves _2-cover_Oracle $(S)$_ in
$O(n\log^{5}n)$ preprocessing time and $O(\log^{3}n)$ query time.

##### Techniques and Ideas.

The main idea of our algorithms is the formulation of the property “an index
$i$ in $S$ is covered by an occurrence of a substring $U$ of $S$” in terms of
point location. At a high level, each index $i$ is assigned a compactly
representable area $\mathcal{A}_{i}$ in the plane, and every substring $U$
that is _not highly periodic_ corresponds to a point $p_{U}$ in the plane such
that $p_{U}\in\mathcal{A}_{i}$ if and only if the index $i$ is covered by some
occurrence of $U$. The same idea, implemented in three dimensions instead of
two, covers the case of highly periodic substrings.

Given such a geometric representation, our algorithms make use of multi-
dimensional range-reporting and range-stabbing data structures to retrieve and
organize the areas associated with each index in $S$. This organization
facilitates the computation of a core set of the $2$-covers, which consists of
pairs of strings that are not highly periodic. This set provides a solution to
the Shortest_2-cover problem. Besides that, we create the oracle solving the
2-cover_Oracle problem and utilize the core set to finalize our solution to
the All_2-covers problem with a small number of queries to this oracle.

##### Organization.

In Section 2 we present notation, auxiliary lemmas, and pre-existing data
structures that are used in our algorithms. In Section 3 we formalize and
prove the connection between covering an index in a string by an occurrence of
a substring and multidimensional point location. In Section 4 we build upon
the insights presented in Section 3 to design the $2$-cover oracle and prove
Theorem 1.3. Finally, in Section 5 we present the reporting algorithms proving
Theorem 1.2 and Theorem 1.1 (the latter one executes the oracle). All details
omitted due to space constraints are put into Appendix.

##  2 Preliminaries

Here we present definitions, notation, and auxiliary lemmas. For completeness,
proofs of the statements appearing in this section are given in Appendix B.

We assume in this paper that $0\in\mathbb{N}$. We denote
$[x..y]=\\{i\in\mathbb{N}\mid x\leq i\leq y\\}$ for any _real_ numbers $x,y$,
possibly negative. We also denote $[x]=[1..x]$. The notation $\mathsf{output}$
stands for the size of output of a reporting algorithm.

All strings in the paper are over an alphabet $\Sigma=\\{1,2,\ldots
O(n^{c})\\}$ for some constant $c$. The letters of a string $S$ are indexed
from 1 to $|S|$. If $X=S[i..j]$, $X$ is called a _substring_ of $S$ (a
_prefix_ of $S$ if $i=1$, a _suffix_ of $S$ if $j=|S|$, and an empty string if
$i>j$). We also say that $S[i..j]$ specifies an _occurrence of $X$ at position
$i$_. If $X$ is a substring of $S$, then $S$ is a _superstring_ of $X$. A
string $X$ that occurs both as a prefix and as a suffix of $S$ is a _border_
of $S$. A string $S$ has _period_ $\rho$ if $S[i]=S[i+\rho]$ for all
$i\in[|S|-\rho]$. Clearly, $S$ has period $\rho$ if and only if
$S[1..|S|-\rho]$ is a border of $S$. The minimal period of $S$ is denoted by
$\mathsf{per}(S)$. Let $\mathsf{per}(S)=\rho$. We say that $S$ is _aperiodic_
if $|S|<2\rho$, _( $\rho$-)periodic_ if $|S|\geq 2\rho$, and _highly (
$\rho$-)periodic_ if $|S|\geq 3\rho$. We say that $S$ is short
($\rho$)-periodic if $|S|\in[2\rho..3\rho-1]$. Note that if a string $X$
occurs in $S$ at positions $i$ and $j$, then $|j-i|\geq\mathsf{per}(X)$.

The following two lemmas specify some useful structure of periodic prefixes
and borders.

######  Lemma 2.1.

The prefixes of a length-$n$ string have, in total, $O(\log n)$ different
periods.

######  Lemma 2.2.

Every string of length $n$ has $O(\log n)$ aperiodic borders and $O(\log n)$
short periodic borders.

We use well known notion of the longest common prefix ($\mathsf{LCP}$).

######  Definition 2.3.

For two strings $S$ and $T$, $\mathsf{LCP}(S,T)=\max\\{\ell\mid
S[1..\ell]=T[1..\ell]\\}$ is the length of their longest common prefix and
$\mathsf{LCP}^{R}(S,T)=\max\\{\ell\mid
S[|S|-\ell+1..|S|]=T[|T|-\ell+1..|T|]\\}$ is the length of their longest
common suffix.

##### Covers.

Given a string $S$, we say that a substring $X$ _covers_ an index $i$ if for
some indices $j_{1},j_{2}\in[|S|]$ we have $X=S[j_{1}..j_{2}]$ and
$i\in[j_{1}..j_{2}]$. We also say that the occurrence of $X$ at $j_{1}$ covers
$i$. If $X$ covers every $i\in[|S|]$, we call $X$ a _$1$ -cover_ of $S$. A
pair of substrings $(X,Y)$ is said to cover $i$ if $X$ or $Y$ covers $i$. If a
pair $(X,Y)$ covers every $i\in[|S|]$, we call $(X,Y)$ a _$2$ -cover_ of $S$.
(It will be convenient to consider 2-covers as ordered pairs, though the
notion of 2-cover is symmetric with respect to $X$ and $Y$.) We say that
$(X,Y)$ is highly periodic if either $X$ or $Y$ is highly periodic, otherwise
$(X,Y)$ is non-highly periodic. The following lemma considers a periodic
string that covers index $i$.

######  Lemma 2.4.

Let $S$ be a string, and let $X$ be a $\rho$-periodic substring. If the string
$X$ covers an index $i$, then the string $X[1..|X|-\rho]]$ (=
$X[\rho+1..|X|]$) also covers $i$.

##### Runs.

A $\rho$-periodic substring of $S$ is a _run_ if it is not contained in a
longer $\rho$-periodic substring. We use the following lemmas regarding runs.

######  Lemma 2.5.

Let $S$ be a string, $\rho\in[|S|]$. Every index $i$ in $S$ is covered by at
most two $\rho$-periodic runs and by $O(\log n)$ highly-periodic runs.

######  Lemma 2.6.

Let $S$ be a string. For every $\rho$-periodic substring $S[i..j]$, there is a
unique $\rho$-periodic run containing $S[i..j]$.

######  Lemma 2.7.

If there is an integer $\rho$ such that $S[x..y]$ is $\rho$-periodic and
$S[x..y+1]$ is not $\rho$-periodic, then $S[x..y+1]$ is aperiodic.

######  Lemma 2.8 ([5, Theorem 9]).

The number of runs in any string $S$ is smaller than $|S|$.

###  2.1 Range Data Structures

Our algorithms use data structures for _orthogonal range queries_. Such a data
structure is associated with a positive integer dimension $d$ and deals with
$d$-dimensional points and $d$-dimensional ranges. A $d$-dimensional point is
a $d$-tuple $p=(x_{1},x_{2},\ldots,x_{d})$ and a $d$-dimensional range is the
cartesian product
$R=[a_{1}..b_{1}]\times[a_{2}..b_{2}]\times\ldots\times[a_{d}..b_{d}]$ of $d$
ranges. We call a $2$-dimensional range a _rectangle_ and a $3$-dimensional
range a _cuboid_. We say that a point $p$ is contained in the range $R$
(denoted by $p\in R$) if $x_{i}\in[a_{i}..b_{i}]$ for every $i\in[d]$.

We make use of the following range data structures.

######  Lemma 2.9 (Range Query Data Structure [29, 8]).

For any integer $d$, a set $P$ of $n$ points in $\mathbb{R}^{d}$ can be
preprocessed in $O(n\log^{d-1}n)$ time to support the following queries.

  * •

Reporting: Given a $d$-dimensional range $R$, output all points in the set
$P\cap R$.

  * •

Emptiness: Given a $d$-dimensional range $R$, report if $P\cap R=\emptyset$ or
not.

The query time is $O(\log^{d-1}n)$ for Emptiness and
$O(\log^{d-1}n+\mathsf{output})$ for Reporting.

######  Lemma 2.10 (Range stabbing queries [8, Theorems 5 and 7]).

For any integer $d$, a set of $d$-dimensional ranges $R_{1},R_{2},\ldots
R_{n}$ can be prepossessed in $O(n\log^{d-1}n)$ time to support the following
queries.

  * •

Stabbing: Given a $d$-dimensional point $p$, report all ranges $R_{i}$ such
that $p\in R_{i}$.

  * •

Existence: Given a $d$-dimensional point $p$, report if no ranges $R_{i}$
satisfy $p\in R_{i}$.

The query time is $O(\log^{d-1}n)$ for Existence and
$O(\log^{d-1}n+\mathsf{output})$ for Stabbing.

###  2.2 Stringology Algorithms and Data Structures

Throughout the paper, we make use of the following string algorithms and data
structures.

######  Lemma 2.11 (Pattern Matching [18]).

There exists an algorithm that, given a string $T$ of length $n$ and a string
$P$ of length $m\leq n$, reports in $O(n)$ time all the occurrences of $P$ in
$T$.

######  Lemma 2.12 ($\mathsf{LCP}_{S}$ Data Structure [21, 15]).

There exists a data structure $\mathsf{LCP}_{S}$ that preprocesses an
arbitrary string $S\in\Sigma^{*}$ of length $n$ in $O(n)$ time and supports
constant-time queries $\mathsf{LCP}_{S}(i,j)=\mathsf{LCP}(S[i..n],S[j..n])$
and $\mathsf{LCP}^{R}_{S}(i,j)=\mathsf{LCP}^{R}(S[1..i],S[1..j])$.

When $S$ is clear from context, we simply write $\mathsf{LCP}(i,j)$ and
$\mathsf{LCP}^{R}(i,j)$.

######  Lemma 2.13 (Internal Pattern Matching ($\mathsf{IPM}$) [20]).

There exists a data structure $\mathsf{IPM}_{S}$ that preprocesses an
arbitrary string $S\in\Sigma^{*}$ of length $n$ in $O(n)$ time and supports
the following constant-time queries.

  * •

Periodic: given a substring $X$, return $\mathsf{per}(X)$ if $X$ is periodic,
and “aperiodic” otherwise.

  * •

Internal Matching: Given two substrings $X$ and $Y$ such that $|Y|=O(|X|)$,
return all occurrences of $X$ in $Y$ represented as $O(1)$ arithmetic
progressions.

######  Lemma 2.14 (Finding all Substrings, see [22]).

There is an algorithm that reports all distinct substrings of a string
$S[1..n]$ in time $O(n+\mathsf{output})$.

######  Lemma 2.15 (Finding all Runs [13, Theorem 1.4]).

There is algorithm that computes all runs of a string $S\in\Sigma^{*}$ of
length $n$ in $O(n)$ time.

##  3 Range Characterization of Covering an Index

In this section we translate the property “an index is covered by an
occurrence of a given substring” to the language of $d$-dimensional points and
ranges. Then this property can be checked with the queries described in Lemmas
2.9 and 2.10. We distinguish between the $2$-dimensional case of not highly
periodic substrings (Lemma 3.1) and 3-dimensional case of highly periodic
substrings (Lemma 3.2). Given a point $p$ and a set $\mathcal{R}$ of ranges
(both in $d$ dimensions), we slightly abuse the notation, writing
$p\in\mathcal{R}$ instead of $p\in\bigcup_{R\in\mathcal{R}}R$.

To present the algorithms that prove these lemmas, we first describe an
$O(n\log^{2}n)$ time preprocessing phase. Throughout the rest of the paper, we
assume that this preprocessing has already been executed.

##### Preprocessing.

The algorithm computes $\mathsf{LCP}_{S}$ data structure of Lemma 2.12 and
$\mathsf{IPM}_{S}$ data structure of Lemma 2.13. In addition, the algorithm
computes all runs of $S$ using Lemma 2.15. For every $\rho\in[n]$, the
algorithm stores all $\rho$-periodic runs of $S$ in a $3$-dimensional range
reporting data structure $D^{\rho}_{\mathsf{run}}$ of Lemma 2.9 as follows.
For every $\rho$-periodic run $S[\ell..r]$, the data structure
$D^{\rho}_{\mathsf{run}}$ contains the point $p=(\ell,r,r-\ell+1)$. By Lemma
2.8, the total number of runs stored in the structures
$D^{\rho}_{\mathsf{run}}$ over all $\rho\in[n]$ is at most $n$. It follows
from Lemmas 2.12, 2.13, 2.15 and 2.9 that the preprocessing time is
$O(n\log^{2}n)$.

###  3.1 The Not Highly Periodic Case

In this section we prove the following lemma.

######  Lemma 3.1.

Let $f,i\in[n]$ be two indices and let $k\in\mathbb{N}$. There exists a set
$\mathcal{R}$ of $O(1)$ rectangles such that for any $\ell,r\in\mathbb{N}$
with $\ell+r+1\in[1.5^{k}..1.5^{k+1}]$ the string
$\mathsf{sub}=S[f-\ell..f+r]$ satisfies the following conditions:

  1. 1.

If $(\ell,r)\in\mathcal{R}$, then $\mathsf{sub}$ covers $i$ and
$\mathsf{per}(\mathsf{sub})\geq\frac{1.5^{k}}{4}$.

  2. 2.

If $\mathsf{sub}$ covers $i$ and is not highly periodic, then
$(\ell,r)\in\mathcal{R}$.

Moreover, $\mathcal{R}$ can be computed in $O(\log^{2}n)$ time.

For $f\in[n]$ and $k\in\mathbb{N}$, let
$\mathsf{sub}_{\mathsf{left}}=S[f-\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor..f]$,
and
$\mathsf{sub}_{\mathsf{right}}=S[f..f+\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor]$.
If an endpoint of a substring is outside $S$, the substring is undefined.

Let $f\in[n]$ be an index and $k\in\mathbb{N}$. For every
$\mathsf{sub}=S[f-\ell..f+r]$ such that $\ell,r\in\mathbb{N}$ and
$|\mathsf{sub}|\in[1.5^{k}..1.5^{k+1}]$, $\mathsf{sub}$ is a superstring of
either $\mathsf{sub}_{\mathsf{left}}$ or $\mathsf{sub}_{\mathsf{right}}$.

Section 3.1 allows us to prove Lemma 3.1 as follows. First we find a set
$\mathcal{R}_{1}$ that satisfies the conditions of the lemma for all pairs
$(\ell,r)$ such that $\mathsf{sub}=S[f-\ell..f+r]$ is a superstring of
$\mathsf{sub}_{\mathsf{right}}$. Similarly, we find a set $\mathcal{R}_{2}$
for the case where $\mathsf{sub}$ is a superstring of
$\mathsf{sub}_{\mathsf{left}}$. Then $\mathcal{R}_{1}\cup\mathcal{R}_{2}$ is
the set required by the lemma.

In the rest of the section we show how to find the set $\mathcal{R}_{1}$. (The
argument for the set $\mathcal{R}_{2}$ is similar, so we omit it.) Let us fix
$f,\ell$, and
$r\geq\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor=|\mathsf{sub}_{\mathsf{right}}|-1$.
Let $i_{\mathsf{right}}$ denote the starting index of an occurrence of
$\mathsf{sub}_{\mathsf{right}}$. We make the following claim.

######  Claim 1.

There exists a rectangle $R$ such that for any $\ell,r\in\mathbb{N}$ with
$\ell+r+1\in[1.5^{k}..1.5^{k+1}]$ and
$r\geq\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor$ the substring
$\mathsf{sub}=S[f-\ell..f+r]$ covers the index $i$ with the occurrence at
position $i_{\mathsf{right}}-\ell$ if and only if $(\ell,r)\in R$. Moreover,
$R$ can be computed in $O(1)$ time.

Let $e_{r}=\mathsf{LCP}(f,i_{\mathsf{right}})$,
$e_{\ell}=\mathsf{LCP}^{R}(f,i_{\mathsf{right}})$. Using $\mathsf{LCP}_{S}$,
we compute in $O(1)$ time the rectangle
$R=[i_{\mathsf{right}}-i\>..\>e_{\ell}-1]\times[i-i_{\mathsf{right}}\>..\>e_{r}-1]$
and check the required conditions.

First assume $(\ell,r)\in R$. Since $\ell\leq e_{\ell}-1$ and $r\leq e_{r}-1$,
one has
$\mathsf{sub}=S[f-\ell..f+r]=S[i_{\mathsf{right}}-\ell..i_{\mathsf{right}}+r]$,
so $\mathsf{sub}$ occurs at $i_{\mathsf{right}}-\ell$. Since $\ell\geq
i_{\mathsf{right}}-i$ and $r\geq i-i_{\mathsf{right}}$, we have
$i\in[i_{\mathsf{right}}-\ell..i_{\mathsf{right}}+r]$, so this occurrence
covers $i$.

Now assume that $\mathsf{sub}$ covers $i$ with the occurrence at
$i_{\mathsf{right}}-\ell$. Since $\mathsf{sub}$ occurs at
$i_{\mathsf{right}}-\ell$, one has $\ell\leq e_{\ell}-1$ and $r\leq e_{r}-1$.
Since this occurrence covers $i$, one also has
$i\in[i_{\mathsf{right}}-\ell..i_{\mathsf{right}}-\ell+|\mathsf{sub}|-1]=[i_{\mathsf{right}}-\ell..i_{\mathsf{right}}+r]$.
Then $\ell\geq i_{\mathsf{right}}-i$ and $r\geq i-i_{\mathsf{right}}$, which
finally proves $(\ell,r)\in R$.

If $\mathsf{sub}$ covers index $i$, its substring
$\mathsf{sub}_{\mathsf{right}}$ must occur close to $i$. Since
$|\mathsf{sub}|\leq 1.5^{k+1}$, if an occurrence of $\mathsf{sub}$ at
$i_{\mathsf{right}}-\ell$ covers $i$, then the position $i_{\mathsf{right}}$,
at which $\mathsf{sub}_{\mathsf{right}}$ occurs, is inside the range
$[i-1.5^{k+1}..i+1.5^{k+1}]$. Let $\mathsf{occ}_{\mathsf{right}}$ be the set
of all such indices $i_{\mathsf{right}}$ from this range. We distinguish
between two cases, regarding the period of $\mathsf{sub}_{\mathsf{right}}$.

##### Case 1:
$\mathsf{per}(\mathsf{sub}_{\mathsf{right}})\geq\frac{1.5^{k}}{4}$.

The following claim is easy.

######  Claim 2.

If $\mathsf{per}(\mathsf{sub}_{\mathsf{right}})\geq\frac{1.5^{k}}{4}$, then
$|\mathsf{occ}_{\mathsf{right}}|=O(1)$.

The distance between two consecutive occurrences of
$\mathsf{sub}_{\mathsf{right}}$ is at least $\frac{1.5^{k}}{4}$. Since a range
of length $2\cdot 1.5^{k+1}$ contains $O(1)$ disjoint ranges of length
$\frac{1.5^{k}}{4}$, the claim follows.

Now we build the set $\mathcal{R}_{1}$. We compute
$\mathsf{occ}_{\mathsf{right}}$ in $O(1)$ time using the $\mathsf{IPM}_{S}$
data structure. For every $j\in\mathsf{occ}_{\mathsf{right}}$, we take the
rectangle $R_{j}$ from Claim 1. Let $\mathcal{R}_{1}=\\{R_{j}\mid
j\in\mathsf{occ}_{\mathsf{right}}\\}$. By Claim 2, $|\mathcal{R}_{1}|=O(1)$.
Consider a pair $(\ell,r)$ such that $\ell+r+1\in[1.5^{k}..1.5^{k+1}]$ and
$r\geq\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor$, and let
$\mathsf{sub}=S[f-\ell..f+r]$. If $(\ell,r)\in\mathcal{R}_{1}$, then
$(\ell,r)\in R_{j}$ for some $j\in\mathsf{occ}_{\mathsf{right}}$. Hence by
Claim 1 $\mathsf{sub}$ covers $i$ with an occurrence at $j-\ell$ and
$\mathsf{per}(\mathsf{sub})\geq\mathsf{per}(\mathsf{sub}_{\mathsf{right}})\geq\frac{1.5^{k}}{4}$,
as required. Conversely, if $\mathsf{sub}$ covers $i$ with an occurrence at
$j$, then $j^{\prime}=j+\ell$ belongs to $\mathsf{occ}_{\mathsf{right}}$. Then
by Claim 1 $(\ell,r)\in R_{j^{\prime}}$ and thus $(\ell,r)\in\mathcal{R}_{1}$.
This concludes the proof of Lemma 3.1 in the case
$\mathsf{per}(\mathsf{sub}_{\mathsf{right}})\geq\frac{1.5^{k}}{4}$.

##### Case 2:
$\rho=\mathsf{per}(\mathsf{sub}_{\mathsf{right}})<\frac{1.5^{k}}{4}$.

Let $\mathsf{run}_{f}=S[f-\ell^{f}_{\mathsf{run}}..f+r^{f}_{\mathsf{run}}]$ be
the $\rho$-periodic run containing $S[f..f+|\mathsf{sub}_{\mathsf{right}}|-1]$
(such a run exists by Lemma 2.6). Consider a pair $(\ell,r)$ such that
$\ell+r+1\in[1.5^{k}..1.5^{k+1}]$ and
$r\geq\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor$, and let the string
$\mathsf{sub}=S[f-\ell..f+r]$ be not highly periodic. Then
$\mathsf{per}(\mathsf{sub})>\frac{1.5^{k}}{3}>\rho$. Hence $\mathsf{sub}$ is
not a substring of $\mathsf{run}_{f}$, which means that either
$\ell>\ell^{f}_{\mathsf{run}}$ or $r>r^{f}_{\mathsf{run}}$. Below we assume
$r>r^{f}_{\mathsf{run}}$; the other case is symmetric. We first observe that
this inequality guarantees that $\mathsf{per}(\mathsf{sub})$ is big enough.

######  Claim 3.

For every $\mathsf{sub}=S[f-\ell..f+r]$ with $r>r^{f}_{\mathsf{run}}$ one has
$\mathsf{per}(\mathsf{sub})\geq\frac{1.5^{k}}{4}$.

The substring $S[f..f+r^{f}_{\mathsf{run}}]$ is $\rho$-periodic and
$u=S[f..f+r^{f}_{\mathsf{run}}+1]$ is not (otherwise, $\mathsf{run}_{f}$ is
not a run). By Lemma 2.7, $u$ is aperiodic. Then
$\mathsf{per}(u)>\frac{|u|}{2}\geq\frac{1.5^{k}}{4}$. It remains to note that
$u$ is a substring of $\mathsf{sub}$.

Let $\mathsf{sub}_{\mathsf{right}}^{\to}=S[f..f+r_{\mathsf{run}}^{f}]$. Note
that $\mathsf{sub}_{\mathsf{right}}^{\to}$ is a $\rho$-periodic suffix of the
$\rho$-periodic run $\mathsf{run}^{f}$ and $\mathsf{sub}$ contains
$\mathsf{sub}_{\mathsf{right}}^{\to}$ followed by a letter that breaks the
period $\rho$. This means that if $\mathsf{sub}$ covers $i$, then $S$
contains, close to $i$, a $\rho$-periodic run with the suffix
$\mathsf{sub}_{\mathsf{right}}^{\to}$. Let us say that a $\rho$-periodic run
$S[a_{\mathsf{run}}\>..\>b_{\mathsf{run}}]$ is close to $i$ if
$a_{\mathsf{run}}\leq i+1.5^{k+1}$ and $b_{\mathsf{run}}\geq i-1.5^{k+1}$.
Clearly, if $\mathsf{sub}$ covers $i$, it contains the suffix
$\mathsf{sub}_{\mathsf{right}}^{\to}$ of a run close to $i$.

Let $\mathsf{Run}_{\mathsf{close}}$ be the set of $\rho$-periodic runs close
to $i$ with length at least $|\mathsf{sub}_{\mathsf{right}}^{\to}|$.

######  Claim 4.

$|\mathsf{Run}_{\mathsf{close}}|=O(1)$. Moreover,
$\mathsf{Run}_{\mathsf{close}}$ can be computed in $O(\log^{2}n)$ time.

Assume that $\mathsf{Run}_{\mathsf{close}}$ is ordered by the positions of
runs. Each of these runs has length at least $\frac{1.5^{k}}{2}$ and any two
$\rho$-periodic runs overlap by less than $\rho<\frac{1.5^{k}}{4}$ positions.
Then the positions of any two consecutive runs from
$\mathsf{Run}_{\mathsf{close}}$ differ by more than $\frac{1.5^{k}}{4}$ and
any two non-consecutive runs are disjoint. Since the first run ends no later
than the position $i-1.5^{k+1}$ by definition of being close to $i$, the third
and all subsequent runs start after this position. Again by definition, all
runs start before the position $i+1.5^{k+1}$. The range
$[i-1.5^{k+1}..i+1.5^{k+1}]$ contains $O(1)$ positions such that any two of
them differ by more than $\frac{1.5^{k}}{4}$. Hence we get
$|\mathsf{Run}_{\mathsf{close}}|=O(1)$.

Querying $D^{\rho}_{\mathsf{run}}$ with the range
$[-\infty..i+1.5^{k+1}]\times[i-1.5^{k+1}..\infty]\times[|\mathsf{sub}_{\mathsf{right}}^{\to}|..\infty]$
we get all $\rho$-periodic runs that are close to $i$ (due to the first two
coordinates) and have length at least $|\mathsf{sub}_{\mathsf{right}}^{\to}|$
(due to the last coordinate); i.e., what we get is
$\mathsf{Run}_{\mathsf{close}}$. The query time is $O(\log^{2}n)$ by Lemma
2.9.

Now we construct the set $\mathcal{R}_{1}$. We query $D^{\rho}_{\mathsf{run}}$
with
$[-\infty..f]\times[f+\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor..\infty]\times[-\infty..\infty]$
to get the unique $\rho$-periodic run
$\mathsf{run}_{f}=[f-\ell^{f}_{\mathsf{run}}..f+r^{f}_{\mathsf{run}}]$
containing the substring
$\mathsf{sub}_{\mathsf{right}}=S[f..f+\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor]$.
Then we compute the $O(1)$-size set $\mathsf{Run}_{\mathsf{close}}$ (Claim 4).
For every $\mathsf{run}\in\mathsf{Run}_{\mathsf{close}}$ we check, with an
$\mathsf{LCP}$ query, whether $\mathsf{sub}_{\mathsf{right}}^{\to}$ is a
suffix of $\mathsf{run}$. If yes, we compute the position $i_{\mathsf{right}}$
of this suffix from the parameters of the run. Since $i_{\mathsf{right}}$ is
the position of an occurrence of $\mathsf{sub}_{\mathsf{right}}$, we apply
Claim 1 to obtain a rectangle $R=[\ell_{1},\ell_{2}]\times[r_{1},r_{2}]$.
Since in our argument we assume $r>r_{\mathsf{run}}^{f}$, we replace $r_{1}$
with $\max\\{r_{1},r_{\mathsf{run}}^{f}+1\\}$. If the range for $r$ remains
nonempty, we denoted the obtained rectangle by $R_{\mathsf{run}}$.

Let
$\mathcal{R}_{\mathsf{right}}=\\{R_{\mathsf{run}}\mid\mathsf{run}\in\mathsf{Run}_{\mathsf{close}}\\}$.
In a symmetric way, we consider the case $\ell>\ell_{\mathsf{run}}^{f}$ and
build the set $\mathcal{R}_{\mathsf{left}}$. Finally we set
$\mathcal{R}_{1}=\mathcal{R}_{\mathsf{right}}\cup\mathcal{R}_{\mathsf{left}}$.
The time complexity is dominated by $O(1)$ queries to
$D^{\rho}_{\mathsf{run}}$, which take $O(\log^{2}n)$ by Lemma 2.9.

Now consider a pair $(\ell,r)$ such that $\ell+r+1\in[1.5^{k}..1.5^{k+1}]$ and
$r\geq\left\lfloor{\frac{1.5^{k}}{2}}\right\rfloor$, and let
$\mathsf{sub}=S[f-\ell..f+r]$. If $(\ell,r)\in\mathcal{R}_{1}$, then
$(\ell,r)$ belongs to some rectangle from $\mathcal{R}_{\mathsf{right}}$ or
$\mathcal{R}_{\mathsf{left}}$; these cases are symmetric, so let this
rectangle be $R_{\mathsf{run}}\in\mathcal{R}_{\mathsf{right}}$, where
$\mathsf{run}=[a_{\mathsf{run}}..b_{\mathsf{run}}]$. Hence by Claim 1
$\mathsf{sub}$ covers $i$ with an occurrence at
$b_{\mathsf{run}}-r_{\mathsf{run}}^{f}-\ell$. We also have
$\mathsf{per}(\mathsf{sub})\geq\frac{1.5^{k}}{4}$ by Claim 3. Conversely, if
$\mathsf{sub}$ is not highly periodic, then either $r>r_{\mathsf{run}}^{f}$ or
$\ell>\ell_{\mathsf{run}}^{f}$. Without loss of generality, let
$r>r_{\mathsf{run}}^{f}$. Now if $\mathsf{sub}$ covers $i$ with an occurrence
at $j$, then there is an occurrence of $\mathsf{sub}_{\mathsf{right}}^{\to}$
at $j^{\prime}=j+\ell$ that is a suffix of a $\rho$-periodic run
$\mathsf{run}$. Then by Claim 1 we have $(\ell,r)\in R_{\mathsf{run}}$ and
thus $(\ell,r)\in\mathcal{R}_{1}$. Thus, we finished the proof of Lemma 3.1.

###  3.2 The Highly Periodic Case

In this section we prove Lemma 3.2, which is the analog of Lemma 3.1 for
periodic strings.

We begin with more notation. Let $u$ be a $\rho$-periodic string having a
substring $v$ of length $\rho$. Then there exist unique integers
$d_{1},d_{2}\in[0..\rho-1]$ and $q\in\mathbb{N}$ such that
$u=v[\rho{-}d_{1}{+}1..\rho]v^{q}v[1..d_{2}]$. We abbreviate this
representation as $u=v^{[d_{1};q;d_{2}]}$. Let $u=v^{[d_{1};q;d_{2}]}$. The
numbers $d_{1},d_{2}$, and $q$ can be computed in $O(1)$ time given $|u|,|v|$,
and the position of any occurrence of $v$ in $u$. For a $\rho$-periodic
substring $\mathsf{sub}=S[f-\ell..f+r]$, we define its _root_ by

$\mathsf{root}=\begin{cases}S[f..f+\rho-1],&\text{if }r\geq\rho-1,\\\
S[f-\rho..f-1],&\text{otherwise}.\end{cases}$

Thus, $\mathsf{sub}=\mathsf{root}^{[d_{\ell};q_{\ell,r};d_{r}]}$ for some
unique integers $d_{\ell},d_{r}\in[0..\rho-1]$ and $q_{\ell,r}>0$.

######  Lemma 3.2.

Let $f,i\in[n]$ be two indices and let $\rho\in[n]$. There exists a set
$\mathcal{C}$ of $O(1)$ cuboids such that every highly $\rho$-periodic
substring of the form $\mathsf{sub}=S[f-\ell..f+r]$ with $\ell,r\in\mathbb{N}$
satisfies the following: $\mathsf{sub}$ covers index $i$ if and only if
$(d_{\ell},d_{r},q_{\ell,r})\in\mathcal{C}$. Moreover, $\mathcal{C}$ can be
computed in $O(\log^{2}n)$ time.

Let $\mathsf{sub}=S[f-\ell..f+r]$ be highly $\rho$-periodic. By Lemma 2.6,
each occurrence of $\mathsf{sub}$ is contained in a unique $\rho$-periodic
run. By Lemma 2.5, there are at most two such runs containing $i$ (say,
$\mathsf{run}_{1}$ and $\mathsf{run}_{2}$). Hence if $\mathsf{sub}$ covers
$i$, it does so with an occurrence contained either in $\mathsf{run}_{1}$ or
in $\mathsf{run}_{2}$. Then Lemma 3.2 follows from Lemma 3.3 below: we query
$D^{\rho}_{\mathsf{run}}$ to get $\mathsf{run}_{1}$ and $\mathsf{run}_{2}$ (in
$O(\log^{2}n)$ time by Lemma 2.9), take the sets $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ given by Lemma 3.3 for $\mathsf{run}_{1}$ and
$\mathsf{run}_{2}$ respectively, and let
$\mathcal{C}=\mathcal{C}_{1}\cup\mathcal{C}_{2}$.

######  Lemma 3.3.

Let $\mathsf{run}=S[a_{\mathsf{run}}..b_{\mathsf{run}}]$ be a $\rho$-periodic
run containing $i$. There is a set $\mathcal{C}$ of $O(1)$ cuboids such that
$\mathsf{sub}$ covers $i$ with an occurrence contained in $\mathsf{run}$ if
and only if $(d_{\ell},d_{r},q_{\ell,r})\in\mathcal{C}$. Moreover, the set
$\mathcal{C}$ can be computed in $O(1)$ time.

In the rest of the section we describe the algorithm computing the set
$\mathcal{C}$ of Lemma 3.3.

First the algorithm checks the length of $\mathsf{run}$. Since $\mathsf{sub}$
is highly $\rho$-periodic, $\mathsf{sub}\geq 3\rho$. If
$|\mathsf{run}|<3\rho$, then $\mathsf{sub}$ has no occurrences in
$\mathsf{run}$. Hence in this case $\mathcal{C}=\varnothing$. Next, the
algorithm verifies if $\mathsf{root}$ is a substring of $\mathsf{run}$. Due to
$\rho$-periodicity of $\mathsf{run}$, it is sufficient to check for an
occurrence of $\mathsf{root}$ the prefix of $\mathsf{run}$ having length
$2\rho=2|\mathsf{root}|$. By Lemma 2.13, this check can be done in $O(1)$ time
with the $\mathsf{IPM}_{S}$ data structure. If $\mathsf{root}$ is not a
substring of $\mathsf{run}$, then once again $\mathsf{sub}$ has no occurrences
in $\mathsf{run}$ and so $\mathcal{C}=\varnothing$.

From now on, we assume that $|\mathsf{run}|\geq 3\rho$ and $\mathsf{run}$
contains an occurrence of $\mathsf{root}$. Then the algorithm computes, in
$O(1)$ time by Section 3.2, the parameters of the representation
$\mathsf{run}=\mathsf{root}^{[d_{\ell}^{\mathsf{run}};q_{\mathsf{run}};d_{r}^{\mathsf{run}}]}$.
One has $q_{\mathsf{run}}\geq 2$ since $|\mathsf{run}|\geq 3\rho$. We recall
that $\mathsf{sub}=\mathsf{root}^{[d_{\ell};q_{\ell,r};d_{r}]}$.

Note that $\mathsf{sub}$ covers index $i$ of $S$ with an occurrence contained
in $\mathsf{run}$ if and only if it covers the index $j=i-a_{\mathsf{run}}+1$
_of the string $\mathsf{run}$_. In order to build the set $\mathcal{C}$, we
describe, in Claim 7, a set of necessary and sufficient conditions for
$\mathsf{sub}$ to cover an index $j$ of $\mathsf{run}$. We denote
$b_{\ell}=[d_{\ell}>d_{\ell}^{\mathsf{run}}]$,
$b_{r}=[d_{r}>d_{r}^{\mathsf{run}}]$ (Iverson bracket notation). We need two
auxiliary claims.

######  Claim 5.

Let $\mathsf{sub}$ occur in $\mathsf{run}$. If $x$ is the starting index of
its leftmost occurrence and $y$ is the ending index of its rightmost
occurrence, then $x=d_{\ell}^{\mathsf{run}}-d_{\ell}+1+b_{\ell}\rho$,
$y=d_{\ell}^{\mathsf{run}}+(q_{\mathsf{run}}-b_{r})\rho+d_{r}$, and $[x..y]$
is exactly the set of indices covered by $\mathsf{sub}$ in $\mathsf{run}$.

We prove the formula for $x$ as the argument for $y$ is similar. Since
$\mathsf{run}$ is $\rho$-periodic, we have $x\in[1..\rho]$ (otherwise, there
is another occurrence at position $x-\rho$). Since $\mathsf{root}$ occurs in
$\mathsf{sub}$ at position $d_{\ell}+1$, $\mathsf{run}$ has a matching
occurrence of $\mathsf{root}$ at position
$d_{\ell}+x\in[d_{\ell}+1..d_{\ell}+\rho]$. The occurrences of $\mathsf{root}$
in $\mathsf{run}$ are at positions
$d_{\ell}^{\mathsf{run}}{+}1,d_{\ell}^{\mathsf{run}}{+}\rho{+}1,\ldots$, so
exactly one of them starts in $[d_{\ell}+1..d_{\ell}+\rho]$. If $d_{\ell}\leq
d_{\ell}^{\mathsf{run}}$, one has
$d_{\ell}^{\mathsf{run}}+1\in[d_{\ell}+1..d_{\ell}+\rho]$. Therefore, we have
$d_{\ell}^{\mathsf{run}}+1=d_{\ell}+x$, implying
$x=d_{\ell}^{\mathsf{run}}-d_{\ell}+1+0\cdot\rho$ as required. Similarly, if
$d_{\ell}>d_{\ell}^{\mathsf{run}}$, one has
$d_{\ell}^{\mathsf{run}}+\rho+1\in[d_{\ell}+1..d_{\ell}+\rho]$. Then
$d_{\ell}^{\mathsf{run}}+\rho+1=d_{\ell}+x$, which implies
$x=d_{\ell}^{\mathsf{run}}-d_{\ell}+1+1\cdot\rho$ as required.

Since $\mathsf{run}$ is $\rho$-periodic, the positions of any two consecutive
occurrences of $\mathsf{sub}$ in $\mathsf{run}$ differ by $\rho$ (see Figure
1). As $|\mathsf{sub}|>\rho$, the indices in $\mathsf{run}$ covered by
occurrences of $\mathsf{sub}$ form a single range from the first index of the
leftmost occurrence (i.e., $x$) to the last index of the rightmost occurrence
(i.e. $y$).

######  Claim 6.

The string $\mathsf{sub}$ occurs in $\mathsf{run}$ if and only if
$q_{\ell,r}\leq q_{\mathsf{run}}-b_{\ell}-b_{r}$.

Let $\mathsf{sub}$ occur in $\mathsf{run}$. By Claim 5, its leftmost
occurrence is at $x=d^{\mathsf{run}}_{\ell}-d_{\ell}+1+b_{\ell}\rho$ and its
rightmost occurrence ends at
$y=d_{\ell}^{\mathsf{run}}+(q_{\mathsf{run}}-b_{r})\rho+d_{r}$. Clearly, we
have the inequality $y-x+1\geq|\mathsf{sub}|=d_{\ell}+q_{\ell,r}\rho+d_{r}$,
which is equivalent to $q_{\ell,r}\leq q_{\mathsf{run}}-b_{\ell}-b_{r}$.

For the converse, we assume that this inequality holds and show that
$\mathsf{sub}$ occurs in $\mathsf{run}$ at position
$x=d_{\ell}^{\mathsf{run}}-d_{\ell}+1+b_{\ell}\rho$. Since $\mathsf{sub}$ and
$\mathsf{run}$ are both $\rho$-periodic and share the substring
$\mathsf{root}$ of length $\rho$, it suffices to prove that
$|\mathsf{run}[x..|\mathsf{run}|]|\geq|\mathsf{sub}|$. Observing that
$b_{r}\rho\geq d_{r}-d_{r}^{\mathsf{run}}$, we obtain

$|\mathsf{run}[x..|\mathsf{run}|]|=q_{\mathsf{run}}\rho+d_{\ell}^{\mathsf{run}}+d_{r}^{\mathsf{run}}-x+1=(q_{\mathsf{run}}-b_{\ell})\rho+d_{\ell}+d_{r}^{\mathsf{run}}\\\
\geq(q_{\mathsf{run}}-b_{\ell}-b_{r})\rho+d_{\ell}+d_{r}\geq
q_{\ell,r}\rho+d_{\ell}+d_{r}=|\mathsf{sub}|,$

as required.

######  Claim 7.

The string $\mathsf{sub}=\mathsf{root}^{[d_{\ell};q_{\ell,r};d_{r}]}$ covers
index $j$ in
$\mathsf{run}=\mathsf{root}^{[d_{\ell}^{\mathsf{run}};q_{\mathsf{run}};d_{r}^{\mathsf{run}}]}$
if and only if one of the following mutually exclusive conditions holds:

  1. 1.

$d_{\ell}\leq d_{\ell}^{\mathsf{run}}$, $d_{r}\leq d_{r}^{\mathsf{run}}$,
$q_{\ell,r}\leq q_{\mathsf{run}}\phantom{\,-\,1}$, and
$j\in[d_{\ell}^{\mathsf{run}}-d_{\ell}+1\>..\>d_{\ell}^{\mathsf{run}}+q_{\mathsf{run}}\rho+d_{r}]$;

  2. 2.

$d_{\ell}>d_{\ell}^{\mathsf{run}}$, $d_{r}\leq d_{r}^{\mathsf{run}}$,
$q_{\ell,r}\leq q_{\mathsf{run}}-1$, and
$j\in[d_{\ell}^{\mathsf{run}}-d_{\ell}+1+\rho\>..\>d_{\ell}^{\mathsf{run}}+q_{\mathsf{run}}\rho+d_{r}]$;

  3. 3.

$d_{\ell}\leq d_{\ell}^{\mathsf{run}}$, $d_{r}>d_{r}^{\mathsf{run}}$,
$q_{\ell,r}\leq q_{\mathsf{run}}-1$, and
$j\in[d_{\ell}^{\mathsf{run}}-d_{\ell}+1\>..\>d_{\ell}^{\mathsf{run}}+(q_{\mathsf{run}}-1)\rho+d_{r}]$;

  4. 4.

$d_{\ell}>d_{\ell}^{\mathsf{run}}$, $d_{r}>d_{r}^{\mathsf{run}}$,
$q_{\ell,r}\leq q_{\mathsf{run}}-2$, and
$j\in[d_{\ell}^{\mathsf{run}}-d_{\ell}+1+\rho\>..\>d_{\ell}^{\mathsf{run}}+(q_{\mathsf{run}}-1)\rho+d_{r}]$.

If $\mathsf{sub}$ covers index $j$, then $\mathsf{sub}$ occurs in
$\mathsf{run}$. Hence Claim 6 implies the inequalities and Claim 5 implies the
range for each of conditions 1–4.

For the converse, if one of the conditions 1–4 is true, then $\mathsf{sub}$
indeed occurs in $\mathsf{run}$ according to Claim 6. Then again Claim 5
implies the range of indices covered by occurrences of $\mathsf{sub}$. As $j$
belongs to this range, it is covered.

The algorithm builds the set $\mathcal{C}$ by running through conditions 1–4
of Claim 7. If $j=i-a_{\mathsf{run}}+1$ belongs to the range from a condition,
the algorithm adds to $\mathcal{C}$ the cuboid defined by the inequalities
listed in this condition; otherwise, it does nothing. The cuboids for the
conditions 1, 2, 3, and 4 are, respectively,
$[1..d_{\ell}^{\mathsf{run}}]\times[1..d_{r}^{\mathsf{run}}]\times[1..q_{\mathsf{run}}]$;
$[d_{\ell}^{\mathsf{run}}{+}1..\rho]\times[1..d_{r}^{\mathsf{run}}]\times[1..q_{\mathsf{run}}{-}1]$;
$[1..d_{\ell}^{\mathsf{run}}]\times[d_{r}^{\mathsf{run}}{+}1..\rho]\times[1..q_{\mathsf{run}}{-}1]$;
$[d_{\ell}^{\mathsf{run}}{+}1..\rho]\times[d_{r}^{\mathsf{run}}{+}1..\rho]\times[1..q_{\mathsf{run}}{-}2]$.

##### Correctness.

Let $\mathsf{sub}$ cover $i$ with an occurrence contained in $\mathsf{run}$.
Then $\mathsf{sub}$ covers the index $j=i-a_{\mathsf{run}}+1$ in
$\mathsf{run}$. By Claim 7, the triple $(d_{\ell},d_{r},q_{\ell,r})$ satisfies
one of conditions 1–4, say, condition N. In particular, $j$ belongs to the
interval of condition N. Then the algorithm built a cuboid $C$ from the
inequalities of condition N such that $(d_{\ell},d_{r},q_{\ell,r})\in C$.
Conversely, if $(d_{\ell},d_{r},q_{\ell,r})\in C$, where $C$ was built from
condition N of Claim 7, then $j$ belongs to the interval of condition N. Hence
condition N holds; by Claim 7, $\mathsf{sub}$ covers the index $j$ in
$\mathsf{run}$, and thus covers $i$ in $S$.

As the time complexity is straightforward, Lemma 3.3, and then Lemma 3.2, is
proved.

##  4 2-Covers Oracle

In this section, we present a solution to the 2-cover_Oracle problem (Theorem
1.3). The preliminary part of the solution is common to all three problems.

Every 2-cover of $S$ contains a prefix and a suffix of $S$. Respectively, each
2-cover has one of two types (see [26]): a prefix-suffix 2-cover (_ps-cover_)
consists of a prefix of $S$ and a suffix of $S$ while in a border-substring
2-cover (_bs-cover_) one string is a border of $S$. We process these two cases
separately.

Let $(U_{1},U_{2})$ be a pair of substrings. Lemmas 3.1 and 3.2 allow us to
express each predicate “$U_{j}$ covers index $i$” as
$p_{j}\in\mathcal{R}_{j}^{i}$, where $p_{j}$ is a point and
$\mathcal{R}_{j}^{i}$ is a set of $O(1)$ ranges in $d_{j}$ dimensions. Then
the predicate “$(U_{1},U_{2})$ is a 2-cover” is expressed by the 2CNF formula
$\bigwedge_{i=1}^{n}(p_{1}\in\mathcal{R}_{1}^{i}\vee
p_{2}\in\mathcal{R}_{2}^{i})$. We answer the instances of this predicate with
a new data structure based on rectangle stabbing (Lemma 2.10). The lemma below
is proven in Appendix C.

######  Lemma 4.1 (2CNF Range Data Structure).

Let $d_{\ell},d_{r}$ be integer constants and let
$\mathsf{Pairs}=\\{(\mathcal{L}_{1},\mathcal{R}_{1}),(\mathcal{L}_{2},\mathcal{R}_{2}),\ldots,(\mathcal{L}_{n},\mathcal{R}_{n})\\}$
be a set of pairs such that for every $i\in[n]$, $\mathcal{L}_{i}$ is a set of
$O(1)$ $d_{\ell}$-dimensional orthogonal ranges and $\mathcal{R}_{i}$ is a set
of $O(1)$ $d_{r}$-dimensional orthogonal ranges. The set $\mathsf{Pairs}$ can
be prepossessed in $O(n\log^{d_{\ell}+d_{r}-1}n)$ time to a data structure
that supports the following query in $O(\log^{d_{\ell}+d_{r}-1}n)$ time:

  * •

$\mathsf{query}(p_{\ell},p_{r})$: for a $d_{\ell}$-dimensional point
$p_{\ell}$ and a $d_{r}$-dimensional point $p_{r}$, decide if for every
$i\in[n]$ either $p_{\ell}\in\mathcal{L}_{i}$ or $p_{r}\in\mathcal{R}_{i}$.

As Lemma 3.1 refers to particular ranges and Lemma 3.2 refers to particular
periods, we partition substrings into groups and build a separate
$2\mathsf{CNF}$ data structure for each pair of groups. For prefixes,
suffixes, and borders, we have $O(\log n)$ periods (Lemma 2.1) and thus
$O(\log n)$ groups of highly periodic prefixes (suffixes, borders). The
remaining prefixes (suffixes) form $O(\log n)$ groups associated with length
ranges $[1.5^{k}..1.5^{k+1}]$ for some $k$. There are $O(\log n)$ remaining
borders (Lemma 2.2), so each of them forms a separate group. For each group of
borders we choose a fixed position $f$. Highly periodic substrings containing
$f$ form $O(\log n)$ groups (Lemma 2.5); the other are grouped according to
$O(\log n)$ length ranges. Therefore, in total we build $O(\log^{2}n)$
$2\mathsf{CNF}$ data structures for ps-covers and bs-covers.

##### Effective dimension.

A direct implementation of Lemmas 3.1 and 3.2 leads to the $2\mathsf{CNF}$
structures of dimension 4 to 6. Let us show how to lower the dimension. For
any group $\mathsf{pref}$ of prefixes we take $f=1$. Then in Lemma 3.1 all
points have the form $(0,r)$. So we have _fixed_ first coordinate and
_variable_ second coordinate. In Lemma 3.2, one has
$\mathsf{root}=S[1..\rho]$, and thus all points have the form
$(0,d_{r},q_{r})$ with two variable coordinates. For groups of suffixes we
take $f=n$ and symmetrically get the points of the form $(\ell,0)$ or
$(d_{\ell},0,q_{\ell})$. Since borders are simultaneously prefixes and
suffixes, we get two fixed coordinates in the corresponding points. (Assuming
$f=1$, a group consisting of a single border $U$, has the point $(0,|U|)$; the
group $\mathsf{bor}$ of highly $\rho$-periodic borders has the points
$(0,d_{r},q)$, where the remainder $d_{r}=|U|\bmod\rho$ is the same for all
$U\in\mathsf{bor}$.) Finally, for general substrings all coordinates are
variable. The _effective dimension_ of a point is the number of its variable
coordinates. Given a pair of groups of substrings, where the first (second)
group has points of _effective_ dimension $d_{1}$ (respectively, $d_{2}$), we
construct for them the $2\mathsf{CNF}$ structure of dimension $d_{1}+d_{2}$.
In order to do this, we replace each involved range with its projection onto
variable coordinates.

##### Building an oracle.

Given a group $\mathsf{pref}$ of not highly periodic (resp., highly periodic)
prefixes, we apply Lemma 3.1 (resp., Lemma 3.2) for every $i\in[n]$. Let
$\mathcal{L}_{1},\ldots\mathcal{L}_{n}$ be the projections of the obtained
ranges onto variable coordinates. A group $\mathsf{suff}$ of suffixes is
processed in the same way, resulting in the ranges
$\mathcal{R}_{1},\ldots,\mathcal{R}_{n}$. Then we apply Lemma 4.1,
constructing the $2\mathsf{CNF}$ structure over the set
$\mathsf{Pairs}=\\{(\mathcal{L}_{1},\mathcal{R}_{1}),\ldots,(\mathcal{L}_{n},\mathcal{R}_{n})\\}$.
This $2\mathsf{CNF}$ thus represents the set
$\mathsf{pref}\times\mathsf{suff}$ of pairs of substrings. We also memorize
the values of fixed coordinates. Iterating over all pairs of prefix and suffix
groups, we obtain the ps-cover part of the oracle.

Given a group $\mathsf{bor}$ of borders, we first determine the reference
position $f_{\mathsf{bor}}$ for groups of substrings and store it. If
$\mathsf{bor}=\\{U\\}$, we use Lemma 2.11 to find all occurrences of $U$ in
$S$ and choose $f_{\mathsf{bor}}$ to be any position not covered by $U$; if
there is no such position, i.e., if $U$ is a 1-cover, we set
$f_{\mathsf{bor}}=\infty$. If $\mathsf{bor}$ is a group of highly
$\rho$-periodic borders, we run a binary search on it, finding the shortest
border $U$ that is not a 1-cover. Then we choose a position $f_{\mathsf{bor}}$
not covered by $U$. Additionally, we store $|U|$. If $U$ does not exist, we
set $f_{\mathsf{bor}}=\infty$. After determining $f_{\mathsf{bor}}$, and only
if it is finite, we build a $2\mathsf{CNF}$ structure similar to the prefix-
suffix case. Iterating over all pairs of border and substring groups (for the
latter, we fix $f=f_{\mathsf{bor}}$), we obtain the bs-cover part of the
oracle.

The time complexity of the construction is dominated by building
$O(\log^{2}n)$ $2\mathsf{CNF}$ structures, each of dimension at most 4 (in the
case where both groups consist of highly periodic strings). By Lemma 4.1, we
get the required $O(n\log^{5}n)$ time bound.

##### Querying an oracle.

Given a pair $(U_{1},U_{2})$ of substrings of $S$, the oracle decides with
$\mathsf{LCP}$ queries, to which of the cases (prefix-suffix, border-
substring, both, or neither) this pair can be attributed, and proceed
accordingly. For prefix, suffix, or border, the oracle finds its group
deciding high periodicity with a query to $\mathsf{IPM}_{S}$ (Lemma 2.13). In
the prefix-suffix case the oracle then create points for $U_{1}$ and $U_{2}$,
“trim” them by dropping fixed coordinates, and query with this pair of trimmed
points the $2\mathsf{CNF}$ structure built for the set
$\mathsf{pref}\times\mathsf{suff}$, where the groups $\mathsf{pref}$ and
$\mathsf{suff}$ contain $U_{1}$ and $U_{2}$ respectively.

Consider the border-substring case (let $U_{1}$ be the border). After
determining the group $\mathsf{bor}$ of $U_{1}$, we check $f_{\mathsf{bor}}$.
If $f_{\mathsf{bor}}=\infty$, the oracle returns True since $U_{1}$ is a
1-cover. The same applies for the case where $f_{\mathsf{bor}}$ is finite,
$\mathsf{bor}$ is highly periodic, and $U_{1}$ is shorter than the saved
length $|U|$. Otherwise, we create the point for $U_{1}$, “trim” it by
dropping fixed coordinates, and create the point for $U_{2}$ using
$f=f_{\mathsf{bor}}$. Then we query with the obtained pair of points the
$2\mathsf{CNF}$ structure built for the pair
$\mathsf{bor}\times\mathsf{sub}_{f}$, where the group $\mathsf{sub}_{f}$
contains $U_{2}$.

Finally, the oracle returns True if it met a condition for “True” in the
border-substring case or if some query made to a $2\mathsf{CNF}$ structure
returned True. Otherwise, the oracle returns False. The query time is
dominated by $O(1)$ queries to $2\mathsf{CNF}$ structures, each of dimension
at most 4. By Lemma 4.1, we get the required $O(\log^{3}n)$ time bound.

As a result, we proved Theorem 1.3. The omitted details can be found in
Appendix D.

##  5 Reporting 2-Covers

A possible, but in general highly inefficient, approach to the All_2-covers
and Shortest_2-cover problems is to construct the oracle of Theorem 1.3 and
query it with every pair (of substrings) that can be in the answer. In this
section, we describe our approach to achieve near-linear running time. In a
high level, we build a fast reporting procedure for “simple” cases and use its
answer to determine the rest of the output with a small number of oracle
queries. To rule out the trivial situation, we assume that all 2-covers
containing a 1-cover are already reported just by listing the 1-covers.

We call a 2-cover $(X,Y)$ _core_ if both substrings $X$ and $Y$ are not highly
periodic. This means that the $2\mathsf{CNF}$ structure for their groups is
built by using only Lemma 3.1, and thus is 2-dimensional. In particular, a
core cover is associated with a 2-dimensional point $(x,y)$. Note that
2-dimensional $2\mathsf{CNF}$ structures represent all core 2-covers (and may
represent some non-core 2-covers as certain highly periodic substrings pass
the restriction on periods in statement 1 of Lemma 3.1). The shortest 2-cover
is core in view of Lemma 2.4.

On the ground level, a $d$-dimensional $2\mathsf{CNF}$ structure stores a set
$\mathcal{R}$ of $O(n)$ $d$-dimensional ranges and checks whether a
$d$-dimensional point, sent as a query, is outside all rectangles. Such a view
inspires the following definition for the case $d=2$ we are interested in.

######  Definition 5.1 (Free Point).

Let $\mathcal{R}$ be a set of rectangles with corners in $[n]^{2}$. A point
$p\in[n]^{2}$ is $\mathcal{R}$-free if $p\notin R$ for every
$R\in\mathcal{R}$.

The following lemma is crucial. For the full proof see Appendix E.

######  Lemma 5.2 (Free Points Reporting).

Let $\mathcal{R}$ be a set consisting of $\Theta(n)$ rectangles with corners
in $[n]^{2}$. There is an algorithm that reports, for the input $\mathcal{R}$,

  * •

all $\mathcal{R}$-free points in $O(n\log^{2}n+\mathsf{output}\cdot\log n)$
time, or

  * •

for each $y\in[n]$, the $\mathcal{R}$-free point $(x,y)$ with minimal $x$ (if
any) in $O(n\log^{2}n)$ time, or

  * •

for an additional input $m\in[n]$, all $\mathcal{R}$-free points $(x,y)$ with
$x+y\leq m$ in time $O(n\log^{2}n+\mathsf{output}\cdot\log(n))$.

The main point of the algorithm of Lemma 5.2 is an efficient reduction of the
2-dimensional problem to its 1-dimensional analog: for each $y\in[n]$, report
all points in the complement of a union of $x$-ranges, corresponding to this
$y$. The algorithm stores the total of $O(n\log n)$ $x$-ranges in an auxiliary
tree $\mathcal{T}$ and associates with each node of $\mathcal{T}$ a version of
the main structure $\mathcal{D}$, which is a variant of persistent lazy
segment tree [27].

To present a solution to the Shortest_2-cover problem, we need the following
claim.

######  Claim 8.

If a point $(x,y)$ is associated with a core 2-cover $(X,Y)$, then
$|X|+|Y|=x+y$ in the prefix-suffix case and $|X|+|Y|=x+y+1+b$ in the border-
substring case with the border of length $b$.

In the prefix-suffix case, $X=S[1..x]$ and $Y=S[n-y+1..n]$. In the border-
substring case, $X=S[1..b]$ and $Y=S[f-x..f+y]$ for some position $f$. The
claim follows.

A solution to Shortest_2-cover is as follows. We build all 2-dimensional
$2\mathsf{CNF}$ structures (Lemma 4.1). For the set $\mathcal{R}$ of each
structure, we run the algorithm of Lemma 5.2 with the second option and choose
the point $(x,y)$ with the minimum sum of coordinates. From this pair we
restore the corresponding 2-cover $(X,Y)$. Due to Claim 8, $(X,Y)$ has the
minimum length among all $2$-covers corresponding to this $2\mathsf{CNF}$
structure. After processing all sets $\mathcal{R}$, we return the $2$-cover of
minimum length among those found.

Since each of $O(\log^{2}n)$ sets $\mathcal{R}$ is computed in $O(n\log n)$
time (Lemma 4.1) and processed in $O(n\log^{2}n)$ time (Lemma 5.2), the time
complexity is $O(n\log^{4}n)$, as required. Theorem 1.2 is proved.

###  5.1 Report All 2-Covers Of Bounded Length

In this section, we overview the proof of Theorem 1.1, focusing on reporting
all ps-covers with length bounded by $m$. The process of reporting all bs-
covers is similar, and the full details are presented in Appendix F.

As a preliminary step, the algorithm constructs the $2$-cover oracle of
Theorem 1.3. The first main step is similar to the proof of Theorem 1.2: the
algorithm computes the set $\mathcal{C}_{m}$ of all core $2$-covers of length
at most $m$ using the third variant of Lemma 5.2.

The remaining task is to report all highly periodic $2$-covers with length
bounded by $m$. This is achieved via an extending procedure based on the
following observation.

Let $(X,Y)$ be a ps-cover of $S$. Let $X_{\mathsf{trim}}=X$ if $X$ is not
highly periodic, or $X_{\mathsf{trim}}=X[1..2\rho+|X|\bmod\rho]$ if $X$ is
highly $\rho$-periodic. Similarly, let $Y_{\mathsf{trim}}=Y$ if $Y$ is not
highly periodic, or $Y_{\mathsf{trim}}=Y[|Y|-2\rho-|Y|\bmod\rho+1..|Y|]$ if
$Y$ is highly $\rho$-periodic.

The pair $(X_{\mathsf{trim}},Y_{\mathsf{trim}})$ is a core $2$-cover of $S$.
The fact that $(X_{\mathsf{trim}},Y_{\mathsf{trim}})$ is a $2$-cover follows
directly from Lemma 2.4, and the fact that it is core is immediate: if $X$ is
not short periodic, so is $X_{\mathsf{trim}}=X$, and if $X$ is highly
periodic, $X_{\mathsf{trim}}$ is its short $\rho$-periodic prefix with the
same length modulo $\rho$. The same analysis applies to $Y$ and
$Y_{\mathsf{trim}}$. Clearly, if the length of $(X,Y)$ is bounded by $m$, we
have $(X_{\mathsf{trim}},Y_{\mathsf{trim}})\in\mathcal{C}_{m}$.

We proceed to describe how to exploit Section 5.1 to report all prefix-suffix
$2$-covers with length bounded by $m$. We process every pair
$(X,Y)\in\mathcal{C}_{m}$. When processing $(X,Y)$, we wish to report all
$2$-covers $(X^{\prime},Y^{\prime})\notin\mathcal{C}_{m}$ with
$|X^{\prime}|+|Y^{\prime}|\leq m$, $X=X^{\prime}_{\mathsf{trim}}$ and
$Y=Y^{\prime}_{\mathsf{trim}}$. Note that such $(X^{\prime},Y^{\prime})$ may
exist only if $X$ or $Y$ is short periodic. Section 5.1 directly implies that
all non-core ps-covers of length at most $m$ are reported in this way. Assume
that $X=S[1..2\rho+d]$ is short $\rho$-periodic and $Y$ is aperiodic. We
initialize an iterator $q=3$, and check if the following conditions hold:

  1. 1.

$q\cdot\rho+d+|Y|\leq m$.

  2. 2.

$X_{q}=S[1..q\cdot\rho+d]$ is $\rho$ periodic.

  3. 3.

the pair $(X_{q},Y)$ is a $2$-cover.

The second condition is checked using Lemma 2.13, and the third condition is
checked via a query to the $2$-cover oracle. If all three conditions are true,
the algorithm reports $(X_{q},Y)$ as a $2$-cover, assigns $q\leftarrow q+1$
and checks the conditions again. Otherwise, the algorithm halts. It is easy to
see that exactly all $2$-covers $(X^{\prime},Y^{\prime})$ such that $(X,Y)$ is
the trimmed version of $(X^{\prime},Y^{\prime})$ are reported this way.

The time complexity is dominated by the queries to the oracle. Each query that
returns True can be charged on the reported $2$-cover. Every query that
returns False can be charged on the original pair $(X,Y)$, as a ’False’
response terminates the algorithm. It follows that the total running time on
every $(X,Y)\in\mathcal{C}_{m}$ is $O(\mathsf{output}\cdot\log^{3}n)$ as
required.

The case in which $X$ is aperiodic and $Y$ is short periodic is completely
symmetrical, and the case in which both are short periodic is treated in a
’nested loop’ fashion: only $X$ is extended until breaking one of the
conditions, and then the process repeats with $Y$ extended by one period, two
periods, and so on. In Appendix F, we show how to appropriately execute this
nested loop in a manner that guaranteed the desired running time.

## References

  * [1] Ali Alatabbi, M. Sohel Rahman, and W. F. Smyth.  Computing covers using prefix tables.  Discret. Appl. Math., 212:2–9, 2016.  URL: https://doi.org/10.1016/j.dam.2015.05.019, doi:10.1016/J.DAM.2015.05.019.
  * [2] Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, and Benny Porat.  Can we recover the cover?  Algorithmica, 81(7):2857–2875, 2019.  URL: https://doi.org/10.1007/s00453-019-00559-8, doi:10.1007/S00453-019-00559-8.
  * [3] Amihood Amir, Avivit Levy, Ronit Lubin, and Ely Porat.  Approximate cover of strings.  Theor. Comput. Sci., 793:59–69, 2019.  URL: https://doi.org/10.1016/j.tcs.2019.05.020, doi:10.1016/J.TCS.2019.05.020.
  * [4] Alberto Apostolico and Andrzej Ehrenfeucht.  Efficient detection of quasiperiodicities in strings.  Theoretical Computer Science, 119(2):247–265, 1993.  URL: https://www.sciencedirect.com/science/article/pii/030439759390159Q, doi:10.1016/0304-3975(93)90159-Q.
  * [5] Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta.  The "runs" theorem.  SIAM J. Comput., 46(5):1501–1514, 2017.  doi:10.1137/15M1011032.
  * [6] Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P. Pissis, and Jakub Radoszewski.  Indexing weighted sequences: Neat and efficient.  Inf. Comput., 270, 2020.  URL: https://doi.org/10.1016/j.ic.2019.104462, doi:10.1016/J.IC.2019.104462.
  * [7] Omer Berkman, Costas S. Iliopoulos, and Kunsoo Park.  The subtree max gap problem with application to parallel string covering.  Inf. Comput., 123(1):127–137, 1995.  URL: https://doi.org/10.1006/inco.1995.1162, doi:10.1006/INCO.1995.1162.
  * [8] Bernard Chazelle.  A functional approach to data structures and its use in multidimensional searching.  SIAM J. Comput., 17(3):427–462, 1988.  doi:10.1137/0217026.
  * [9] Richard Cole, CS Ilopoulos, Manal Mohamed, William F Smyth, and Lu Yang.  The complexity of the minimum k-cover problem.  Journal of Automata, Languages and Combinatorics, 10(5-6):641–653, 2005.
  * [10] Maxime Crochemore and Wojciech Rytter.  Squares, cubes, and time-space efficient string searching.  Algorithmica, 13(5):405–425, 1995.
  * [11] Patryk Czajka and Jakub Radoszewski.  Experimental evaluation of algorithms for computing quasiperiods.  Theoretical Computer Science, 854:17–29, 2021.
  * [12] James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan.  Making data structures persistent.  J. Comput. Syst. Sci., 38(1):86–124, 1989.  doi:10.1016/0022-0000(89)90034-2.
  * [13] Jonas Ellert, Pawel Gawrychowski, and Garance Gourdel.  Optimal square detection over general alphabets.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5220–5242. SIAM, 2023.  URL: https://doi.org/10.1137/1.9781611977554.ch189, doi:10.1137/1.9781611977554.CH189.
  * [14] N. J. Fine and H. S. Wilf.  Uniqueness theorems for periodic functions.  Proc. Amer. Math. Soc., 16:109–114, 1965.
  * [15] Zvi Galil and Raffaele Giancarlo.  Data structures and algorithms for approximate string matching.  Journal of Complexity, 4(1):33–72, 1988.  doi:10.1016/0885-064X(88)90008-8.
  * [16] Pawel Gawrychowski, Jakub Radoszewski, and Tatiana Starikovskaya.  Quasi-periodicity in streams.  In Nadia Pisanti and Solon P. Pissis, editors, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy, volume 128 of LIPIcs, pages 22:1–22:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  URL: https://doi.org/10.4230/LIPIcs.CPM.2019.22, doi:10.4230/LIPICS.CPM.2019.22.
  * [17] Qing Guo, Hui Zhang, and Costas S Iliopoulos.  Computing the $\lambda$-covers of a string.  Information Sciences, 177(19):3957–3967, 2007.
  * [18] Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt.  Fast pattern matching in strings.  SIAM J. Comput., 6(2):323–350, 1977.
  * [19] Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  Fast algorithm for partial covers in words.  Algorithmica, 73(1):217–233, 2015.  URL: https://doi.org/10.1007/s00453-014-9915-3, doi:10.1007/S00453-014-9915-3.
  * [20] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  Optimal data structure for internal pattern matching queries in a text and applications.  CoRR, abs/1311.6235, 2013.  URL: http://arxiv.org/abs/1311.6235, arXiv:1311.6235.
  * [21] Gad M. Landau and Uzi Vishkin.  Fast string matching with k differences.  Journal of Computer and System Sciences, 37(1):63–78, 1988.  doi:10.1016/0022-0000(88)90045-1.
  * [22] Laurentius Leonard and Ken Tanaka.  Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems.  CoRR, abs/2203.16908, 2022.  URL: https://doi.org/10.48550/arXiv.2203.16908, arXiv:2203.16908, doi:10.48550/ARXIV.2203.16908.
  * [23] Dennis Moore and W.F. Smyth.  An optimal algorithm to compute all the covers of a string.  Information Processing Letters, 50(5):239–246, 1994.  URL: https://www.sciencedirect.com/science/article/pii/002001909400045X, doi:10.1016/0020-0190(94)00045-X.
  * [24] Dennis Moore and W.F. Smyth.  A correction to “an optimal algorithm to compute all the covers of a string”.  Information Processing Letters, 54(2):101–103, 1995.  URL: https://www.sciencedirect.com/science/article/pii/002001909400235Q, doi:10.1016/0020-0190(94)00235-Q.
  * [25] Alexandru Popa and Andrei Tanasescu.  An output-sensitive algorithm for the minimization of 2-dimensional string covers.  In T. V. Gopal and Junzo Watada, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13-16, 2019, Proceedings, volume 11436 of Lecture Notes in Computer Science, pages 536–549. Springer, 2019.  doi:10.1007/978-3-030-14812-6\\_33.
  * [26] Jakub Radoszewski and Juliusz Straszyński.  Efficient computation of 2-covers of a string.  In 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [27] Mikhail Rubinchik and Arseny M. Shur.  Counting palindromes in substrings.  In Gabriele Fici, Marinella Sciortino, and Rossano Venturini, editors, String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings, volume 10508 of Lecture Notes in Computer Science, pages 290–303. Springer, 2017.
  * [28] Smyth.  Computing the cover array in linear time.  Algorithmica, 32:95–106, 2002.
  * [29] Dan E. Willard.  New data structures for orthogonal range queries.  SIAM J. Comput., 14(1):232–253, 1985.  doi:10.1137/0214019.
  * [30] Hui Zhang, Qing Guo, and Costas S Iliopoulos.  Algorithms for computing the $\lambda$-regularities in strings.  Fundamenta Informaticae, 84(1):33–49, 2008.

##  Appendix A Figures

Figure 1: Occurrences of $\mathsf{sub}$ in $\mathsf{run}$ (Claim 7). Grey
strip is $\mathsf{run}$, color strips indicate occurrences of $\mathsf{sub}$
(one color for one substring $\mathsf{sub}$). The substrings drawn red, green,
and blue realize, respectively, conditions 1, 3, and 4 of Claim 7. Dash lines
show ranges covered by $\mathsf{sub}$ in each case.

##  Appendix B Missing Proofs

The following two well-known lemmas are useful for the proofs in this section.

######  Lemma B.1 (Fine and Wilf Theorem [14]).

Every string having periods $p,q$ and length at least $p+q-\gcd(p,q)$, has
period $\gcd(p,q)$.

######  Lemma B.2 (Rephrased Three Squares Lemma [10]).

If a string $S$ has periodic prefixes $X$, $Y$, and $Z$ such that
$\mathsf{per}(X)<\mathsf{per}(Y)<\mathsf{per}(Z)$, then
$\mathsf{per}(Z)\geq\mathsf{per}(X)+\mathsf{per}(Y)$.

We complete here all missing proofs of Section 2.

######  Proof B.3 (Proof of Lemma 2.1).

Let $p_{1}<p_{2}<\cdots<p_{\ell}$ be all periods of periodic prefixes of the
string $S[1..n]$. Consider three consecutive values $p_{i},p_{i+1},p_{i+2}$
from this list. By Lemma B.2, $p_{i+2}>2p_{i}$. Since $p_{\ell}\leq n$, we
immediately get $\ell=O(\log n)$ as required.

######  Proof B.4 (Proof of Lemma 2.2).

Let $b_{1}<b_{2}<\cdots<b_{\ell}$ be all different lengths of _aperiodic_
borders of the string $S[1..n]$. Since for every $i\in[1..\ell-1]$ the string
$S[1..b_{i}]$ is a border of $S[1..b_{i+1}]$, $b_{i+1}-b_{i}$ is a period of
$S[1..b_{i+1}]$. Then $(b_{i+1}-b_{i})>b_{i+1}/2$ because of aperiodicity.
Hence $b_{i+1}>2b_{i}$. Since $b_{\ell}\leq n$, we get $\ell=O(\log n)$.

For _short periodic_ borders, a similar argument gives the inequalities
$b_{i+1}>1.5b_{i}$, which also bound the number of borders by $O(\log n)$.

######  Proof B.5 (Proof of Lemma 2.4).

By definition of period, $X[1..|X|-\rho]=Y$ implies $X[\rho+1..|X|]=Y$. Since
$\rho\leq\frac{|X|}{2}$, the string $Y$ covers all indices in $X$ with these
two occurrences. It follows that $Y$ covers every index $i$ in $S$ that is
covered by $X$.

######  Proof B.6 (Proof of Lemma 2.5).

Clearly, an occurrence of a substring of length $\rho$ is contained in at most
one $\rho$-periodic run. Then the first statement of the lemma stems from the
fact that a $\rho$-periodic run covering $i$ contains either $S[i-\rho+1..i]$
or $S[i..i+\rho-1]$ (or both). For the second statement, some work is needed.

With respect to the index $i$, we call a run _left_ (resp., _right_ ,
_central_) if it contains the substring $S[i-2\rho+1..i]$ (resp.,
$S[i..i+2\rho-1]$, $S[i-\rho..i+\rho]$), where $\rho$ is the period of the
run. Every highly-periodic run covering $i$ possesses at least one of these
three properties. By Lemma B.2, the number of right runs is $O(\log n)$; the
dual of Lemma B.2 implies the same result for left runs. Now let $A$ and $B$
be two highly-periodic central runs, with $\rho=\mathsf{per}(A)$,
$\rho^{\prime}=\mathsf{per}(B)$. If neither of $A$, $B$ contains the other
one, then their overlap is of length at least $\rho+\rho^{\prime}$ (otherwise,
one of them is not central). This overlap is a string with periods $\rho$ and
$\rho^{\prime}$, and then has period $\gcd(\rho,\rho^{\prime})$ by Lemma B.1.
Hence $A$ and $B$ are substrings of some $\gcd(\rho,\rho^{\prime})$-periodic
run, contradicting our assumption that $A$ and $B$ are runs. Therefore, one of
$A,B$ contains the other. Without loss of generality, $B$ contains $A$. Then
$\rho\neq\rho^{\prime}$. The string $A$ has periods $\rho$ and $\rho^{\prime}$
but no period $\gcd(\rho,\rho^{\prime})$ (otherwise it is not a
$\rho$-periodic run). Then $|A|<\rho+\rho^{\prime}$ by Lemma B.1; as $|A|\geq
3\rho$, we have $\rho^{\prime}>2\rho$. This immediately implies the $O(\log
n)$ upper bound on the number of central runs. The lemma now follows.

######  Proof B.7 (Proof of Lemma 2.6).

First notice that since $S[i..j]$ is $\rho$ periodic, there is at least one
$\rho$-periodic run containing $S[i..j]$. Assume to the contrary that there
are two different $\rho$-periodic runs $A$ and $B$ containing $S[i..j]$. Since
$A$ and $B$ overlap by a range of length $\rho$, the entire range covered by
$A$ and $B$ is $\rho$-periodic, which contradicts the maximality of $A$ and
$B$.

######  Proof B.8 (Proof of Lemma 2.7).

Assume to the contrary that $S[x..y+1]$ is $\rho^{\prime}$-periodic for some
$\rho^{\prime}$. If $\rho^{\prime}$ is divisible by $\rho$, we have
$S[y+1]=S[y-\rho^{\prime}+1]=S[y-\rho+1]$ where the second equality is due to
the $\mathsf{per}(S[x..y])=\rho$. Then $S[x..y+1]$ is $p$-periodic,
contradicting the condition of the lemma. If $\rho^{\prime}$ is not divisible
by $\rho$, by Lemma B.1 we have that $\mathsf{per}(S[x..y])$ is smaller than
$\rho$, contradicting the definition of $\rho$-periodic.

######  Proof B.9 (Proof of Lemma C.1).

We present a proof for a set of $2$-dimensional ranges, i.e., rectangles. This
proof can be easily generalized for any constant dimension. Consider the
infinite extensions of every side of a rectangle $R\in\mathcal{R}$ to both
directions. Namely, for a rectangle $R=[x_{1}..x_{2}]\times[y_{1}..y_{2}]$,
the infinite extensions of the sides of $R$ are the lines $x=x_{1}$,
$x=x_{2}$, $y=y_{1}$ and $y=y_{2}$. Clearly, the infinite extensions of the
sides of all rectangles in $\mathcal{R}$ partition the plane into
$O(|\mathcal{R}|^{2})=O(1)$ rectangles. Every rectangle in this partition is
either contained in a rectangle of $R$, or is disjoint from all rectangles of
$R$. The set of rectangles in the partition disjoint from all rectangles of
$R$ satisfies the claim. Moreover, this set can be computed in $O(1)$ time
straightforwardly.

##  Appendix C 2CNF Data Structure

In this section we prove Lemma 4.1. We use the following auxiliary lemma to
manipulate $d$-dimensional ranges.

######  Lemma C.1 (Inverse of Ranges).

Let $\mathcal{R}$ be a set of $O(1)$ $d$-dimensional ranges, where $d$ is an
integer constant. There is a set $\overline{\mathcal{R}}$ of $O(1)$
$d$-dimensional ranges such that
$\bigcup_{R\in\overline{\mathcal{R}}}R=[-\infty..\infty]^{d}\setminus\bigcup_{R\in\mathcal{R}}R$.
Moreover, the set $\overline{R}$ can be computed in $O(1)$ time given
$\mathcal{R}$.

See 4.1

######  Proof C.2.

Let $d=d_{\ell}+d_{r}$. We build a set $\mathcal{B}$ of $d$-dimensional
ranges, processing each pair $(\mathcal{L}_{i},\mathcal{R}_{i})$ as follows.
We start with the set $B_{i}$ of $d$-dimensional ranges defined by

$B_{i}=\\{L\times[-\infty..\infty]^{d_{r}}\mid
L\in\mathcal{L}_{i}\\}\cup\\{[-\infty..\infty]^{d_{\ell}}\times R\mid
R\in\mathcal{R}_{i}\\}.$

As $|B_{i}|=|\mathcal{L}_{i}|+|\mathcal{R}_{i}|=O(1)$, we apply Lemma C.1 to
get, in $O(1)$ time, its inverse set of ranges $\overline{B_{i}}$, which is
also of size $O(1)$. Now let $\mathcal{B}=\bigcup_{i\in[n]}\overline{B_{i}}$.

We preprocess the set $\mathcal{B}$ into a range stabbing data structure
(Lemma 2.10). To answer $\mathsf{query}(p_{\ell},p_{r})$, where
$p_{\ell}=(x_{1},\ldots,x_{d_{\ell}})$ and $p_{r}=(y_{1},\ldots,y_{d_{r}})$,
we perform the Existence query to this structure with the $d$-dimensional
point $p=(x_{1},\ldots,x_{d_{\ell}},y_{1},\ldots,y_{d_{r}})$ and report the
negation of the obtained answer. The required time complexities follow from
Lemma 2.10.

##### Correctness.

We need to prove that $p\notin\bigcup_{B\in\mathcal{B}}B$ if and only if for
every $i\in[n]$ either $p_{\ell}\in L$ for some $L\in\mathcal{L}_{i}$ or
$p_{r}\in R$ for some $R\in\mathcal{R}_{i}$.

Let $p\notin\bigcup_{B\in\mathcal{B}}B$ and let $i\in[n]$. By definition of
$\mathcal{B}$, $p\notin\bigcup_{B\in\overline{B_{i}}}B$. Then
$p\in\bigcup_{B\in B_{i}}B$. By definition of $B_{i}$, this implies that
$p_{\ell}\in L$ for some $L\in\mathcal{L}_{i}$ of $p_{r}\in R$ for some
$R\in\mathcal{R}_{i}$.

For the converse note that if $p_{\ell}\in L$ for some $L\in\mathcal{L}_{i}$
of $p_{r}\in R$ for some $R\in\mathcal{R}_{i}$, then $p\in B$ for some $B\in
B_{i}$ and hence $p\notin B^{\prime}$ for all $B^{\prime}\in\overline{B_{i}}$.
If this is the case for all $i$, then $p\notin\bigcup_{B\in\mathcal{B}}B$ by
definition.

##  Appendix D 2-Covers Oracle

In this section, we provide a detailed proof of Theorem 1.3. We distinguish
between two types of $2$-covers. A $2$-cover $(C_{1},C_{2})$ is a prefix-
suffix cover (ps-cover) if $C_{1}$ is a prefix of $S$ and $C_{2}$ is a suffix
of $S$ (or vice versa). A $2$-cover is a border-substring cover (bs-cover) if
$C_{1}$ is a border of $S$ and $C_{2}$ is a substring of $S$ (or vice versa).
Note that every $2$-cover can be classified into one of these two types. More
specifically, the oracle queries each data structure twice: once for
$(C_{1},C_{2})$ and once for $(C_{2},C_{1})$.

Our data structure consists of two independent data structures, one for
checking if $(C_{1},C_{2})$ is a prefix-suffix cover, and one for checking if
it is a border-substring cover. When receiving a query, the data structure
checks both options and answers accordingly.

##### Common Preprocess.

In both data structures, the following preprocess on $S$ is applied in
addition to the preprocessing phase described in Section 3. The algorithm
constructs an interval stabbing data structure $D^{s}_{hp}$ that contains an
interval $[i..j]$ for every highly periodic run $S[i..j]$ in $S$ using Lemma
2.10. This preprocess takes $O(n\log^{2}n)$ time.

###  D.1 Prefix-Suffix Oracle

In this section, we describe the oracle checking if
$(U_{1},U_{2})=(S[1..p],S[x..y])$ is a ps-cover.

##### Construction.

We partition prefixes and suffixes into _groups_. The groups
$\mathsf{pper}(\rho)$ and $\mathsf{sper}(\rho)$ consist of all highly
$\rho$-periodic prefixes (resp., suffixes). The groups $\mathsf{paper}(k)$ and
$\mathsf{saper}(k)$ consist of all not highly periodic prefixes (resp.,
suffixes) that have length in the range $[1.5^{k}..1.5^{k+1}]$. Let

$\displaystyle\mathcal{P}$ $\displaystyle=\\{\mathsf{paper}(k)\mid 1.5^{k}\leq
n\\}\cup\\{\mathsf{pper}(\rho)\mid\rho\text{ is a prefix period}\\},$
$\displaystyle\mathcal{S}$ $\displaystyle=\\{\mathsf{saper}(k)\mid 1.5^{k}\leq
n\\}\cup\\{\mathsf{sper}(\rho)\mid\rho\text{ is a suffix period}\\}.$

As the number of prefix/suffix periods is $O(\log n)$ by Lemma 2.1, one has
$|\mathcal{P}|,|\mathcal{S}|\in O(\log n)$.

The algorithm processes each pair
$(\mathsf{pref},\mathsf{suff})\in\mathcal{P}\times\mathcal{S}$ as follows.

  * •

If $\mathsf{pref}=\mathsf{paper}(k)$, it uses, for every $i\in[n]$, Lemma 3.1
with parameters $f=1$, $i$, and $k$ to build a set of rectangles
$\mathcal{R}_{i}$. From the construction given in Claim 1 we see that each
rectangle in $\mathcal{R}_{i}$ has the form $R=[0..0]\times[r_{1}..r_{2}]$,
and every prefix in $\mathsf{paper}(k)$ is associated with a point of the form
$p=(0,r)$. Then the inclusion $p\in R$ is decided solely from the second
coordinates. We refer to the first coordinate as _fixed_ and we drop it to
reduce the dimension. We thus define $\mathcal{P}_{i}$ to be the set of
projections of all rectangles from $\mathcal{R}_{i}$ to the second coordinate.

  * •

If $\mathsf{pref}=\mathsf{pper}(\rho)$, it uses, for every $i\in[n]$, Lemma
3.2 with parameters $f=1$, $i$, and $\rho$ to build a set of cuboids
$\mathcal{C}_{i}$. Similar to the previous case we know that each
$R\in\mathcal{R}_{i}$ has the first range $[0..0]$ and every prefix in
$\mathsf{pper}(\rho)$ is associated with a point having zero first coordinate.
Accordingly, we drop the fixed first coordinate and define $\mathcal{P}_{i}$
as the set of projections, to the last two coordinates, of all cuboids from
$\mathcal{C}_{i}$.

The sets $\mathcal{S}_{i}$ are defined in a symmetric way from
$\mathsf{suff}$; here we drop the fixed second coordinate.

Thus, the algorithm obtain the set
$\mathsf{Pairs}=\\{(\mathcal{P}_{1},\mathcal{S}_{1}),(\mathcal{P}_{2},\mathcal{S}_{2}),\ldots,(\mathcal{P}_{n},\mathcal{S}_{n})\\}$
and builds a $2\mathsf{CNF}$ data structure
$\mathsf{CNF}_{\mathsf{pref},\mathsf{suff}}$ of Lemma 4.1 for the set
$\mathsf{Pairs}$ with the following dimensions:

$d_{\ell}=\begin{cases}1&\text{if }\mathsf{pref}=\mathsf{paper}(k)\\\
2&\text{if }\mathsf{pref}=\mathsf{pper}(\rho)\end{cases}\text{ and
}d_{r}=\begin{cases}1&\text{if }\mathsf{suff}=\mathsf{saper}(k)\\\ 2&\text{if
}\mathsf{suff}=\mathsf{sper}(\rho)\end{cases}.$

##### Query.

For a query $(S[1..p],S[x..y])$ the algorithm first verifies that $S[x..y]$ is
a suffix of $S$ by checking if $\mathsf{LCP}^{R}(y,n)\geq y-x+1$. If it is not
a suffix, the oracle answers False. Otherwise, the algorithm queries the
$\mathsf{IPM}_{S}$ data structure (Lemma 2.13) with Periodic($S[1..p]$). If
the answer is “aperiodic” or a number $\rho>p/3$, the prefix is not highly
periodic. So the algorithm computes $k=\left\lfloor{\log_{1.5}p}\right\rfloor$
and sets $\mathsf{pref}=\mathsf{paper}(k)$ and $p_{\ell}=(p-1)$ (recall that
the first coordinate is dropped!). Otherwise, the prefix is highly
$\rho$-periodic. In this case, the algorithm sets
$\mathsf{pref}=\mathsf{pper}(\rho)$ and $p_{\ell}=(d_{r},q_{r})$ for the
integers $d_{r}\in[0..\rho-1]$ and $q_{r}$ such that $p=q_{r}\cdot\rho+d_{r}$.
Similarly, the algorithm queries $\mathsf{IPM}_{S}$ with Periodic($S[x..y]$).
If $S[x..y]$ is not highly periodic, the algorithm computes
$k=\left\lfloor{\log_{1.5}(y-x+1)}\right\rfloor$ and sets
$\mathsf{suff}=\mathsf{saper}(k)$ and $p_{r}=(y-x)$. Otherwise, it is highly
$\rho$-periodic, and the algorithm sets $\mathsf{suff}=\mathsf{sper}(\rho)$
and $p_{r}=(d_{\ell},q_{\ell})$ for the integers $d_{\ell}\in[0..\rho-1]$ and
$q_{\ell}$ such that $y-x+1=q_{\ell}\cdot\rho+d_{\ell}$. Finally, the
algorithm queries the structure $\mathsf{CNF}_{\mathsf{pref},\mathsf{suff}}$
with the pair of points $(p_{\ell},p_{r})$ and returns the obtained answer.

##### Complexity.

The preprocessing phase takes $O(n\log^{2}n)$ time. The periods of highly
periodic prefixes and these prefixes themselves can be found in $O(n)$ time by
$O(n)$ $\mathsf{LCP}$ queries $\mathsf{LCP}_{S}(S[1..n],S[\rho+1..n])$. Highly
periodic suffixes are operated in a symmetric way. For each pair
$(\mathsf{pref},\mathsf{suff})$, the algorithm iterates every $i\in[n]$ and
applies Lemma 3.1 or Lemma 3.2, which takes $O(n\log^{2}n)$ time. Then, the
algorithm constructs a 2$\mathsf{CNF}$ data structure of dimension
$d_{\ell}+d_{r}\leq 2+2=4$, which takes $O(n\log^{3}n)$ time by Lemma 4.1.
Summing over $O(\log^{2}n)$ distinct pairs $(\mathsf{pref},\mathsf{suff})$, we
get the total running time of $O(n\log^{5}n)$.

The query complexity is dominated by a single query to a $2\mathsf{CNF}$ data
structure with $d_{\ell}+d_{r}\leq 4$, which requires $O(\log^{3}n)$ time by
Lemma 4.1.

##### Correctness.

By definition, $(S[1..p],S[x..y])$ is a $2$-cover of $S$ if and only if for
every $i$ we have $(S[1..p],S[x..y])$ covers $i$. Denote by
$\mathsf{Cover}_{i}$ the event in which either $p_{\ell}$ is in some range of
$\mathcal{P}_{i}$ or $p_{r}$ is in some range of $\mathcal{S}_{i}$ (where
$\mathcal{S}_{i}$ and $\mathcal{P}_{i}$ refer to the sets used in the
construction of $\mathsf{CNF}_{\mathsf{pref},\mathsf{suff}}$). According to
Lemmas 3.1 and 3.2, and our rule on dropping coordinates, an index $i$ is
covered by $(S[1..p],S[x..y])$ if and only if $\mathsf{Cover}_{i}$ occurs. It
immediately follows that $(S[1..p],S[x..y])$ is a $2$-cover if and only if
$\mathsf{Cover}_{i}$ occurs for every $i\in[n]$. This is exactly the output of
the $2\mathsf{CNF}$ query, as required.

###  D.2 Border-Substring Oracle

In this section, we describe the oracle checking if
$(U_{1},U_{2})=(S[1..p],S[x..y])$ is a bs-cover.

##### Construction.

Similar to the prefix-suffix case, we partition borders into groups. A group
$\mathsf{bor}(\rho)$ consists of all highly $\rho$-periodic borders. Each
border that is not highly periodic, forms a separate group. By Lemmas 2.1 and
2.2 the number of groups is $O(\log n)$.

With every group $\mathsf{bor}$ of borders, the algorithm associates the
reference position $f_{\mathsf{bor}}$ for the groups of substrings that will
be considered with this group of borders. If $\mathsf{bor}=\\{U\\}$, the
algorithm uses Lemma 2.11 to find all occurrences of $U$ in $S$ and chooses
$f_{\mathsf{bor}}$ to be any position not covered by $U$; if there is no such
position, i.e., if $U$ is a 1-cover, it sets $f_{\mathsf{bor}}=\infty$. If
$\mathsf{bor}=\mathsf{bor}(\rho)$, the algorithm runs a binary search on
$\mathsf{bor}$, finding the shortest border $U\in\mathsf{bor}(\rho)$ that is
not a 1-cover. This requires $O(n\log n)$ time as it uses Lemma 2.11 $O(\log
n)$ times. Then the algorithm chooses a position $f_{\mathsf{bor}}$ not
covered by $U$ and additionally stores $q_{\mathsf{bor}}=|U|$. If $U$ does not
exist, it sets $f_{\mathsf{bor}}=\infty$.

Let $f\in[n]$ be an index. We define the sets $\mathsf{subaper}_{f}(k)$ and
$\mathsf{subper}_{f}(\rho)$ in an analogous manner to the sets
$\mathsf{paper}(k)$ and $\mathsf{pper}(\rho)$. For an integer $k$, we define

$\displaystyle\mathsf{subaper}_{f}(k)=\\{S[f-\ell..f+r]\mid r,\ell\geq
0\textit{ , }S[f-\ell..f+r]\textit{ is aperiodic, and
}\ell+r-1\in[1.5^{k}..1.5^{k+1})\\}$

For an integer $\rho$, we define

$\displaystyle\mathsf{subper}_{f}(\rho)=\\{S[f-\ell..f+r]\mid r,\ell\geq
0\textit{ and }S[f-\ell..f+r]\textit{ is highly }\rho\textit{-periodic}\\}$

Note that every substring of $S$ that covers the index $f$ is either contained
in $\mathsf{subaper}_{f}(k)$ for some value of $k$, or in
$\mathsf{subper}_{f}(\rho)$ for some value of $\rho$. The set
$\mathcal{S}_{f}$ (analogous to $\mathcal{P}$ and $\mathcal{S}$) is defined as

$\displaystyle\mathcal{S}_{f}=\\{\mathsf{subaper}_{f}(k)\mid 1.5^{k}\leq
n\\}\cup\\{\mathsf{subper}_{f}(\rho)\mid\mathsf{subper}_{f}(\rho)\neq\emptyset\\}$

Note that for a period $\rho$, every substring in $\mathsf{subper}_{f}(\rho)$
is contained in a highly $\rho$-periodic run that contains $f$. It follows
from Lemma 2.5, that $|\mathcal{S}_{f}|\in O(\log n)$.

The algorithm iterates over all pairs $(\mathsf{bor},\mathsf{sub})$ where
$\mathsf{bor}\in\mathcal{B}$ and
$\mathsf{sub}\in\mathcal{S}_{f_{\mathsf{bor}}}$ (If $f_{\mathsf{bor}}=\infty$,
we treat $\mathcal{S}_{f_{\mathsf{bor}}}$ as $\emptyset$). Once again, there
will be two fixed coordinates, but now both of them come from the border’s
side. As the border is both a prefix (having fixed first coordinate) and a
suffix (having fixed second coordinate), it has the first two coordinates
fixed.

Consider processing of one pair $(\mathsf{bor},\mathsf{sub})$. It results in
creation of the set
$\mathsf{Pairs}=\\{(\mathcal{B}_{1},\mathcal{S}_{1}),(\mathcal{B}_{2},\mathcal{S}_{2}),\ldots,(\mathcal{B}_{n},\mathcal{S}_{n})\\}$,
which is then used to create a $2\mathsf{CNF}$ structure of Lemma 4.1. If
$\mathsf{bor}=\\{U\\}$, the algorithm applies Lemma 2.11 to find the all
indices in $S$ that are covered by $U$. For each $i\in[n]$, we have a
“0-dimensional” interval, which is just a boolean value indicating whether
this position is covered by $U$ or not. However, it is more convenient to
represent it as a 1-dimensional interval, setting
$\mathcal{B}_{i}=\\{[-\infty..\infty]\\}$ if $i$ is covered and
$\mathcal{B}_{i}=\varnothing$ if it is not. If
$\mathsf{bor}=\mathsf{bor}(\rho)$, the algorithm constructs for every
$i\in[n]$ the set of cuboids $\mathcal{C}_{i}$, drops the first two
coordinates that are fixed, and sets $\mathcal{B}_{i}$ to be the set of
obtained intervals. (In fact, this set is always a single interval in view of
Lemma 2.4.) For the group $\mathsf{sub}$ we use Lemma 3.1 or Lemma 3.2
depending on periodicity, and store the results as the sets $\mathcal{S}_{i}$.
The dimensions of the $2\mathsf{CNF}$ data structure constructed from
$\mathsf{Pairs}$ are

$d_{\ell}=\begin{cases}1&\text{if }\mathsf{bor}=\\{U\\}\\\ 1&\text{if
}\mathsf{bor}=\mathsf{bor}(\rho)\end{cases}\text{ and
}d_{r}=\begin{cases}2&\text{if }\mathsf{sub}\text{ is not highly periodic }\\\
3&\text{if }\mathsf{sub}\text{ is highly periodic }\end{cases}.$

##### Query.

For a query $(S[1..b],S[x..y])$, the algorithm verifies that $U=S[1..b]$ is a
border by checking if $\mathsf{LCP}_{S}^{R}(b,n)=b$. If this is not the case,
the oracle answers False. Otherwise, the algorithm checks if $U$ is highly
periodic by querying $\mathsf{IPM}_{S}$. If it is not, the algorithm sets
$\mathsf{bor}=\\{U\\}$ and checks if $f_{\mathsf{bor}}=\infty$. If
$f_{\mathsf{bor}}=\infty$, the algorithm returns True. Otherwise, it creates a
$1$-dimensional point $p_{\ell}=(0)$.

If $U$ is highly $\rho$-periodic, the algorithm defines
$\mathsf{bor}=\mathsf{bor}(\rho)$, and checks if $f_{\mathsf{bor}}=\infty$ or
$q_{\mathsf{bor}}>|U|$. If this is the case, the algorithm returns True.
Otherwise, it sets $|U|=q\rho+d$ with the unique integers and
$d\in[0..\rho-1]$ and $q$. The algorithm then creates the point $(0,d,q)$ and
trims it to $p_{\ell}=(q)$ as the first two coordinates are fixed.

Now the algorithm works with $f=f_{\mathsf{bor}}$ (which is finite). It
queries $\mathsf{IPM}_{S}$ to check if there is an occurrence of $V=S[x..y]$
that covers $f$. Technically, the algorithm queries
$\mathsf{IPM}_{S}(S[f-|V|+1..f+|V|-1],V)$ and checks if the output is empty.
If there is no such occurrence, the algorithm returns False. Otherwise, the
algorithm picks an arbitrary occurrence $i_{V}$ of $V$ covering $f$ and
computes the integers $\ell$ and $r$ such that $V=S[f-\ell..f+r]$.

Next, the algorithm checks if $V$ is highly periodic by querying
$\mathsf{IPM}_{S}$. Getting the result, it chooses the appropriate group
$\mathsf{sub}$ for $V$ and creates a point for $V$. If $V$ is not highly
periodic, the point is $p_{r}=(\ell,r)$. If $V$ is highly $\rho$-periodic then
the algorithm defines $\mathsf{root}$ and computes the point
$p_{r}=(d_{\ell},d_{r},q_{\ell,r})$ for $V$ such that $V=\mathsf{root}[\rho-
d_{\ell}+1..\rho]\cdot\mathsf{root}^{q_{\ell,r}}\cdot\mathsf{root}[1..d_{r}]$.
Finally, the algorithm queries the
$2\mathsf{CNF}_{(\mathsf{bor},\mathsf{sub})}$ data structure with the point
$(p_{\ell},p_{r})$ and returns the answer obtained for this query.

##### Complexity.

As in the prefix-suffix case, the construction time is dominated by the amount
needed to build $2\mathsf{CNF}$ structure (all the rest is within
$O(n\log^{2}n)$ bound). As this structure is at most 4-dimensional, we get the
$O(n\log^{3}n)$ bound from Lemma 4.1. Since the number of such structures the
algorithm builds for different pairs of groups is $O(\log^{2}n)$, the total
construction time is $O(n\log^{5}n)$.

A query consists of a constant number of $\mathsf{LCP}$ queries,
$\mathsf{IPM}$ queries, and arithmetic operations. The algorithm also applies
a single query to a $2\mathsf{CNF}$ data structure, which takes $O(\log^{3}n)$
time due to Lemma 4.1.

##### Correctness.

We claim that the query returns the correct answer to the question “Is
$(S[1..b],S[x..y])$ a border-substring cover?”. If the algorithm returns False
due to $S[1..b]$ not being a border, this is obviously correct. Assume that
$U=S[1..b]$ is a border and let $\mathsf{bor}$ be its group. If the query
returns True due to $f_{\mathsf{bor}}=\infty$ or Let $|U|<q_{\mathsf{bor}}$,
then $U$ is a 1-cover, and then forms a 2-cover with any substring.

In the remaining case the query returns the same answer as the $2\mathsf{CNF}$
data structure built for the groups of $U$ and $S[x..y]$. Here the analysis is
similar to the prefix-suffix case, so we omit it.

##  Appendix E Free Points Data Structure

In this section, we prove Lemma 5.2. In the proof of Lemma 5.2 we use the
concept of _persistent data structure_ [12]. A data structure is persistent if
it supports multiple versions of itself and allows quick access to any version
for querying, deletion, or update (an update creates a new version).

We first recall the definition of a free point and the statement of Lemma 5.2.
See 5.1

See 5.2

######  Proof E.1.

The main point of the algorithm is an efficient reduction of the 2-dimensional
problem to its 1-dimensional analog. The algorithm uses an auxiliary tree
$\mathcal{T}$ and the main structure $\mathcal{D}$, which is a variant of
persistent lazy segment tree [27]. The details are described below.

We take a fully balanced binary tree with $2^{\left\lceil{\log
n}\right\rceil}$ leaves and delete $2^{\left\lceil{\log n}\right\rceil}-n$
rightmost leaves together with all internal nodes having no leaves remained in
their subtrees. The remaining leaves are enumerated from $1$ to $n$ in a
natural order. Thus, the leaves in a subtree of every node form a sub-range of
$[n]$; we use these ranges as names of nodes. The only data stored in a node
is the links $.\mathit{left}$ and $.\mathit{right}$ to its children. We refer
to the obtained tree $\mathcal{T}_{0}$ as the _blank_ tree. It is used to
construct both $\mathcal{T}$ and $\mathcal{D}$.

Building $\mathcal{T}$ from $\mathcal{T}_{0}$, we interpret each leaf as the
$y$-coordinate of a point in $[n]^{2}$; the leaf $k$ corresponds to all points
$(x,y)\in[n]^{2}$ with $y=k$. The algorithm processes each rectangle
$R\in\mathcal{R}$, adding the information about its $x$-range to the nodes of
$\mathcal{T}_{0}$. Precisely, a rectangle $[x_{1}..x_{2}]\times[y_{1}..y_{2}]$
is fed to the following recursive procedure, starting at the root $[n]$ of
$\mathcal{T}_{0}$:

  * •

for the current node $[y^{\prime}..y^{\prime\prime}]$:

    * –

if $[y^{\prime}..y^{\prime\prime}]\cap[y_{1}..y_{2}]=\varnothing$, stop;

    * –

if $[y^{\prime}..y^{\prime\prime}]\subseteq[y_{1}..y_{2}]$, add the range
$[x_{1}..x_{2}]$ to $[y^{\prime}..y^{\prime\prime}]$ and stop;

    * –

otherwise, call the procedure for both children of
$[y^{\prime}..y^{\prime\prime}]$.

A well-known observation says that the procedure is called for at most $4$
nodes at each level of $\mathcal{T}_{0}$. Therefore, each rectangle is
processed in $O(\log n)$ time and adds $O(\log n)$ to the space used by
$\mathcal{T}_{0}$. After processing all rectangles from $\mathcal{R}$ in
$O(n\log n)$ time, the resulting tree is $\mathcal{T}$. This tree stores
stores $O(n\log n)$ information.

######  Claim 9.

A point $(x,y)$ is $\mathcal{R}$-free if and only if $x$ does not belong to
any $x$-range stored in a node on the path from the root of $\mathcal{T}$ to
the leaf $y$.

Note that the algorithm partitions each rectangle $R\in\mathcal{R}$ into a set
of $O(\log n)$ disjoint “new” rectangles with the same $x$-range such that the
$y$-ranges of these rectangles correspond to some nodes of $\mathcal{T}$. Then
a point is $\mathcal{R}$-free if and only if it is not contained in any of the
new rectangles. Each node $[y_{1}..y_{2}]$ stores all new rectangles of the
form $[x_{1}..x_{2}]\times[y_{1}..y_{2}]$. Hence, the nodes on the path from
the root to $y$ store all new rectangles containing $y$ in their $y$-range.
Then $(x,y)$ is $\mathcal{R}$-free if and only if $x$ is out of all $x$-ranges
stored in these nodes. By Claim 9, to report all free points it suffices to
find, for each $y\in[n]$, the complement of the union of all $x$-ranges stored
in the nodes on the path from the root of $\mathcal{T}$ to the leaf $y$. First
we describe how to compute the complement of the union of a fixed set
$\mathcal{X}$ of $x$-ranges.

##### Solution for the $1$-dimensional case.

The algorithm starts with $\mathcal{T}_{0}$, associates each leaf with the
$x$-coordinate of a point, and processes ranges from $\mathcal{X}$ one by one.
Each node $[x_{1}..x_{2}]$ stores a single value $[x_{1}..x_{2}].f$, which is
the number of points from $[x_{1}..x_{2}]$ that are not contained in already
processed ranges. When all ranges are processed, points in
$\overline{X}=[n]\setminus\bigcup_{X\in\mathcal{X}}X$ are reported. We assume
that the algorithm reports _all_ points, and consider the other two options
stated in the lemma in the end of the proof. Reporting is made during a
partial depth-first traversal of the obtained tree
$\mathcal{T}_{\mathcal{X}}$. This traversal skips subtrees rooted at zero-
valued nodes and thus visits only $O(|\overline{X}|\log n)$ nodes, including
$|\overline{X}|$ leaves. Hence the reporting costs $O(|\overline{X}|\log
n)=O(\mathsf{output}\cdot\log n)$ time. Let us describe the processing phase.

The value of a node is initialized as the number of points in its range. The
call $\mathsf{Add}([n],X)$ is then performed for each $X\in\mathcal{X}$, where
the recursive function $\mathsf{Add}$ is defined as follows.

  * •

$\mathsf{Add}(\mathsf{node}\ [x_{1}..x_{2}],\mathsf{range}\ X):$

    * –

If $[x_{1}..x_{2}]\subseteq X$, set $[x_{1}..x_{2}].f=0$

    * –

If $[x_{1}..x_{2}]\cap X\neq\varnothing$ and $[x_{1}..x_{2}].f>0$, set
$[x_{1}..x_{2}].f=\mathsf{Add}([x_{1}..x_{2}].\mathit{left})+\mathsf{Add}([x_{1}..x_{2}].\mathit{right})$

    * –

Return $[x_{1}..x_{2}].f$

If a value $[x_{1}..x_{2}].f$ equals $|[n]\setminus(X_{1}\cup\cdots\cup
X_{k})|$ after processing the ranges $X_{1},\ldots,X_{k}$, we call it
_correct_. The following claim proves correctness of values in all nodes
traversed during the reporting phase.

######  Claim 10.

After any sequence of calls
$\mathsf{Add}([n],X_{1}),\ldots,\mathsf{Add}([n],X_{k})$, every node
$[x_{1}..x_{2}]\in\mathcal{T}_{\mathcal{X}}$ has either a correct value or a
zero-valued proper ancestor.

The proof is by induction on $k$. The initialization of values proves the base
case. For the step case, assume that the claim is true after processing
$X_{i}$ and consider the call $\mathsf{Add}([n],X_{i+1})$. Since zero values
never change and the recursion does not reach below a zero-valued node, it is
sufficient to consider an arbitrary node $[x_{1}..x_{2}]$ with nonzero values
in it and in all its ancestors. If $[x_{1}..x_{2}]\subseteq X_{i+1}$, then the
value of either this node or one of its ancestors is correctly set to $0$
during the call. If $[x_{1}..x_{2}]\cap X_{i+1}=\varnothing$, the value
$[x_{1}..x_{2}].f$ remains unchanged which is correct by the inductive
hypothesis. In both cases, the step case holds. In the remaining case, the
value $[x_{1}..x_{2}].f$ was set to the sum of the values of its children. If
an incorrect value was assigned, then _earlier_ during the call another
incorrect value was assigned to a child of $[x_{1}..x_{2}]$. But if an
incorrect assignment is necessarily preceded by another incorrect assignment,
then no incorrect assignment can happen. Hence, all values set as the sums of
their children’s values are assigned correctly. The step case is proved. By
Claim 10, in the reporting phase the algorithm meets only correct values and
thus correctly reports the set $\overline{}X$. During the call
$\mathsf{Add}([n],X)$, at most $4$ nodes at each level are touched. Thus, each
range $X\in\mathcal{X}$ is processed in $O(\log n)$ time, and the whole
processing phase requires $O(|\mathcal{X}|\log n)$ time.

##### Processing of all $x$-ranges stored in $\mathcal{T}$.

For a node $t\in\mathcal{T}$, let $\mathcal{X}_{t}$ be the set of $x$-ranges
stored in all nodes on the path from the root to $t$. The algorithm traverses
$\mathcal{T}$ depth first, creating the tree $\mathcal{T}_{\mathcal{X}_{t}}$
on the first visit to $t$ and deleting it on the last visit. When $t=y$ is a
leaf, the reporting phase is run for $\mathcal{T}_{\mathcal{X}_{y}}$, during
which $\mathcal{R}$-free points with the second coordinate $y$ are reported.
In order to save space and construction time, the trees
$\mathcal{T}_{\mathcal{X}_{t}}$ are built and stored as versions of a
persistent data structure $\mathcal{D}$.

Let us briefly explain how it works. We first build the tree
$\mathcal{T}_{\mathcal{X}_{[n]}}$, processing all ranges stored in the root of
$\mathcal{T}$. To every node of this tree we assign its _version index_ ,
equal to 0; version 0 is now the _current version_. Then we start a depth-
first traversal of $\mathcal{T}$, adding and deleting versions as follows.

The index of the current version is always the depth of the _currently
traversed node_ of $\mathcal{T}$. To _copy_ a node $v$ means to create a new
node $v^{\prime}$ with $v^{\prime}.\mathit{left}=v.\mathit{left}$,
$v^{\prime}.\mathit{right}=v.\mathit{right}$, $v^{\prime}.f=v.f$, and
$v^{\prime}.\mathit{version}$ being the current version. Reaching node
$t^{\prime}$ from its parent $t$, we create a new version as follows. We copy
the root $v$ of the version $\mathcal{T}_{\mathcal{X}_{t}}$ into $v^{\prime}$.
Now we can navigate $\mathcal{T}_{\mathcal{X}_{t}}$ using the root
$v^{\prime}$ instead of $v$. Starting from $v^{\prime}$, we process all ranges
stored in $t^{\prime}$ with with a simple modification of the function
$\mathsf{Add}(\cdot,\cdot)$. This modification, when calling to a child $x$ of
the currently processed node $u$, checks if $x.\mathit{version}$ is current;
if not, it copies $x$ to $x^{\prime}$, updates the link of $u$ from $x$ to
$x^{\prime}$, and then runs the recursive call for $x^{\prime}$. When all
ranges stored in $t^{\prime}$ are processed, we have the tree
$\mathcal{T}_{\mathcal{X}_{t^{\prime}}}$ with the root $v^{\prime}$.

When visiting $t$ for the last time, the algorithm deletes all nodes of the
current version, starting from the root. The time spent for all deletions in
the same as for all creations of new copies, so we can ignore it. Note that at
every moment all existing versions correspond to the nodes on the path from
the root to the current node of $\mathcal{T}$. In particular, all version
indices are different. In order to return to the previous version after
deleting the current one, it suffices to store all roots in an array of
version indices.

Every call to the modified function $\mathsf{Add}([n],\cdot)$ still takes
$O(\log n)$ time as in the original implementation, since what we added is
just $O(1)$ copying operations per level of the tree (recall that at most 4
nodes per level of the tree are touched during this call). As $\mathcal{T}$
contains $O(n\log n)$ ranges, and each range is added to $\mathcal{D}$ only
once, the processing time is $O(n\log^{2}n)$. As every two reporting phases
output disjoint sets of points, the reporting costs
$O(n+\mathsf{output}\cdot\log n)$ time. This gives the time bounds stated in
the lemma.

It remains to consider the other two modes of reporting: report the minimal
$x$ for each $y$ and report all pairs with $(x+y)\leq m$. As we traverse the
leaves of any tree $\mathcal{T}_{\mathcal{X}}$ in increasing order, we just
stop the depth-first traversal of the reporting phase at the moment when all
required pairs $(x,y)$ with the given $y$ are reported. Thus, the reporting
costs the same $O(n+\mathsf{output}\cdot\log n)$ time as in the general case.
If we report at most one $x$ for each $y$, then $\mathsf{output}=O(n)$. The
lemma is proved.

##  Appendix F Reporting All 2-Covers Up To A Given Length

In this section, we prove Theorem 1.1. The algorithm operates in two phases.
First, the algorithm reports all non-highly periodic $2$-covers (see Section
F.1). Then, the algorithm uses the non-highly periodic $2$-covers to find all
the highly periodic covers (see Section F.2).

###  F.1 Report All Non-Highly Periodic 2-Covers

In this section we prove the following lemma.

######  Lemma F.1.

Let $S$ be a string. There exists an algorithm that reports all non-highly
periodic $2$-covers of $S$ (and may report also some highly periodic
$2$-covers as well) in $O(n\log^{4}n+\mathsf{output}\cdot\log n)$ time.

We split the proof of Lemma F.1 into two parts, one for reporting prefix-
suffix $2$-covers, and one for reporting border-substring $2$-covers.

####  F.1.1 Report All Non-Highly Periodic Prefix-Suffix 2-Covers

The following lemma is useful in this section. In essence, we claim that the
dimension of the ranges of Lemma 3.1 are actually $1$ (and not $2$) in the
case in which $f$ is an endpoint of $S$.

######  Lemma F.2.

Let $i\in[n]$ be an index and let $k\in\mathbb{N}$. There exists a set
$\mathcal{I}_{\ell}$ of $O(1)$ intervals such that for any $z\in\mathbb{N}$
where $\mathsf{pref}=S[1..1+z]$ has $z\in[1.5^{k}..1.5^{k+1}]$ we have:

  1. 1.

If $z\in\bigcup_{I\in\mathcal{I}_{\ell}}I$, then $\mathsf{pref}$ covers $i$.

  2. 2.

If $\mathsf{pref}$ is a non-highly periodic string covering $i$, then
$z\in\bigcup_{I\in\mathcal{I}_{\ell}}I$.

Symmetrically, there exists a set $\mathcal{I}_{r}$ of $O(1)$ intervals such
that for any $z\in\mathbb{N}$ where $\mathsf{suff}=S[n-z..n]$ has
$z\in[1.5^{k}..1.5^{k+1}]$ we have:

  1. 1.

If $z\in\bigcup_{I\in\mathcal{I}_{r}}I$, then $\mathsf{suff}$ covers $i$.

  2. 2.

If $\mathsf{suff}$ is a non-highly periodic string covering $i$, then
$z\in\bigcup_{I\in\mathcal{I}_{r}}I$.

Moreover, $\mathcal{I}_{\ell}$ and $\mathcal{I}_{r}$ can be computed in
$O(\log^{2}n)$ time.

######  Proof F.3.

We use Lemma 3.1 with $f=1$, $i$ and $k$ to obtain a set $\mathcal{R}_{\ell}$
of rectangles. Let
$\mathcal{I}_{\ell}=\\{[a..b]\mid[c..d]\times[a..b]\in\mathcal{R}\textit{ and
}0\in[c..d]\\}$. We use again Lemma 3.1 with $f=n$, $i$ and $k$ to obtain a
set $\mathcal{R}_{r}$ of rectangles. Let
$\mathcal{I}_{r}=\\{[a..b]\mid\exists_{c}[a..b]\times[c..d]\in\mathcal{R}\textit{
and }0\in[c..d]\\}$.

Note that every point $(\ell,r)$ such that $S[1-\ell..1+r]=S[1..1+z]$ must
have $\ell=0$ and $z=r$. Therefore, $z\in\bigcup_{I\in\mathcal{I}}I$ if and
only if $(0,z)\in\bigcup_{R\in\mathcal{R}_{r}}R$. The claim immediately
follows from Lemma 3.1 (the proof for $\mathcal{I}_{r}$ is symmetric).

Now, we are ready to prove the following lemma, which yields the reporting
mechanism stated in Lemma F.1 for _prefix-suffix_ $2$-covers.

######  Lemma F.4.

Let $S$ be a string and $m$ an integer. There is an algorithm that reports a
set $\mathcal{C}^{\prime}_{m}$ of $2$-covers of length at most $m$ such that
every non non-highly periodic prefix-suffix $2$-covers of $S$ is in
$\mathcal{C}^{\prime}_{m}$ in $O(n\log^{4}n+\mathsf{output}\cdot\log n)$ time.

######  Proof F.5.

The algorithm starts with the common preprocess phase described in Section 3.
The algorithm iterates over all pairs of integers $(k_{\ell},k_{r})$ such that
$1.5^{k_{\ell}}\leq n$ and $1.5^{k_{r}}\leq n$. Let $(k_{\ell},k_{r})$ be such
a pair, the algorithm processes $(k_{\ell},k_{r})$ as follows. For every
$i\in[n]$ the algorithm applies Lemma F.2 with $k=k_{\ell}$ to get
$\mathcal{I}_{\ell}$ and with $k=k_{r}$ to get $\mathcal{I}_{r}$. Let
$\mathcal{R}_{i}=\\{I\times[-\infty..\infty]\mid
I\in\mathcal{I}_{\ell}\\}\cup\\{[-\infty..\infty]\times I\mid
I\in\mathcal{I}_{r}\\}$. The algorithm uses Lemma C.1 to compute a set
$\overline{\mathcal{R}}_{i}$ of rectangles such that
$\bigcup_{R\in\overline{\mathcal{R}}_{i}}R=[-\infty..\infty]^{2}\setminus\bigcup_{R\in\mathcal{R}_{i}}R$
in $O(1)$ time. Let
$\mathsf{Valid}=\\{[1.5^{k_{\ell}}..1.5^{k_{\ell}+1}]\times[1.5^{k_{r}}..1.5^{k_{r}+1}]\\}$,
and let $\overline{\mathsf{Valid}}$ be the inverse set of rectangles computed
by Lemma C.1. Then, the algorithm computes
$\overline{\mathcal{R}}=(\bigcup_{i\in[n]}\overline{\mathcal{R}_{i}})\cup(\overline{\mathsf{Valid}})$.
Finally, the algorithm uses the third component of Lemma 5.2 with
$\overline{\mathcal{R}}$ and $m-2$ as a bound for $x+y$. For every free point
$(\ell,r)$ with respect to $\overline{\mathcal{R}}$ reported by Lemma 5.2, the
algorithm reports $(S[1..1+\ell],S[n-r..n])$ as a $2$-cover of $S$.

##### Correctness.

Let $(\mathsf{pref},\mathsf{suff})$ be a non-highly periodic $2$-cover with
$\mathsf{pref}=S[1..1+\ell]$, $\mathsf{suff}=S[n-r..n]$ and $\ell+r+2\leq m$.
Let $k_{\ell}$ and $k_{r}$ be the integers such that
$\ell\in[1.5^{k_{\ell}}..1.5^{k_{\ell}+1}]$ and
$r\in[1.5^{k_{r}}..1.5^{k_{r}+1}]$. Clearly,
$(\ell,r)\in[1.5^{k_{\ell}}..1.5^{k_{\ell}+1}]\times[1.5^{k_{r}}..1.5^{k_{r}+1}]$.
Additionally, since $(\mathsf{pref},\mathsf{suff})$ covers $i$ for every
$i\in[n]$, it must be the case that $(\ell,r)\notin R$ for every
$R\in\overline{\mathcal{R}_{i}}$ by Lemma F.2. It follows that $(\ell,r)$ is a
free point with respect to $\overline{\mathcal{R}}$ with $\ell+r\leq m-2$, as
required.

Let $(\mathsf{pref},\mathsf{suff})$ be a pair reported by the algorithm with
$\mathsf{pref}=S[1..1+\ell]$ and $\mathsf{suff}=S[n-r..n]$. Let
$(k_{\ell},k_{r})$ be the pair such that $(\mathsf{pref},\mathsf{suff})$ was
reported by the instance of Lemma 5.2 created when processing
$(k_{\ell},k_{r})$. Let $\overline{\mathcal{R}}$ and
$\overline{\mathsf{Valid}}$ be the sets computed when processing
$(k_{\ell},k_{r})$. Since $(\mathsf{pref},\mathsf{suff})$ was reported, it
must be the case that $(\ell,r)$ is free with respect to
$\overline{\mathcal{R}}$. Since
$\overline{\mathsf{Valid}}\subseteq\overline{\mathcal{R}}$ it must be that
$(\ell,r)\in\mathsf{Valid}$ which means
$\ell\in[1.5^{k_{\ell}}..1.5^{k_{\ell}+1}]$ and
$r\in[1.5^{k_{r}}..1.5^{k_{r}+1}]$. Moreover, for every $i\in[n]$ we have
$(\ell,r)\notin\bigcup_{R\in\overline{\mathcal{R}_{i}}}R$ and therefore
$(\ell,r)\in\bigcup_{R\in\mathcal{R}_{i}}R$. It follows from Lemma F.2 that
$(\mathsf{pref},\mathsf{suff})$ covers $i$. It follows that
$(\mathsf{pref},\mathsf{suff})$ is a $2$-cover. Finally, the point $(\ell,r)$
satisfies $\ell+r\leq m-2$ which leads to
$|\mathsf{pref}|+|\mathsf{suff}|=\ell+r+2\leq m$ as required.

##### Complexity.

The preprocess of Section 3 is computed in $O(n\log^{2}n)$ time. When a pair
$(k_{\ell},k_{r})$ is processed, Lemma F.2 and Lemma C.1 are applied $O(n)$
times, which takes $O(n\log^{2}n)$ time. Then, Lemma 5.2 is applied on a set
of $\Theta(n)$ rectangles, which takes
$O(n\log^{3}n+\mathsf{output}_{(k_{\ell},k_{r})}\cdot\log^{2}n)$ time, with
$\mathsf{output}_{(k_{\ell},k_{r})}$ being the set of free points with respect
to the rectangles $\overline{\mathcal{R}}$ created for the pair
$(k_{\ell},k_{r})$. Due to the inclusion of $\overline{\mathsf{Valid}}$ in
$\overline{\mathcal{R}}$, we have that every reported point $(\ell,r)$ has
$\ell\in[1.5^{k_{\ell}}..1.5^{k_{\ell}+1}]$ and
$r\in[1.5^{k_{r}}..1.5^{k_{r}+1}]$. It immediately follows that every point is
reported at most once. It follows from Lemma F.2 that every free point
$(\ell,r)$ with respect to $\overline{\mathcal{R}}$ corresponds to a $2$-cover
$(S[1..1+\ell],S[n-r..n])$. Notice that the same $2$-cover may be reported at
most twice - in the case in which $S[1..1+\ell]=S[n-\ell..n]$ and
$S[1..1+r]=S[n-r..n]$. It follows that the accumulated size of
$\mathsf{output}_{(k_{\ell},k_{r})}$ across all pairs $(k_{\ell},k_{r})$ is
bounded by $2\cdot\mathsf{output}$, with $\mathsf{output}$ being the set of
$2$-covers reported by the algorithm. In conclusion, the total running time is
bounded by $O(n\log^{4}+\mathsf{output}\cdot\log n)$ due to the existence of
$O(\log^{2}n)$ pairs $(k_{\ell},k_{r})$.

####  F.1.2 Report All Non-Highly Periodic Border-Substring 2-Covers

We proceed to prove that all non-highly periodic border-substring $2$-covers
can be reported efficiently.

######  Lemma F.6.

Let $S$ be a string and $m$ be an integer. There exists an algorithm that
reports a set $\mathcal{C}_{m}$ of $2$-covers with length at most $m$, such
that every non-highly periodic border-substring $2$-covers of $S$ is in
$\mathcal{C}_{m}$. The running time of the algorithm is
$O(n\log^{4}n+\mathsf{output}\cdot\log^{2}n)$.

######  Proof F.7.

The algorithm starts with the common preprocessing phase described in Section
3. We also assume that all $1$-covers are found in advance via the linear time
algorithm of Moore and Smyth [23, 24].. Every $2$-cover containing a $1$-cover
is implicitly reported via the corresponding $1$-cover. The algorithm iterates
every pair $(b,k)$ such that $S[1..b]$ is a non-highly periodic border and $k$
is an integer such that $1.5^{k}\leq n$ as follows. The algorithm finds all
occurrences of $S[1..b]$ in $S$ using Lemma 2.11. If every index in $S$ is
covered by $S[1..b]$, the algorithm simply ignores $S[1..b]$, as all pairs
including it are implicitly reported as the $1$-cover $S[1..b]$ If $S[1..b]$
is not a $1$-cover, the algorithm picks an arbitrary index $f$ not covered by
$S[1..b]$. For every index $i$ that is not covered by $S[1..b]$, the algorithm
applies Lemma 3.1 with $f$,$i$, and $k$ to obtain a set $\mathcal{R}_{i}$ of
rectangles. The algorithm then applies Lemma C.1 to obtain a set of $O(1)$
rectangles $\overline{\mathcal{R}}_{i}$ such that
$\bigcup_{R\in\overline{\mathcal{R}}_{i}}R=[-\infty..\infty]^{2}\setminus\bigcup_{R\in\mathcal{R}_{i}}R$,
The algorithm then creates a set $\overline{\mathsf{Valid}}$ of $O(n)$
rectangles such that a point $(\ell,r)$ is not in a rectangle of
$\overline{\mathsf{Valid}}$ if and only if $\ell+r+1\in[1.5^{k}..1.5^{k+1}]$.
Note that there is a set of $O(1.5^{k})=O(n)$ rectangles that satisfy this
constraint. Finally, the algorithm applies the third variant of Lemma 5.2 on
the set $\overline{R}=(\bigcup_{i\in
U}\overline{\mathcal{R}}_{i})\cup(\overline{\mathsf{Valid}})$ with $U$ being
the set of indices not covered by $S[1..b]$ and $m-1-b$ the bound on $x+y$.
For every free point $(\ell,r)$ obtained by Lemma 5.2, the algorithm reports
the pair $(S[1..b],S[f-\ell..f+r])$ as a $2$-cover.

##### Correctness

Let $(\mathsf{bor},\mathsf{sub})$ be a non-highly periodic border-substring
$2$-cover with $\mathsf{bor}=S[1..b]$ and $b+|\mathsf{sub}|\leq m$. If every
index in $S$ is covered by an occurrence of $\mathsf{bor}$, the pair is report
implicitly via the $1$-cover $\mathsf{bor}$. Otherwise, the index $f$ not
covered by $\mathsf{bor}$ picked by the algorithm must be covered by
$\mathsf{sub}$. It follows that $\mathsf{sub}=[f-\ell..f+r]$ for some
$\ell,r\in\mathbb{N}$. Let $k$ be the integer such that
$|\mathsf{sub}|=\ell+r-1\in[1.5^{k}..1.5^{k+1}]$. Let $\overline{\mathcal{R}}$
be the set of rectangles on which the algorithm applied Lemma 5.2 when the
pair $(b,k)$ was processed. It is clear from the definition of
$\overline{\mathsf{Valid}}$ that the point $(\ell,r)$ is not in a rectangle of
$\overline{\mathsf{Valid}}$. Note that every index in $S$ not covered by
$\mathsf{bor}$ must be covered by $\mathsf{sub}$. It follows from Lemma 3.1
and from $|\mathsf{sub}|\in[1.5^{k}..1.5^{k+1}]$ that $(\ell,r)$ is a free
point with respect to $\overline{\mathcal{R}}$, and therefore the pair
$(S[1..b],S[f-\ell..f+r])$ is reported as a $2$-cover. Finally the point
$(\ell+r)$ respects the bound of the third variant of Definition 5.1, since
$|\mathsf{bor}|+|\mathsf{sub}|=b+r+\ell+1\leq m$ as required.

Now, let $(S[1..b],S[f-\ell..f+r])$ be a pair reported by the algorithm. Let
$k$ be the unique integer such that $\ell+r-1\in[1.5^{k}..1.5^{k+1}]$. Since
the pair $(S[1..b],S[f-\ell..f+r]$ was reported by the algorithm, it must be
the case that $(\ell,r)$ is a free point with respect to a set of rectangles
$\overline{\mathcal{R}}$ created when processing some pair $(b,k^{\prime})$.
Due to the inclusion of $\overline{\mathsf{Valid}}$ in
$\overline{\mathcal{R}}$ and the uniqueness of $k$, it must be the case that
$k^{\prime}=k$. According to Lemma 3.1, it follows from $(\ell,r)$ being a
free point with respect to $\overline{\mathcal{R}}$ and from
$\ell+r+1\in[1.5^{k}..1.5^{k+1}]$ that $S[f-\ell..f+r]$ covers every index
that is not covered by $S[1..b]$, so $(S[1..b],S[f-\ell..f+r])$ is indeed a
$2$-cover. Finally, the bound on $\ell+r$ on any reported point ensures that
$|S[1..b]|+S[f-\ell..f+r]|=b+\ell+r+1\leq m$ as required.

##### Complexity

The preprocessing of Section 3 is carried in $O(n\log^{2}n)$ time. The set of
all non-highly periodic borders is computed in $O(n)$ time as in Section D.2.
For every $1$-cover $S[1..b]$ identified the algorithm, the algorithm applies
Lemma 2.14 to report all $2$-covers containing $S[1..b]$ in time
$O(\mathsf{output}_{b})$ with $\mathsf{output}_{b}$ being the number of such
borders. We proceed to consider non-highly periodic borders $S[1..b]$ that are
not $1$-covers. For every pair $(b,k)$, the algorithm applies pattern matching
once, and creates $O(n)$ rectangles using Lemma 3.1. The time complexity of
these operations sums up to $O(n\log^{2}n)$. Then, the algorithm finds free
point on a set of $\Theta(n)$ rectangles using Lemma 5.2. The time complexity
of this part of the algorithm is
$O(n\log^{3}n+\log^{2}n\cdot\mathsf{output}_{b,k})$ with
$\mathsf{output}_{b,k}$ being the number of free points with respect to the
rectangle set $\overline{\mathcal{R}}$ created when processing $(b,k)$. We
bound the number of times that a $2$-cover $(S[1..b],\mathsf{sub})$ can be
reported by the algorithm via a free point. Let $k$ be the unique integer such
that $|\mathsf{sub}|\in[1.5^{k}..1.5^{k+1}]$. When the pair $(b,k)$ is being
processed, $(S[1..b],\mathsf{sub})$ may be reported multiple times due to
multiple occurrences of $\mathsf{sub}$ in the proximity of $f$. More
specifically, there may be two (or more) points $(\ell_{1},r_{1})$ and
$(\ell_{2},r_{2})$ such that
$S[f-\ell_{1}..f+r_{1}]=S[f-\ell_{2}..f+r_{2}]=\mathsf{sub}$. We claim that
there are at most $6$ such points. This is since due to Lemma 3.1, we have
$\mathsf{per}(\mathsf{sub})\geq\frac{1.5^{k}}{4}$ (due to $(\ell,r)$ being a
free point with respect to $\overline{\mathcal{R}}$). It follows that two
starting indices of occurrences of $\mathsf{sub}$ must be at least
$\frac{1.5^{k}}{4}$ indices apart. Since $|\mathsf{sub}|\leq 1.5^{k+1}$ we
have that at most $1.5^{k+1}/\frac{1.5^{k}}{4}=6$ occurrences of
$\mathsf{sub}$ can touch the index $f$. The $2$-cover $(S[1..b],\mathsf{sub})$
can also be reported with reversed roles i.e. with $S[1..b]$ acting as the
substring and $\mathsf{sub}$ as the border. This can only happen when
processing the pair $(b^{\prime},k^{\prime})$ with $k^{\prime}$ being the
unique integer such that $b\in[1.5^{k^{\prime}}..1.5^{k^{\prime}+1}]$ and
$S[1..b^{\prime}]=\mathsf{sub}$. Due to the same reasoning as before, the
$2$-cover can be reported at most $O(1)$ times when the pair
$(b^{\prime},k^{\prime})$ is processed. It follows from the above analysis
that across all pairs $(b,k)$, a $2$-cover can be reported at most $12=O(1)$
times. It follows that the total contribution of the
$O(\log^{2}n\cdot\mathsf{output}_{(b,k)})$ component to the time complexity is
$O(\log^{2}n\cdot\mathsf{output})$. In conclusion, the algorithm runs in time
$O(n\log^{4}n+\log n\cdot\mathsf{output})$ (due to the existence of
$O(\log^{2}n)$ pairs $(b,k)$).

Note that Lemma F.1 follows directly from Lemmas F.4 and F.6.

###  F.2 Report All Highly-Periodic 2-Covers

We are now ready to prove Theorem 1.1.

######  Proof F.8 (Proof of Theorem 1.1).

The algorithm starts by applying Lemma F.1 to obtain and report every non-
highly periodic $2$-cover of $S$ with length bounded by $m$. In addition, the
algorithm constructs the $2$-cover oracle of Theorem 1.3. In particular, we
assume that the algorithm has access to $\mathsf{Dict}$ and
$\mathsf{Dict}_{q}$ presented in Section D.2. The key idea for obtaining the
rest of the $2$-covers is attempting to extend short periodic strings
components of non-highly periodic $2$-covers.

##### Prefix-Suffix.

To streamline the presentation, we present two operators for extending a
periodic substring.

######  Definition F.9.

Let $S$ be a string and let $\mathsf{pref}=S[1..p]$ be a $\rho$-periodic
prefix of $S$. The Operator $\mathsf{PrefExtend}(\mathsf{pref})$ is defined as
follows.

$\mathsf{PrefExtend}(\mathsf{pref})=\begin{cases}S[1..p+\rho]&\textsf{if
}S[1..p+\rho]\textsf{ is }\rho\textsf{-periodic}\\\
\mathsf{End}&\text{otherwise.}\end{cases}$

Similarly, the operator $\mathsf{SuffExtend}(.)$ is defined on a
$\rho$-periodic suffix $\mathsf{suff}=S[s..n]$ as follows.

$\mathsf{SuffExtend}(\mathsf{pref})=\begin{cases}S[s-\rho..n]&\textsf{if
}S[s-\rho..n]\textsf{ is }\rho\textsf{-periodic}\\\
\mathsf{End}&\text{otherwise.}\end{cases}$

We slightly abuse notation by interpreting $\mathsf{PrefExtend}^{0}(X)$ (i.e
applying the operator zero times on $X$) as $X$ even for an aperiodic prefix
$X$, on which the operator is not defined (a similar abuse is allowed for
suffixes). Observe that an $\mathsf{IPM}$ data structure of Lemma 2.13 can be
used to obtain $\mathsf{PrefExtend}$ and $\mathsf{SuffExtend}$ in constant
time.

Finally, we make the following observation which is a direct implication of
Lemma 2.4.  Let $(X,Y)$ be a highly periodic prefix-suffix $2$-cover of $S$.
There is a unique core prefix-suffix $2$-cover $(X^{\prime},Y^{\prime})$ and
two non-negative integers $p,s$ such that
$\mathsf{PrefExtend}^{p}(X^{\prime})=X$ and
$\mathsf{SuffExtend}^{s}(Y^{\prime})=Y$.

Furthermore, for every $(s^{\prime},p^{\prime})\in[0..s]\times[0..p]$ the pair
$(\mathsf{PrefExtend}^{p^{\prime}}(X^{\prime}),\mathsf{SuffExtend}^{s^{\prime}}(Y^{\prime}))$
is also a $2$-cover.

The uniqueness of $(X^{\prime},Y^{\prime})$ arises from the fact that both
operations preserve the period of the prefix/suffix when applied to a periodic
prefix/suffix. Therefore, in order to obtain $X$ from some $X^{\prime}$, we
either have to start from $X^{\prime}=X$ and apply $\mathsf{PrefExtend}$ zero
times if $X$ is aperiodic, or start with a short periodic prefix $X^{\prime}$
with the same period as $X$ (which is unique). The same reasoning applies to
$Y$.

The algorithm processes every non-highly periodic prefix-suffix $2$-cover
$(\mathsf{pref}=S[1..p],\mathsf{suff}=S[n-s+1..n])$ with the following goal:
Report all prefix suffix $2$-covers $(X,Y)$ with length bounded by $m$ such
that $X=\mathsf{PrefExtend}^{p}(\mathsf{pref})$ and
$Y=\mathsf{SuffExtend}^{s}(\mathsf{suff})$ for some naturals $p$ and $s$. It
follows directly from Section F.2 that all required prefix-suffix two covers
are found by applying such process to every core pair.

We proceed to describe the algorithm for processing a core pair
$(\mathsf{pref},\mathsf{suff})$.

  * •

If both $\mathsf{pref}$ and $\mathsf{suff}$ are aperiodic - the algorithm does
not apply further processing to it.

  * •

If $\mathsf{pref}$ is short $\rho$-periodic and $\mathsf{suff}$ is aperiodic,
the algorithm initialize an iterator $p=1$ initiates a loop. In every step of
the loop, the algorithm sets $X_{p}=\mathsf{PrefExtend}^{p}(\mathsf{pref})$
and checks if $X_{p}\neq\mathsf{End}$, $|X_{p}|+|\mathsf{suff}|\leq m$ and
$(X_{p},\mathsf{suff})$ is a $2$-cover of $S$. If all of the conditions are
satisfied, the algorithm reports $(X_{p},\mathsf{suff})$ as a $2$-cover,
assigns $p\leftarrow p+1$ and repeats the loop. If one of the conditions is
false - the loop is terminated.

  * •

If $\mathsf{pref}$ is aperiodic and $\mathsf{suff}$ is short $\rho$-periodic
the algorithm processes $(\mathsf{pref},\mathsf{suff})$ in a symmetric manner
to the previous case, extending $\mathsf{suff}$ using $\mathsf{SuffExtend}$.

  * •

If both $\mathsf{pref}$ and $\mathsf{suff}$ are short periodic, the algorithm
applies the extensions of the previous two cases in a nested loop fashion as
follows. The algorithm initiates two iterators $p=0$ and $s=0$. In every step
of the loop, the algorithm sets $X_{p}=\mathsf{PrefExtend}^{p}(X)$ and
$Y_{p}=\mathsf{SuffExtend}^{s}(Y)$. The algorithm checks if
$X_{p}\neq\mathsf{End}$, $Y_{p}\neq\mathsf{End}$, $|X_{p}|+|Y_{p}|\leq m$ and
$(X_{p},Y_{p})$ is a $2$-cover. If all conditions are satisfied - the
algorithm reports $(X_{p},Y_{p})$ as a $2$-cover, assigns $p\leftarrow p+1$,
and repeats the loop. If one of the conditions fails, and $p\neq 0$, the
algorithm assigns $p\leftarrow 0$ and $s\leftarrow s+1$, and repeats the loop.
If one of the conditions fails and $p=0$, the loop terminates.

##### Correctness.

The correctness of the algorithm arises naturally from Section F.2. Clearly,
every pair $(X,Y)$ reported by the algorithm is a $2$-cover with length
bounded by $m$, as these conditions are explicitly tested for every reported
pair.

It remains to show that all required pairs are reported. Let $(X,Y)$ be a
prefix suffix highly periodic $2$-cover with length bounded by $m$. Let
$(X^{\prime},Y^{\prime})$ be the unique core pair derived from Section F.2 and
$p^{*}$ and $s^{*}$ the integers such that
$X=\mathsf{PrefExtend}^{p^{*}}(X^{\prime})$ and
$Y=\mathsf{SuffExtend}^{s^{*}}(Y^{\prime})$. From now on, we assume that both
$X$ and $Y$ are highly periodic. The analysis required for the case in which
only one of $X$ and $Y$ is highly periodic is derived from the analysis for
the case in which both are highly periodic. In this case, both $X^{\prime}$
and $Y^{\prime}$ are short periodic with the same periods of $X$ and of $Y$,
respectively. When the pair $(X^{\prime},Y^{\prime})$ is processed by the
algorithm, we claim that for every $s^{\prime}<s^{*}$ the pair
$(X^{\prime}_{0},Y^{\prime}_{s^{\prime}})$ satisfies all conditions checked by
the loop.

  1. 1.

$X^{\prime}_{0}=X^{\prime}\neq\mathsf{End}$.

  2. 2.

$Y^{\prime}_{s^{\prime}}\neq\mathsf{End}$ since
$Y^{\prime}_{s^{*}}\neq\mathsf{End}$, and $\mathsf{SuffExtend}(\mathsf{End})$
is undefined.

  3. 3.

$|X^{\prime}_{0}|+|Y^{\prime}_{s^{\prime}}|\leq m$. Since for every
$s^{\prime}<s^{*}$ such that $Y^{\prime}_{s^{*}}\neq\mathsf{End}$ and
$Y^{\prime}_{s^{\prime}}\neq\mathsf{End}$ we have
$|Y^{\prime}_{s^{\prime}}|<|Y^{\prime}_{s^{*}}|$, and we have
$|X|+|Y|=|X^{\prime}_{p^{*}}|+|Y^{\prime}_{s^{*}}|\leq m$.

  4. 4.

$(X^{\prime}_{0},Y^{\prime}_{s^{\prime}})$ is a $2$-cover due to Section F.2.

It follows that the iterator $s$ of the loop will reach the value $s^{*}$. A
similar analysis shows that when reaching $s^{*}$ and starting the process of
increasing $p$, the $p$ iterator of the loop would reach the value $p^{*}$. At
this point, the pair $(X,Y)=(X^{\prime}_{p^{*}},Y^{\prime}_{s^{*}})$ is
reported, as required.

##### Complexity.

We analyze the complexity of the nested loop executed in the case in which
both $X$ and $Y$ are short periodic. The complexity of the rest of the cases
arises from the same arguments. When processing a pair $(X,Y)$, each step of
every loop is dominated by the query to the oracle - Obtaining
$\mathsf{PrefExtend}^{p}(X)$ or $\mathsf{SuffExtend}^{s}(Y)$ can be done in
constant time using $\mathsf{PrefExtend}^{p-1}(X)$ of
$\mathsf{SuffExtend}^{s-1}(Y)$ and the rest of the checks consist of integer
comparisons. Each $2$-oracle query on a pair $(X_{p},Y_{s})$ to the oracle
that reports True can be charged on the reported pair $(X_{p},Y_{s})$. Due to
the uniqueness of the core pair $(X,Y)$ with respect to $(X_{p},Y_{s})$, the
total number of such queries is $\mathsf{output}$. Each query on a pair
$(X_{p},Y_{s})$ that reports False is charged on the pair $(X_{0},Y_{s})$. If
$p>0$, it means that the pair $(X_{0},Y_{s})$ was reported as a $2$-cover. It
follows that the total number of such queries on pairs $(X_{p},Y_{s})$ with
$p>0$ is bounded by $\mathsf{output}$ across all core pairs. If $p=0$, the
loop terminates after the query. It follows that there is at most one such
query for every processed core pair, and their total number across all pairs
is bounded by $\mathsf{output}$ as well. It follows that the overall
complexity of processing all pairs is bounded by
$O(\mathsf{output}\cdot\log^{3})$ as required.

##### Border-Substring.

The algorithm proceeds to report all border-substring $2$-covers. The
reporting is carried out following the same principles as in the prefix-suffix
case. However, extending the periodic substrings requires a more careful
treatment.

We define the following operator for extending substrings.

######  Definition F.10.

Let $S$ be a string and let $\mathsf{sub}=S[i..j]$ be a $\rho$-periodic prefix
of $S$. The Operator $\mathsf{SubExtend}(\mathsf{sub})$ is defined as follows.

$\mathsf{SubExtend}(\mathsf{sub})=\begin{cases}S[i..j+\rho]&\textsf{if
}S[i..j+\rho]\textsf{ is }\rho\textsf{-periodic}\\\ S[i-\rho..j]&\textsf{if
}S[i-\rho..j]\textsf{ is }\rho\textsf{-periodic and }S[i..j+\rho]\textsf{ is
not}\\\ \mathsf{End}&\text{otherwise.}\end{cases}$

Again, we slightly abuse notation by allowing $\mathsf{SubExtend}^{0}(X)=X$,
even for non-periodic substrings $X$. Note that unlike $\mathsf{PrefExtend}$
and $\mathsf{SuffExtend}$, the operator $\mathsf{SubExtend}$ is sensitive to
the exact location of the substring $\mathsf{sub}$ in $S$. However, it is
still easy to obtain $\mathsf{SubExtend}(\mathsf{sub})$ from $\mathsf{sub}$
using $\mathsf{IPM}_{S}$ in constant time.

The following observation parallels Section F.2 and arises due to the same
arguments.  Let $(X,Y)$ be a highly periodic border-substring $2$-cover of $S$
such that $X$ is not a $1$-cover. Let $f$ be an index not covered by $X$.
There is a unique core border-substring $2$-cover $(X^{\prime},Y^{\prime})$
and two non-negative integers $b,s$ such that
$\mathsf{PrefExtend}^{b}(X^{\prime})=X$ and
$\mathsf{SubExtend}^{s}(Y^{\prime})=Y$. Where the $\mathsf{SubExtend}$
operations applied to $Y^{\prime}$ are with respect to an occurrence of
$Y^{\prime}$ covering $f$.

Furthermore, for every $(s^{\prime},p^{\prime})\in[0..s]\times[0..p]$ the pair
$(\mathsf{PrefExtend}^{p^{\prime}}(X^{\prime}),\mathsf{SuffExtend}^{s^{\prime}}(Y^{\prime}))$
is also a $2$-cover.

Not that an occurrence of $Y^{\prime}$ covering $f$ must exist, as $Y$ must
cover $f$, and $Y^{\prime}$ covers every index covered by $Y$ by Lemma 2.4.

As an initial step, the algorithm uses the $O(n)$ time algorithm of Smyth [28]
to find all $1$-covers of $S$. For every $1$-cover $\mathsf{bor}$ of $S$, all
pairs $(\mathsf{bor},\mathsf{sub})$ are considered to be reported implicitly
via $\mathsf{bor}$.

We now proceed to treat the non-trivial case. As in the prefix-suffix , the
algorithm processes every core pair $(X,Y)$ and reports all pairs that arise
from $(X,Y)$ via Section F.2.

  * •

If both $\mathsf{bor}$ and $\mathsf{sub}$ are aperiodic, the algorithm does
not apply any further processing.

  * •

If $\mathsf{bor}$ is short $\rho$-periodic and $\mathsf{sub}$ is aperiodic,
the algorithm attempts to extend $\mathsf{bor}$ similarly to the prefix
extension process described in the prefix-suffix case with the following
modification. As a preliminary step, the algorithm obtains
$p^{*}=\mathsf{Dict}_{q}[b]$ (see Section D.2). Let
$\mathsf{bor}=S[1..2\rho+d_{b}]$ for $d_{b}\in[0..\rho-1]$. The algorithm
starts the process of extending $\mathsf{bor}$ from
$\mathsf{bor}^{\prime}=S[1..q^{*}\cdot\rho+d_{b}]$ i.e. setting the initial
value of $p$ as $q^{*}$. In essence, the algorithm ‘skips’ any extension of
$\mathsf{bor}$ that is a $1$-cover. All $2$-covers containing a $1$-cover are
reported implicitly. If $q^{*}=\infty$, the algorithm does not apply any
further processing to the pair $(\mathsf{bor},\mathsf{sub})$.

  * •

If $\mathsf{sub}$ is short $\rho$-periodic and $\mathsf{bor}$ is aperiodic,
the algorithm attempts to extend $\mathsf{sub}$ as follows. Let $f=f_{b}$ be
an index not covered by $S[1..b]$ extracted from $\mathsf{Dict}$ (see Section
D.2). If $f=\infty$, $\mathsf{bor}$ is a $1$-cover and all pairs containing
$\mathsf{bor}$ are reported implicitly.

Otherwise, $f$ is an index not covered by $\mathsf{bor}$. The algorithm finds
an occurrence of $\mathsf{sub}$ covering $f$ using the $\mathsf{IPM}_{S}$ data
structure of Lemma 2.13, let $\mathsf{sub}=S[f-\ell..f+r]$ for some integers
$\ell,r$ (note that such $\ell$ and $r$ must exist since
$(\mathsf{bor},\mathsf{sub})$ is a $2$-cover). The algorithm starts the
extension process from $Y_{1}=S[f-\ell..f+r]$. It initializes an iterator
$b=1$, and the loop is carried as in the prefix suffix case, replacing
$\mathsf{PrefExtend}$ with $\mathsf{SubExtend}$.

  * •

If $\mathsf{bor}$ is short $\rho_{b}$-periodic and $\mathsf{sub}$ is short
$\rho_{s}$-periodic, the algorithm processes $(\mathsf{bor},\mathsf{sub})$ in
a nested loop fashion as follows. We present this case in more detail, to
provide a full picture of the previous cases as well. First, the algorithm
finds the minimal value $q$ such that
$X_{q}=\mathsf{PrefExtend}^{q}(\mathsf{bor})$ is not a $1$-cover. This is done
using $\mathsf{Dict}_{q}$. If no such value exists - the algorithm halts the
processing of the pair $(\mathsf{bor},\mathsf{sub})$. If this value exists,
the algorithm sets an iterator $b\leftarrow q$. Next, the algorithm uses
$\mathsf{Dict}$ to find an index $f$ not covered by $X_{q}$ and applies
internal pattern matching (Lemma 2.13) on the text
$S[f-|\mathsf{sub}|..f+|\mathsf{sub}|]$ to find an occurrence of
$\mathsf{sub}$. If no such occurrence is found, the algorithm terminates the
process of the pair $(\mathsf{bor},\mathsf{sub})$. Otherwise, the algorithm
uses the occurrence to find two non-negative integers $\ell,r$ such that
$\mathsf{sub}=S[f-\ell..f+r]$. The algorithm then sets $Y_{0}=S[f-\ell..f+r]$
and initializes a secondary iterator $s=0$. Now, the algorithm starts running
the loop. At every step of the loop, the algorithm sets
$X_{b}=\mathsf{PrefExtend}^{b}(\mathsf{bor})$ and