# Small space and streaming pattern matching with $k$ edits

Tomasz Kociumaka Partly supported by NSF 1652303, 1909046, and HDR TRIPODS
1934846 grants, and an Alfred P. Sloan Fellowship. University of California,
Berkeley, USA  Ely Porat  Bar-Ilan University, Israel  Tatiana Starikovskaya
Partly supported by the grant ANR-20-CE48-0001 from the French National
Research Agency (ANR). DI/ENS, PSL Research University, France

###### Abstract

In this work, we revisit the fundamental and well-studied problem of
approximate pattern matching under edit distance. Given an integer $k$, a
pattern $P$ of length $m$, and a text $T$ of length $n\geq m$, the task is to
find substrings of $T$ that are within edit distance $k$ from $P$. Our main
result is a streaming algorithm that solves the problem in
$\tilde{\mathcal{O}}(k^{5})$ space and $\tilde{\mathcal{O}}(k^{8})$ amortised
time per character of the text, providing answers correct with high
probability. (Hereafter, $\tilde{\mathcal{O}}(\cdot)$ hides a
$\mathrm{poly}(\log n)$ factor.) This answers a decade-old question: since the
discovery of a $\mathrm{poly}(k\log n)$-space streaming algorithm for pattern
matching under Hamming distance by Porat and Porat [FOCS 2009], the existence
of an analogous result for edit distance remained open. Up to this work, no
$\mathrm{poly}(k\log n)$-space algorithm was known even in the simpler semi-
streaming model, where $T$ comes as a stream but $P$ is available for read-
only access. In this model, we give a deterministic algorithm that achieves
slightly better complexity.

Our central technical contribution is a new space-efficient deterministic
encoding of two strings, called the greedy encoding, which encodes a set of
all alignments of cost $\leq k$ with a certain property (we call such
alignments _greedy_). On strings of length at most $n$, the encoding occupies
$\tilde{\mathcal{O}}(k^{2})$ space. We use the encoding to compress substrings
of the text that are close to the pattern. In order to do so, we compute the
encoding for substrings of the text and of the pattern, which requires read-
only access to the latter.

In order to develop the fully streaming algorithm, we further introduce a new
edit distance sketch parametrised by integers $n\geq k$. For any string of
length at most $n$, the sketch is of size $\tilde{\mathcal{O}}(k^{2})$ and it
can be computed with an $\tilde{\mathcal{O}}(k^{2})$-space streaming
algorithm. Given the sketches of two strings, in $\tilde{\mathcal{O}}(k^{3})$
time we can compute their edit distance or certify that it is larger than $k$.
This result improves upon $\tilde{\mathcal{O}}(k^{8})$-size sketches of
Belazzougui and Zhu [FOCS 2016] and very recent
$\tilde{\mathcal{O}}(k^{3})$-size sketches of Jin, Nelson, and Wu [STACS
2021].

##  1 Introduction

In the pattern matching problem, given two strings, a _pattern_ $P$ of length
$m$ and a _text_ $T$ of length $n$, one must find all substrings of the text
equal to the pattern. This is a fundamental problem of string processing with
a myriad of applications in such fields as computational biology, information
retrieval, and signal processing, to mention just a few. However, in many
applications, retrieving substrings that are exactly equal to the pattern is
not enough, and one must search for substrings merely _similar_ to the
pattern. This task, which is often referred to as _approximate pattern
matching problem_ , can be formalised in the following way: for each position
$i$ in the text, compute the smallest distance $d_{i}$ between $P$ and any
substring of $T$ that ends at position $i$. In string processing, the two most
popular distances are the Hamming distance and the edit distance. Recall that
the Hamming distance between two equal-length strings is the number of
mismatching pairs of characters of the strings. The edit distance of two
strings, not necessarily of equal lengths, is the smallest number of edits
(character insertions, deletions, and substitutions) needed to transform one
string into the other. Due to its practical importance, the approximate
pattern matching problem has been extensively studied in the literature,
originally in the classic setting with input strings explicitly stored in
memory.

In general, computing Hamming distance is easier and can be considered as a
preliminary step towards tackling edit distance. The first solution for
approximate pattern matching under the Hamming distance was given by
Abrahamson [2] and, independently, Kosaraju [40]; based on the fast Fourier
transform, it spends $\mathcal{O}(n\sqrt{m\log m})$ time to compute the
Hamming distance between the pattern and all the length-$m$ substrings of the
text. Up to date, no algorithms improve upon this time complexity for the
general version of approximate pattern matching under Hamming distance, but
there are better solutions when one is interested only in the distances not
exceeding a given $k$, a variant known as the _$k$ -mismatch problem_. The
first algorithm for the $k$-mismatch problem was given by Landau and Vishkin
[42], who improved the running time to $\mathcal{O}(kn)$ via so-called
“kangaroo jumps”, a technique utilising the suffix tree to compute the longest
common prefix of two suffixes of a string in constant time. This bound was
further improved by Amir et al. [3] who showed two solutions, one with running
time $\mathcal{O}(n\sqrt{k\log k})$ and one with running time
$\tilde{\mathcal{O}}(n+k^{3}n/m)$-time algorithm111Hereafter,
$\tilde{\mathcal{O}}(\cdot)$ hides a factor of $\mathrm{poly}(\log n)$..
Continuing this line of research, Clifford et al. [14] presented an
$\tilde{\mathcal{O}}(n+k^{2}n/m)$-time algorithm, while Gawrychowski and
Uznański [31] demonstrated a smooth trade-off between the latter and the
solution of Amir et al. by designing an
$\tilde{\mathcal{O}}(n+kn/\\!\sqrt{m})$-time algorithm. Very recently, Chan et
al. [11] shaved off most of the polylogarithmic factors and achieved the
running time of $\mathcal{O}(n+\min(k^{2}n/m,kn\sqrt{\log m}/\sqrt{m}))$ at
the cost of Monte-Carlo randomization.

For the edit distance, a detailed survey of previous solutions can be found in
[49], and here we only discuss the landmark results of the theoretical
landscape. For the general variant of the problem, the first algorithm was
given by Sellers [56]. The algorithm was based on dynamic programming and used
$\mathcal{O}(nm)$ time. Masek and Paterson [46] improved the running time of
the algorithm to $\mathcal{O}(nm/\log n)$ via the Four Russians technique. On
the lower bound side, it is known that there is no solution with strongly
subquadratic time complexity unless the Strong Exponential Time hypothesis
[36] is false, even for the binary alphabet [5, 8]. Abboud et al. [1] gave a
more precise bound under a weaker assumption: Namely, they showed that even
shaving an arbitrarily large polylog factor would imply that NEXP does not
have non-uniform $\mathrm{NC}^{1}$ circuits. Finally, Clifford et al. [15]
showed that, in the cell-probe model with the word size $w=1$, any randomised
algorithm that computes the edit distances between the pattern and the text
online must spend $\Omega(\frac{\sqrt{\log n}}{(\log\log n)^{3/2}})$ expected
amortised time per character of the text.

Similarly to the Hamming distance, one can define the threshold variant of
approximate pattern matching, which we refer to as approximate pattern
matching with $k$ edits. The first algorithm for this variant of the problem
was developed by Landau and Vishkin [43]; this by-now classical algorithm
solves the problem in $\mathcal{O}(nk)$ time. The current best result was
achieved by a series of work [55, 17] with the running time (for some range of
parameters) $\mathcal{O}(n+k^{4}n/m)$. Very recently, Charalampopoulos et al.
[12] studied the problem for both distances in the grammar-compressed setting.
Their result, in particular, implies an $\mathcal{O}(k^{4})$-space and
$\mathcal{O}(nk^{4})$-time algorithm for the read-only model, where random
access to characters in $P$ and $T$ is allowed and one accounts only for the
“extra” space, the space required beyond the space needed to store the pattern
and the text.

In this work, we focus on developing algorithms for approximate pattern
matching with $k$ edits that use as little space as possible. In particular,
we consider the streaming model of computation. In this model, we assume that
the input arrives as a stream, one character at a time. We define the space
complexity of the algorithm to be all the space used, in other words, we
cannot store any information about the input without accounting for it.

The field of streaming algorithms for string processing is relatively recent
but, because of its practical interest, it has received a lot of attention in
the literature. It started with a seminal paper of Porat and Porat in FOCS
2009 [52], who showed streaming algorithms for exact pattern matching and for
the $k$-mismatches problem. The result of Porat and Porat was followed by a
series of works on streaming pattern matching [7, 13, 34, 14, 57, 33, 30, 16,
32, 53], search of repetitions in streams [20, 18, 19, 28, 48, 47, 29], and
recognising formal languages in streams [45, 24, 25, 22, 23, 27, 4, 21, 26].

All known streaming algorithms for approximate pattern matching under the
Hamming distance [52, 14, 16] are based on some rolling hash — a hash on
strings of fixed length that can be efficiently updated when we delete the
first character of a string and append a new one to the end of the string,
such as, for example, the famous Karp–Rabin fingerprint, which allows
computing the Hamming distance between two strings or certify that it exceeds
$k$. The current best algorithm was demonstrated by Clifford et al. in SODA
2019 [16]. The algorithm uses only $\mathcal{O}(k\log\frac{m}{k})$ space,
which is optimal up to a logarithmic factor, and spends
$\mathcal{O}(\log\frac{m}{k}(\sqrt{k\log k}+\log^{3}m))$ time per character.
The algorithm is necessarily randomised and can err with high
probability222With high probability means with probability at least
$1-1/n^{c}$ for any predefined constant $c>1$.. In other words, approximate
pattern matching under the Hamming distance in the streaming model is
essentially fully understood.

On the other hand, for the edit distance there are no small-space solutions,
in particular, because there are no rolling hashes that allow to compute the
edit distance between strings. When $k$ is small, the state-of-the-art
solution [57] uses $\mathcal{O}(k^{8}\sqrt{m}\log^{6}m)$ space and
$\mathcal{O}((k^{2}\sqrt{m}+k^{13})\cdot\log^{4}m)$ worst-case time per
symbol. Again, the algorithm is randomised and outputs all substrings at edit
distance at most $k$ from the pattern with high probability. Another
interesting result is that of Chakraborty et al. [9], who developed an
algorithm for the general version of approximate pattern matching under edit
distance in the model where the text is streaming, but the pattern is read-
only. They showed a randomised algorithm that, for every position $i$ of the
text $T$, computes the smallest edit distance $d_{i}$ between $P$ and a suffix
of $T[1\mathinner{.\,.\allowbreak}i]$ with constant multiplicative and
$m^{8/9}$-additive approximation (in other words, the algorithm returns a
number between $d_{i}$ and $c\cdot d_{i}+m^{8/9}$, where $c\geq 1$ is a
predetermined constant). The algorithm receives the text online and uses
$\mathcal{O}(m^{1-1/54})$ extra space, in addition to the space required to
store the pattern.

Naturally, a question arises: is the true complexity of streaming approximate
pattern matching under edit distance is on par with that of the Hamming
distance? In this work, we answer this question affirmatively.

###  1.1 Our results

The main result of our work is a fully streaming algorithm for approximate
pattern matching under the edit distance that uses
$\tilde{\mathcal{O}}(k^{5})$ space and $\tilde{\mathcal{O}}(k^{8})$ amortized
time per character of the text (Theorem 7.6). The algorithm is randomised and
its answers are correct with high probability.

As a stepping stone, we also consider a simpler semi-streaming model
introduced in [9]. In this model, we assume that the text arrives in a stream,
but the pattern is read-only, which means that, at any moment, the algorithm
can access any character of the pattern in constant time (but re-writing
characters is prohibited). The space complexity of the algorithm is defined as
the total space used on top of the read-only memory holding the pattern. In
this setting, we show a _deterministic_ algorithm for approximate pattern
matching under the edit distance that uses $\tilde{\mathcal{O}}(k^{5})$ space
and $\tilde{\mathcal{O}}(k^{6})$ amortized time per character of the text
(Theorem 7.5).

Additionally, we design a new sketch for retrieving the exact edit distance
(capped with a threshold $k$) between strings of length at most $n$ (3.17).
The sketch is of size $\tilde{\mathcal{O}}(k^{2})$, and it can be built using
a streaming algorithm that costs $\tilde{\mathcal{O}}(nk)$ total time and uses
$\tilde{\mathcal{O}}(k^{2})$ space. Given the sketches of two strings $X,Y$,
in $\tilde{\mathcal{O}}(k^{3})$ time and $\tilde{\mathcal{O}}(k^{2})$ space,
we can compute the edit distance between $X,Y$ or certify that it is larger
than $k$. The answer is correct with a large constant probability (with
standard amplification, we then achieve high probability of success). This
improves upon the $\tilde{\mathcal{O}}(k^{8})$-size sketches of Belazzougui
and Zhang [6] and the $\tilde{\mathcal{O}}(k^{3})$-size sketches of Jin,
Nelson, and Wu [37] developed independently.

The conceptual contribution of our work is described in the technical overview
(Section 3).

##  2 Preliminaries

We assume an integer alphabet $\Sigma=\\{1,2,\ldots,\sigma\\}$ with $\sigma$
_characters_. A _string_ $Y$ is a sequence of characters numbered from $1$ to
$n=|Y|$. By $Y[i]$ we denote the $i$-th symbol of $Y$. For a string $Y$ of
length $n$, we denote its _reverse_ $Y[n]Y[n-1]\ldots Y[1]$ by $\overline{Y}$.
We define $Y[i\mathinner{.\,.\allowbreak}j]$ to be equal to $Y[i]\dots Y[j]$
which we call a _fragment_ of $Y$ if $i\leq j$ and to the empty string
$\varepsilon$ otherwise. We also use notations
$Y[i\mathinner{.\,.\allowbreak}j)$ and $Y(i\mathinner{.\,.\allowbreak}j]$
which naturally stand for $Y[i]\dots Y[j-1]$ and $Y[i+1]\dots Y[j]$,
respectively. We call a fragment $Y[1]\dots Y[j]$ _a prefix_ of $Y$ and use a
simplified notation $Y[\mathinner{.\,.\allowbreak}i]$, and a fragment
$Y[i]\dots Y[n]$ _a suffix_ of $Y$ denoted by
$Y[i\mathinner{.\,.\allowbreak}]$. We say that $X$ is a _substring_ of $Y$ if
$X=Y[i\mathinner{.\,.\allowbreak}j]$ for some $1\leq i\leq j\leq|Y|$. The
fragment $Y[i\mathinner{.\,.\allowbreak}j]$ is called an _occurrence_ of $X$.

For a string $Y$, we define $Y^{m}$ to be the concatenation of $m$ copies of
$Y$. We also define $Y^{\infty}$ to be an infinite string obtained by
concatenating infinitely many of copies of $Y$. We say that a string $X$ of
length $x$ is a _period_ of a string $T$ if
$X=T[1\mathinner{.\,.\allowbreak}x]$ and $T[i]=T[i+x]$ for all
$i=1,\ldots,|T|-x$. By $\mathsf{per}(T)$ we denote the length of the shortest
period of $T$. The string $T$ is called _periodic_ if
$2\,\mathsf{per}(T)\leq|T|$. For a string $Y\in\Sigma^{n}$, we define a
_forward rotation_ $\mathsf{rot}(Y)=Y[2]\cdots Y[n]Y[1]$. In general, a
_cyclic rotation_ $\mathsf{rot}^{s}(Y)$ with _shift_ $s\in\mathbb{Z}$ is
obtained by iterating $\mathsf{rot}$ or the inverse operation
$\mathsf{rot}^{-1}$. A non-empty string $X\in\Sigma^{n}$ is _primitive_ if it
is distinct from its non-trivial rotations, i.e., if $X=\mathsf{rot}^{s}(X)$
holds only when $s$ is a multiple of $n$.

We say that a fragment $X[i\mathinner{.\,.\allowbreak}i+\ell)$ is a _previous
factor_ if
$X[i\mathinner{.\,.\allowbreak}i+\ell)=X[i^{\prime}\mathinner{.\,.\allowbreak}i^{\prime}+\ell)$
holds for some $i^{\prime}\in[1\mathinner{.\,.\allowbreak}i)$. The _LZ77
factorization_ of $X$ is a factorization $X=F_{1}\cdots F_{z}$ into non-empty
_phrases_ such tht the $j$th phrase $F_{j}$ is the longest previous factor
starting at position $1+|F_{1}\cdots F_{j-1}|$; if no previous factor starts
there, then $F_{j}$ consists of a single character. In the underlying _LZ77
representation_ , every phrase $F_{j}=T[j\mathinner{.\,.\allowbreak}j+\ell)$
that is a previous fragment is encoded as $(i^{\prime},\ell)$, where
$i^{\prime}\in[1\mathinner{.\,.\allowbreak}i)$ satisfies
$X[i\mathinner{.\,.\allowbreak}i+\ell)=X[i^{\prime}\mathinner{.\,.\allowbreak}i^{\prime}+\ell)$.
The remaining length-1 phrases are represented by the underlying character. We
use $\mathsf{LZ}(X)$ to denote the underlying _LZ77 representation_ and
$|\mathsf{LZ}(X)|$ to denote its size (the number of phrases).

###  2.1 Edit Distance Alignments

The _edit distance_ $\mathsf{ed}(X,Y)$ between two strings $X$ and $Y$ is
defined as the smallest number of character insertions, deletions, and
substitutions required to transform $X$ to $Y$. The _Hamming distance_
$\mathsf{hd}(X,Y)$ allows substitutions only (and we assume
$\mathsf{hd}(X,Y)=\infty$ if $|X|\neq|Y|$).

######  Definition 2.1.

A sequence $(x_{t},y_{t})_{t=1}^{m}$ is an _alignment_ of $X,Y\in\Sigma^{*}$
if $(x_{1},y_{1})=(1,1)$, $(x_{m},y_{m})=(|X|+1,|Y|+1)$, and
$(x_{t+1},y_{t+1})\in\\{(x_{t}+1,y_{t}+1),(x_{t}+1,y_{t}),(x_{t},y_{t}+1)\\}$
for $t\in[1\mathinner{.\,.\allowbreak}m)$.333This definition is rather
complex, but it is equivalent to the standard definition given in the
textbooks. We chose this particular formulation as it allowed us to introduce
notions essential for this work in a rigorous way.

Given an alignment $\mathcal{A}=(x_{t},y_{t})_{t=1}^{m}$ of strings
$X,Y\in\Sigma^{*}$, for every $t\in[1\mathinner{.\,.\allowbreak}m)$:

  * •

If $(x_{t+1},y_{t+1})=(x_{t}+1,y_{t})$, we say that $\mathcal{A}$ _deletes_
$X[x_{t}]$,

  * •

If $(x_{t+1},y_{t+1})=(x_{t},y_{t}+1)$, we say that $\mathcal{A}$ _deletes_
$Y[y_{t}]$,

  * •

If $(x_{t+1},y_{t+1})=(x_{t}+1,y_{t}+1)$, we say that $\mathcal{A}$ _aligns_
$X[x_{t}]$ and $Y[y_{t}]$, denoted $X[x_{t}]\sim_{\mathcal{A}}Y[y_{t}]$. If
additionally $X[x_{t}]=Y[y_{t}]$, we say that $\mathcal{A}$ _matches_
$X[x_{t}]$ and $Y[y_{t}]$, denoted $X[x_{t}]\simeq_{\mathcal{A}}Y[y_{t}]$.
Otherwise, we say that $\mathcal{A}$ _substitutes_ $X[x_{t}]$ for $Y[y_{t}]$.

The _cost_ of an edit distance alignment $\mathcal{A}$ is the total number
characters that $\mathcal{A}$ deletes or substitutes. We denote the cost by
$\mathsf{cost}_{X,Y}(\mathcal{A})$, omitting the subscript if $X,Y$ are clear
from context. The cost of an alignment $\mathcal{A}=(x_{t},y_{t})_{t=1}^{m}$
is at least its width $0pt(\mathcal{A})=\max_{t=1}^{m}|x_{t}-y_{t}|$. Observe
that $\mathsf{ed}(X,Y)$ can be defined as the minimum cost of an alignment of
$X$ and $Y$. An alignment of $X$ and $Y$ is _optimal_ if its cost is equal to
$\mathsf{ed}(X,Y)$.

Given an alignment $\mathcal{A}=(x_{t},y_{t})_{t=1}^{m}$ of
$X,Y\in\Sigma^{+}$, we partition the elements $(x_{t},y_{t})$ of $\mathcal{A}$
into _matches_ (for which $X[x_{t}]\simeq_{\mathcal{A}}Y[y_{t}]$) and
_breakpoints_ (the remaining elements). We denote the set of matches and
breakpoints by $\mathcal{M}_{X,Y}(\mathcal{A})$ and
$\mathcal{B}_{X,Y}(\mathcal{A})$, respectively, omitting the subscripts if the
strings $X,Y$ are clear from context. Observe that
$|\mathcal{B}_{X,Y}(\mathcal{A})|=1+\mathsf{cost}(\mathcal{A})$.

We call
$M\subseteq[1\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|]$
a _non-crossing matching_ of $X,Y\in\Sigma^{*}$ if $X[x]=Y[y]$ holds for all
$(x,y)\in M$ and there are no distinct pairs $(x,y),(x^{\prime},y^{\prime})\in
M$ with $x\leq x^{\prime}$ and $y\geq y^{\prime}$. Note that, for every
alignment $\mathcal{A}$ of $X,Y$, the set $\mathcal{M}(\mathcal{A})$ is a non-
crossing matching of $X,Y$.

######  Example 2.2.

Consider strings $X=\mathtt{abbaabcb}$ and $Y=\mathtt{acabaabab}$ and a
cost-$4$ alignment

$\mathcal{A}:(1,1),(2,2),(3,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,8),(8,9),(9,10).$

$X$:a1b2b3a4a5b6c7b8$Y$:a1c2a3b4a5a6b7a8b9

The breakpoints are
$\mathcal{B}(\mathcal{A})=\\{(2,2),(3,3),(7,8),(8,8),(9,10)\\}$; the first $4$
breakpoints correspond to a substitution of $X[2]$ for $Y[2]$, a deletion of
$Y[3]$, a deletion of $X[7]$, and a deletion of $Y[8]$, respectively.
Graphically, the alignment is depicted on the right; the aligned pairs of
characters are connected with an edge, and the substituted pair is
highlighted.

Given an alignment $\mathcal{A}=(x_{t},y_{t})_{t=1}^{m}$ of $X$ and $Y$, for
every $\ell,r\in[1\mathinner{.\,.\allowbreak}m]$ with $\ell\leq r$, we say
that $\mathcal{A}$ _aligns_ $X[x_{\ell}\mathinner{.\,.\allowbreak}x_{r})$ and
$Y[y_{\ell}\mathinner{.\,.\allowbreak}y_{r})$, denoted
$X[x_{\ell}\mathinner{.\,.\allowbreak}x_{r})\sim_{\mathcal{A}}Y[y_{\ell}\mathinner{.\,.\allowbreak}y_{r})$.
If there is no breakpoint $(x_{t},y_{t})$ with
$t\in[\ell\mathinner{.\,.\allowbreak}r)$, we further say that $\mathcal{A}$
_matches_ $X[x_{\ell}\mathinner{.\,.\allowbreak}x_{r})$ and
$Y[y_{\ell}\mathinner{.\,.\allowbreak}y_{r})$, denoted
$X[x_{\ell}\mathinner{.\,.\allowbreak}x_{r})\simeq_{\mathcal{A}}Y[y_{\ell}\mathinner{.\,.\allowbreak}y_{r})$.

An alignment $\mathcal{A}=(x_{t},y_{t})_{t=1}^{m}$ of $X,Y\in\Sigma^{*}$
naturally induces a unique alignment of any two fragments
$X[x\mathinner{.\,.\allowbreak}x^{\prime})$ and
$Y[y\mathinner{.\,.\allowbreak}y^{\prime})$. Formally, the _induced alignment_
$\mathcal{A}_{[x\mathinner{.\,.\allowbreak}x^{\prime}),[y\mathinner{.\,.\allowbreak}y^{\prime})}$
is obtained by removing repeated entries from
$(\max(x,\min(x^{\prime},x_{t}))-x+1,\max(y,\min(y^{\prime},y_{t}))-y+1)_{t=1}^{m}$.

######  Fact 2.3.

If an alignment $\mathcal{A}$ satisfies
$X[x\mathinner{.\,.\allowbreak}x^{\prime})\sim_{\mathcal{A}}Y[y\mathinner{.\,.\allowbreak}y^{\prime})$,
then $|x-x^{\prime}|,|y-y^{\prime}|\leq 0pt(\mathcal{A})$ and
$|(x^{\prime}-x)-(y^{\prime}-y)|\leq\mathsf{ed}(X[x\mathinner{.\,.\allowbreak}x^{\prime}),Y[y\mathinner{.\,.\allowbreak}y^{\prime}))\leq\mathsf{cost}(\mathcal{A}_{[x\mathinner{.\,.\allowbreak}x^{\prime}),[y\mathinner{.\,.\allowbreak}y^{\prime})})\leq\mathsf{cost}(\mathcal{A})$.

##  3 Technical Overview

In this section, we provide an overview of our conceptual and technical
contribution. Let us start with a formal statement of the pattern matching
with $k$ edits problem. We say that $T[\ell\mathinner{.\,.\allowbreak}r]$ is a
_$k$ -edit occurrence_ of $P$ if
$\mathsf{ed}(P,T[\ell\mathinner{.\,.\allowbreak}r])\leq k$, and we denote the
set of the _right_ endpoints of the $k$-edit occurrences of $P$ in $T$ by
$\mathsf{OCC}^{E}_{k}(P,T)$.

######  Problem 3.1 (Pattern matching with $k$ edits).

Given a pattern $P$ of length $m$ over an alphabet $\Sigma$, a text $T$ of
length $n$ over $\Sigma$, and an integer $k$, compute
$\mathsf{OCC}_{k}^{E}(P,T)$.

We solve an _online_ version of the problem, where the text arrives in a
stream (character by character) and the algorithm must decide whether
$r\in\mathsf{OCC}^{E}_{k}(P,T)$ while processing $T[r]$. The pattern is
preprocessed in advance (consistently with [52], in the current version of
this paper we do not account for this preprocessing in the complexity
analysis). We consider two settings:

  1. 1.

In the _streaming_ setting, the algorithm can no longer access $P$ or
$T[1\mathinner{.\,.\allowbreak}r)$ while processing $T[r]$. In other words,
all the information regarding these strings needs to be stored explicitly and
accounted for in the space complexity of the algorithm.

  2. 2.

In the _semi-streaming_ setting, the algorithm can no longer access
$T[1\mathinner{.\,.\allowbreak}r)$ while processing $T[r]$, but it is given an
oracle providing read-only constant-time access to individual characters of
$P$. This oracle is not counted towards the space complexity of the algorithm.

For the semi-streaming setting, we provide a deterministic solution, whereas
our solution for the streaming setting is Monte-Carlo randomized. Both
algorithms are designed for the $w$-bit word RAM model, where $w=\Omega(\log
n)$, and integer alphabets
$\Sigma=[0\mathinner{.\,.\allowbreak}n^{\mathcal{O}(1)})$.

###  3.1 (Semi-)Streaming Algorithm for Pattern Matching with $k$ Edits

Our algorithms solve a slightly stronger problem: every element
$r\in\mathsf{OCC}_{k}^{E}(P,T)$ is augmented with the smallest integer
$k^{\prime}\in[0\mathinner{.\,.\allowbreak}k]$ such that
$r\in\mathsf{OCC}_{k^{\prime}}^{E}(P,T)$. At a very high-level, we reuse the
structure of existing streaming algorithms for exact pattern matching and the
$k$-mismatch problem [52, 7, 14, 16]. Namely, we consider $\mathcal{O}(\log
m)$ prefixes $P_{i}=P[1\mathinner{.\,.\allowbreak}\ell_{i}]$ of exponentially
increasing lengths $\ell_{i}$. The algorithms are logically decomposed into
$\mathcal{O}(\log m)$ levels, with the $i$th level receiving
$\mathsf{OCC}_{k}^{E}(P_{i-1},T)$ and producing
$\mathsf{OCC}_{k}^{E}(P_{i},T)$. In other words, the task of the $i$th level
is determine which $k$-edit occurrences of $P_{i-1}$ can be extended to
$k$-edit occurrences of $P_{i}$. When the algorithm processes $T[r]$, the
relevant positions $p\in\mathsf{OCC}_{k}^{E}(P_{i-1},T)$ are those satisfying
$|r-p-(\ell_{i}-\ell_{i-1})|\leq k$. Since each
$p\in\mathsf{OCC}_{k}^{E}(P_{i-1},T)$ is reported when the algorithm processes
$T[p]$, we need a buffer storing the _active_ $k$-edit occurrences of
$P_{i-1}$. We implement it using a recent combinatorial characterization of
$k$-edit occurrences [12], which classifies strings based on the following
notion of approximate periodicity:

######  Definition 3.2 ($k$-periodic string).

A string $X$ is _$k$ -periodic_ if there exists a primitive string $Q$ with
$|Q|\leq|X|/128k$ such that the edit distance between $X$ and a prefix of
$Q^{\infty}$ is at most $2k$. We call $Q$ a _$k$ -period_ of $X$.

The main message of [12] is that only $k$-periodic strings may have many
$k$-edit occurrences.

######  Corollary 3.3 (of [12, Theorem 5.1]).

Let $X\in\Sigma^{m}$, $k\in[1\mathinner{.\,.\allowbreak}m]$, and
$Y\in\Sigma^{n}$ with $n\leq 2m$. If $X$ is not $k$-periodic, then
$|\mathsf{OCC}_{k}^{E}(X,Y)|=\mathcal{O}(k^{2})$.

In particular, if $P_{i-1}$ is not $k$-periodic, then it has
$\mathcal{O}(k^{2})$ active $k$-edit occurrences. For each active occurrence
$p\in\mathsf{OCC}_{k}^{E}(P_{i-1},T)$, we maintain an edit-distance sketch
$\mathsf{sk}^{E}_{k}(T(p\mathinner{.\,.\allowbreak}r])$ and combine it with a
sketch $\mathsf{sk}^{E}_{k}(P(\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}])$
(constructed at preprocessing) in order to derive
$\mathsf{ed}(T(p\mathinner{.\,.\allowbreak}r],P(\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}])$
or certify that this distance exceeds $k$. Since we have stored the smallest
$k^{\prime}\in[0\mathinner{.\,.\allowbreak}k]$ such that
$p\in\mathsf{OCC}_{k^{\prime}}^{E}(P,T)$, this lets us check whether any
$k$-edit occurrence of $P_{i-1}$ ending at position $p$ extends to a $k$-edit
occurrence of $P_{i}$ ending at position $r$. With existing $k$-edit sketches
[6, 37], this already yields an $\mathrm{poly}(k\log n)$-space implementation
in this case.

The difficulty lies in $k$-periodic strings whose occurrences form _chains_.

######  Definition 3.4 (Chain of occurrences).

Consider strings $X,Y\in\Sigma^{*}$ and an integer $k\in\mathbb{Z}_{\geq 0}$.
An increasing sequence of positions $p_{1},\ldots,p_{c}$ forms a _chain_ of
$k$-edit occurrences of $X$ in $Y$ if:

  1. 1.

there is a _difference_ string $D\in\Sigma^{*}$ such that
$D=Y(p_{j}\mathinner{.\,.\allowbreak}p_{j+1}]$ for
$j\in[1\mathinner{.\,.\allowbreak}c)$, and

  2. 2.

there is an integer $k^{\prime}\in[0\mathinner{.\,.\allowbreak}k]$ such that
$p_{j}\in\mathsf{OCC}_{k^{\prime}}^{E}(X,Y)\setminus\mathsf{OCC}_{k^{\prime}-1}^{E}(X,Y)$
for $j\in[1\mathinner{.\,.\allowbreak}c]$.

######  Corollary 3.5 (of [12, Theorem 5.2, Claim 5.16, Claim 5.17]).

Let $X\in\Sigma^{m}$, $k\in[1\mathinner{.\,.\allowbreak}m]$, and
$Y\in\Sigma^{n}$ with $n\leq 2m$. If $X$ is $k$-periodic with period $Q$, then
$\mathsf{OCC}_{k}^{E}(X,Y)$ can be decomposed into $\mathcal{O}(k^{3})$ chains
whose differences are of the form $\mathsf{rot}^{s}(Q)$ with $|m-s|\leq 10k$.

In the following discussion, assume that $P_{i-1}$ is $k$-periodic with period
$Q_{i-1}$. Compared to the previous algorithm, we cannot afford maintaining a
sketch $\mathsf{sk}^{E}_{k}(T(p\mathinner{.\,.\allowbreak}r])$ for all active
$p\in\mathsf{OCC}_{k}^{E}(P,T)$. If $\mathsf{sk}^{E}_{k}$ were a rolling
sketch (like the $k$-mismatch sketches of [16]), we would compute
$\mathsf{sk}^{E}_{k}(D)$ at preprocessing time for all $\mathcal{O}(k)$
feasible chain differences $D$ and then, for any two subsequent positions
$p_{j},p_{j+1}$ in a chain with difference $D$, we could use
$\mathsf{sk}^{E}_{k}(D)=\mathsf{sk}^{E}_{k}(T(p_{j}\mathinner{.\,.\allowbreak}p_{j+1}])$
to transform $\mathsf{sk}^{E}_{k}(T(p_{j}\mathinner{.\,.\allowbreak}r])$ into
$\mathsf{sk}^{E}_{k}(T(p_{j+1}\mathinner{.\,.\allowbreak}r])$. However,
despite extensive research, no rolling edit distance sketch is known, which
remains the main obstacle in designing streaming algorithms for approximate
pattern matching with $k$ edits.

Our workaround relies on a novel _encoding_ $\mathsf{qGR}(X,Y)$ that, for a
pair of strings $X,Y\in\Sigma^{*}$, represents a large class of low-distance
edit distance alignments between $X,Y$. In the preprocessing phase of our
algorithm, we build
$\mathsf{qGR}(P(\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\ell_{i}-\ell_{i-1}])$
for every feasible chain difference $D$. In the main phase, for subsequent
positions $p_{j}\in\mathsf{OCC}_{k}^{E}(P_{i-1},T)$ in a chain with difference
$D$, we aim to build
$\mathsf{qGR}(T(p_{j}\mathinner{.\,.\allowbreak}r],D^{\infty}[1\mathinner{.\,.\allowbreak}\ell_{i}-\ell_{i-1}])$
when necessary, i.e., $|r-p_{j}-(\ell_{i}-\ell_{i-1})|\leq k$. We then combine
the two encodings to derive
$\mathsf{qGR}(P(\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}],T(p_{j}\mathinner{.\,.\allowbreak}r])$
and
$\mathsf{ed}(P(\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}],T(p_{j}\mathinner{.\,.\allowbreak}r])$.
Except for such _products_ (transitive compositions), our encoding supports
_concatenations_ , i.e., $\mathsf{qGR}(X_{1},Y_{1})$ and
$\mathsf{qGR}(X_{2},Y_{2})$ can be combined into
$\mathsf{qGR}(X_{1}X_{2},Y_{1}Y_{2})$. Consequently, it suffices to maintain
$\mathsf{qGR}(T(p_{c}\mathinner{.\,.\allowbreak}r],D^{\infty}[1\mathinner{.\,.\allowbreak}r-p_{c}-k])$
(where $p_{c}$ is the rightmost element of the chain). When necessary, we
prepend $(j-c)$ copies of $\mathsf{qGR}(D,D)$ (merged by doubling) and append
$\mathsf{qGR}(\varepsilon,D^{\infty}(r-p_{j}-k\mathinner{.\,.\allowbreak}\ell_{i}-\ell_{i-1}])$
to derive
$\mathsf{qGR}(P(\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\ell_{i}-\ell_{i-1}])$.

In the semi-streaming setting, we extend
$\mathsf{qGR}(T(p_{c}\mathinner{.\,.\allowbreak}r],D^{\infty}[1\mathinner{.\,.\allowbreak}r-p_{c}-k])$
one character at a time using read-only random access to $D^{\infty}$. In the
streaming setting, we cannot afford storing $D$, so we append the entire
difference $D$ in a single step and utilize a new edit-distance sketch
$\mathsf{sk}^{\mathsf{q}}$ that allows retrieving
$\mathsf{qGR}(T(r-|D|\mathinner{.\,.\allowbreak}r],D)$ from
$\mathsf{sk}^{\mathsf{q}}(T(r-|D|\mathinner{.\,.\allowbreak}r])$ and
$\mathsf{sk}^{\mathsf{q}}(D)$. The sketch $\mathsf{sk}^{\mathsf{q}}(D)$ is
constructed in the preprocessing phase, whereas
$\mathsf{sk}^{\mathsf{q}}(T(r-|D|\mathinner{.\,.\allowbreak}r])$ is built as
the algorithm scans $T$. Similarly, we can (temporarily) append any of the
$\mathcal{O}(k)$ prefixes that of $D$ may arise when
$\mathsf{qGR}(T(p_{c}\mathinner{.\,.\allowbreak}r],D^{\infty}[1\mathinner{.\,.\allowbreak}r-p_{c}-k])$
is necessary. A complete presentation of our algorithms is provided in Section
7. Below, we outline the ideas behind our two main conceptual and technical
contributions: the encoding $\mathsf{qGR}(\cdot,\cdot)$ and the sketch
$\mathsf{sk}^{\mathsf{q}}(\cdot)$.

###  3.2 Greedy Alignments and Encodings

Recall that the encoding $\mathsf{qGR}(\cdot,\cdot)$ needs to support the
following three operations:

Capped edit distance:

given $\mathsf{qGR}(X,Y)$, compute $\mathsf{ed}(X,Y)$ or certify that
$\mathsf{ed}(X,Y)$ is large;

Product:

given $\mathsf{qGR}(X,Y)$ and $\mathsf{qGR}(Y,Z)$, retrieve
$\mathsf{qGR}(X,Z)$;

Concatenation:

given $\mathsf{qGR}(X_{1},Y_{1})$ and $\mathsf{qGR}(X_{2},Y_{2})$, retrieve
$\mathsf{qGR}(X_{1}X_{2},Y_{1}Y_{2})$.

Our encoding is parameterized with a threshold $k\in\mathbb{Z}_{+}$ such that
$\mathsf{ed}(\cdot,\cdot)>k$ is considered large, and the goal is to achieve
$\tilde{\mathcal{O}}(k^{\mathcal{O}(1)})$ encoding size. In fact, whenever
$\mathsf{ed}(X,Y)>k$, we shall simply assume that $\mathsf{qGR}_{k}(X,Y)$ is
undefined (formally, $\mathsf{qGR}_{k}(X,Y)=\bot$). Consequently, products and
concatenations will require sufficiently large thresholds in the input
encodings so that if either of them is undefined, the output encoding is also
undefined.

In order to support concatenations alone, we could use so-called _semi-local_
edit distances. For now, suppose that we only need to encode pairs of equal-
length strings.444Pairs of strings of any lengths can be supported in the same
way provided that concatenations require larger input thresholds (compared to
the output threshold) to accommodate length differences. Through a sequence of
concatenations, we may only extend $\mathsf{qGR}_{k}(X,Y)$ to
$\mathsf{qGR}_{k}(X^{\prime},Y^{\prime})$ so that
$X=X^{\prime}[\ell\mathinner{.\,.\allowbreak}r)$ and
$Y=Y^{\prime}[\ell\mathinner{.\,.\allowbreak}r)$. For any alignment
$\mathcal{A}^{\prime}$ of $X^{\prime},Y^{\prime}$ with
$\mathsf{cost}(\mathcal{A}^{\prime})\leq k$, consider the induced alignment
$\mathcal{A}:=\mathcal{A}^{\prime}_{[\ell\mathinner{.\,.\allowbreak}r),[\ell\mathinner{.\,.\allowbreak}r)}$.
Note that $\mathcal{A}$ mimics the behavior of $\mathcal{A}^{\prime}$ except
that it deletes some characters at the extremes of $X$ and $Y$ (which
$\mathcal{A}^{\prime}$ aligns outside $Y$ and $X$, respectively). By Fact 2.3,
we have $\mathsf{cost}(\mathcal{A})\leq k$ and, in particular, $\mathcal{A}$
deletes at most $k$ characters at the extremes of $X$ and $Y$. If, after
performing these deletions, we replace $\mathcal{A}$ with an optimal alignment
between the remaining fragments of $X$ and $Y$, this modification may only
decrease $\mathsf{cost}(\mathcal{A})$ and
$\mathsf{cost}(\mathcal{A}^{\prime})$. Consequently, it suffices to store the
$\mathcal{O}(k)$ characters at the extremes of $X,Y$ and the
$\mathcal{O}(k^{4})$ edit distances555In fact, $\mathcal{O}(k^{2})$ edit
distances suffice and they can be encoded in $\mathcal{O}(k)$ space using
techniques of Tiskin [58]. between long fragments of $X$ and $Y$. In a sense,
this encoding represents $\mathcal{O}(k^{4})$ alignments between $X,Y$ that
are sufficient to derive an optimal alignment of any extension.

The main challenge is to handle products, for which we develop a _greedy
encoding_ $\mathsf{GR}_{k}(X,Y)$ that compactly represents the following
family $\mathsf{GA}_{k}(X,Y)$ of _greedy alignments_ of $X,Y$.

######  Definition 3.6 (Greedy alignment).

We say that an alignment $\mathcal{A}$ of two strings $X,Y\in\Sigma^{*}$ is
_greedy_ if $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([1\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|])$.
Given $k\geq 0$, we denote by $\mathsf{GA}_{k}(X,Y)$ the set of all greedy
alignments $\mathcal{A}$ of $X,Y$ satisfying $\mathsf{cost}(\mathcal{A})\leq
k$.

Intuitively, whenever a greedy alignment encounters a pair of matching
characters $X[x]$ and $Y[y]$, it must (greedily) match these characters (it
cannot delete $X[x]$ or $Y[y]$). As stated below, this restriction does not
affect the optimal cost. (All claims are proved in Section 5.)

######  Fact 3.7.

For any two strings $X,Y\in\Sigma^{*}$, there is an optimal greedy alignment
of $X,Y$.

For strings $X,Y\in\Sigma^{*}$ and an integer $k\geq\mathsf{ed}(X,Y)$, we
define a set $\mathcal{M}_{k}(X,Y)$ of _common matches_ of all alignments
$\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$; formally
$\mathcal{M}_{k}(X,Y)=\bigcap_{\mathcal{A}\in\mathsf{GA}_{k}(X,Y)}\mathcal{M}_{X,Y}(\mathcal{A})$.
In our greedy encoding, we shall mask out all the characters involved in the
common matches. Below, this transformation is defined for an arbitrary non-
crossing matching of ${X,Y}$.

######  Definition 3.8.

Let $M$ be a non-crossing matching of strings $X,Y\in\Sigma^{*}$. We define
$X^{M},Y^{M}$ to be the strings obtained from $X,Y$ by replacing $X[x]$ and
$Y[y]$ with $\\#\notin\Sigma$ for every $(x,y)\in M$. We refer to $\\#$ as a
_dummy symbol_ and to maximal blocks of $\\#$’s as _dummy segments_.

The following lemma proves that masking out common matches does not affect
$\mathsf{ed}(X,Y)$ or $\mathcal{M}_{k}(X,Y)$ provided that we _enumerate_ the
dummy symbols, that is, any string $Z$ is transformed to $\mathsf{num}(Z)$ by
replacing the $i$th leftmost occurrence of $\\#$ with a unique symbol
$\\#_{i}\notin\Sigma$.

######  Lemma 3.9.

Consider strings $X,Y\in\Sigma^{*}$, an integer $k\geq\mathsf{ed}(X,Y)$, and a
set $M\subseteq\mathcal{M}_{k}(X,Y)$. Then,
$\mathsf{ed}(X,Y)=\mathsf{ed}(\mathsf{num}(X^{M}),\mathsf{num}(Y^{M}))$ and
$\mathcal{M}_{k}(X,Y)=\mathcal{M}_{k}(\mathsf{num}(X^{M}),\mathsf{num}(Y^{M}))$.

At the same time, after masking out the common matches, the strings become
compressible. Intuitively, this is because once two greedy alignments
converge, they stay together until they encounter a mismatch. Moreover, when
two alignments proceed in parallel without any mismatch, this incurs a small
period (at most $2k$) that is captured by the LZ factorization.

######  Lemma 3.10.

Let $M=\mathcal{M}_{k}(X,Y)$ for strings $X,Y\in\Sigma^{*}$ and a positive
integer $k\geq\mathsf{ed}(X,Y)$. Then,
$|\mathsf{LZ}(X^{M})|,|\mathsf{LZ}(Y^{M})|=\mathcal{O}(k^{2})$, and
$X^{M},Y^{M}$ contain $\mathcal{O}(k)$ dummy segments.

Consequently, for $k\geq\mathsf{ed}(X,Y)$, we could define the _greedy
encoding_ $\mathsf{GR}_{k}(X,Y)$ so that it consists of $\mathsf{LZ}(X^{M})$
and $\mathsf{LZ}(Y^{M})$. Instead, we use a more powerful compressed
representation (developed in Section 4) that supports more efficient queries
concerning $X^{M}$ and $Y^{M}$.

Even though $\mathsf{GR}_{k}(X,Y)$ is small, $\mathsf{GA}_{k}(X,Y)$ may
consist of $2^{\Theta(k)}$ alignments, which is why constructing
$\mathsf{GR}_{k}(X,Y)$ in $\mathrm{poly}(k)$ time is far from trivial. The
following combinatorial lemma lets us obtain an $\mathcal{O}(k^{5})$-time
algorithm in Section 5.2. Intuitively, the alignments in
$\mathsf{GA}_{k}(X,Y)$ can be interpreted as paths in a directed acyclic graph
with $\mathcal{O}(k^{5})$ branching vertices.

######  Lemma 3.11.

For all $X,Y\in\Sigma^{*}$ and $k\in\mathbb{Z}_{+}$, the set
$\mathcal{B}_{k}(X,Y)=\bigcup\limits_{\mathcal{A}\in\mathsf{GA}_{k}(X,Y)}\mathcal{B}(\mathcal{A})$
is of size $\mathcal{O}(k^{5})$.

The reason why $\mathsf{GR}_{k}(X,Y)$ supports products is that every greedy
alignment of $X,Z$ can be interpreted as a product of a greedy alignment of
$X,Y$ and a greedy alignment of $Y,Z$.

######  Definition 3.12.

Consider strings $X,Y,Z\in\Sigma^{*}$, an alignment $\mathcal{A}^{X,Y}$ of
$X,Y$, an alignment $\mathcal{A}^{Y,Z}$ of $Y,Z$, and an alignment
$\mathcal{A}^{X,Z}$ of $X,Z$. We say that $\mathcal{A}^{X,Z}$ is a _product_
of $\mathcal{A}^{X,Y}$ and $\mathcal{A}^{Y,Z}$ if, for every
$(x,z)\in\mathcal{A}^{X,Z}$, there is
$y\in[1\mathinner{.\,.\allowbreak}|Y|+1]$ such that
$(x,y)\in\mathcal{A}^{X,Y}$ and $(y,z)\in\mathcal{A}^{Y,Z}$.

######  Lemma 3.13.

Consider strings $X,Y,Z\in\Sigma^{*}$ and $k\in\mathbb{Z}_{\geq 0}$. Every
alignment $\mathcal{A}^{X,Z}\in\mathsf{GA}_{k}(X,Z)$ is a product of
alignments $\mathcal{A}^{X,Y}\in\mathsf{GA}_{d}(X,Y)$ and
$\mathcal{A}^{Y,Z}\in\mathsf{GA}_{d}(Y,Z)$, where $d=2k+\mathsf{ed}(X,Y)$.

As a result, $\mathsf{GR}_{d}(X,Y)$ and $\mathsf{GR}_{d}(Y,Z)$ contain enough
information to derive $\mathsf{GR}_{k}(X,Z)$. The underlying algorithm
propagates the characters of $Y$ stored in $\mathsf{GR}_{d}(X,Y)$ and
$\mathsf{GR}_{d}(Y,Z)$ along the matchings $\mathcal{M}_{d}(Y,Z)$ and
$\mathcal{M}_{d}(X,Y)$, respectively. Then, $\mathsf{GR}_{k}(X,Z)$ is obtained
by masking out all the characters corresponding to $\mathcal{M}_{k}(X,Y)$ (see
Section 5.4 for details).

To support concatenations, we extend the family $\mathsf{GA}_{k}(X,Y)$ of
greedy alignments to a family $\mathsf{qGA}_{k}(X,Y)$ of _quasi-greedy
alignments_ , which are allowed to delete a prefix of $X$ or $Y$ in violation
of Definition 3.6. The _quasi-greedy encoding_ $\mathsf{qGR}_{k}(X,Y)$ is
defined analogously to $\mathsf{GR}_{k}(X,Y)$. Equivalently,
$\mathsf{qGA}_{k}(X,Y)$ can be derived from
$\mathsf{GA}_{k+1}(\$_{1}X,\$_{2}Y)$, where $\$_{1}\neq\$_{2}$ are sentinel
symbols outside $\Sigma$, by taking the alignments induced by $X,Y$. The
latter characterization makes all our claims regarding $\mathsf{GA}$ and
$\mathsf{GR}$ easily portable to $\mathsf{qGA}$ and $\mathsf{qGR}$ (see
Section 5.3). In particular, this is true for the sketches, described in the
following subsection for $\mathsf{GR}$ only.

###  3.3 Edit Distance Sketches

Recall that we need an edit-distance sketch $\mathsf{sk}^{E}$ allowing to
retrieve $\mathsf{GR}_{k}(X,Y)$ from $\mathsf{sk}^{E}_{k}(X)$ and
$\mathsf{sk}^{E}_{k}(Y)$ for any strings $X,Y\in\Sigma^{\leq n}$ and any
threshold $k\in[0\mathinner{.\,.\allowbreak}n]$. Furthermore, we need to make
sure that $\mathsf{sk}^{E}_{k}(S)$ can be computed given streaming access to
$S\in\Sigma^{\leq n}$, and that the encoding and decoding procedures use
$\mathrm{poly}(k,\log n)$ space. While the existing sketches [6, 37] are
designed to compute the exact edit distance $\mathsf{ed}(X,Y)$ capped with
$k$, we believe that they could be adapted to output $\mathsf{qGR}_{k}(X,Y)$.
Nevertheless, these sketches are relatively large (taking
$\tilde{\mathcal{O}}(k^{8})$ and $\tilde{\mathcal{O}}(k^{3})$ bits,
respectively), and we would need to strengthen the bulk of their analyses to
prove that, in principle, they provide enough information to retrieve
$\mathsf{qGR}_{k}(X,Y)$. Hence, to further demonstrate the power of our
techniques, we devise a novel $\tilde{\mathcal{O}}(k^{2})$-size sketch
specifically designed to output $\mathsf{qGR}_{k}(X,Y)$. We note that the
$\tilde{\mathcal{O}}(k^{2})$ size is optimal for $\mathsf{qGR}_{k}(X,Y)$, but
we are not aware of a matching lower bound for retrieving $\mathsf{ed}(X,Y)$
capped with $k$.

Just like the sketches of [6, 37], ours relies on the embedding of
Chakraborty, Goldenberg, and Koucký [10]. The CGK algorithm performs a random
walk over the input string (with forward and stationary steps only). In
abstract terms, such walk can be specified as follows:

######  Definition 3.14 (Complete walk).

For a string $S\in\Sigma^{*}$, we say that $(s_{t})_{t=1}^{m+1}$ is an _$m$
-step complete walk over $S$_ if $s_{1}=1$, $s_{m+1}=|S|+1$, and
$s_{t+1}\in\\{s_{t},s_{t}+1\\}$ for $t\in[1\mathinner{.\,.\allowbreak}m]$.

For any two strings $X,Y\in\Sigma^{*}$, the two walks underlying
$\mathsf{CGK}(X)$ and $\mathsf{CGK}(Y)$ can be interpreted as an edit distance
alignment using the following abstract definition:

######  Definition 3.15 (Zip alignment).

The _zip alignment_ of $m$-step complete walks $(x_{t})_{t=1}^{m+1}$ and
$(y_{t})_{t=1}^{m+1}$ over ${X,Y\in\Sigma^{*}}$ is obtained by removing
repeated entries in $(x_{t},y_{t})_{t=1}^{m+1}$.

The key result of [10] is that the cost of the zip alignment of CGK walks over
$X,Y\in\Sigma^{*}$ is $\mathcal{O}(\mathsf{ed}(X,Y)^{2})$ with good
probability, which is then exploited to derive a metric embedding (mapping
edit distance to Hamming distance) with quadratic distortion. In our sketch,
we also need to observe that the CGK alignment is greedy and that its width is
$\mathcal{O}(\mathsf{ed}(X,Y))$ with good probability. The following
proposition, proved in Section 6.1, provides a complete black-box interface of
the properties of the CGK algorithm utilized in our sketches. It also
encapsulates Nisan’s pseudorandom generator [50] that reduces the number of
(shared) random bits.

######  Proposition 3.16.

For every constant $\delta\in(0,1)$, there exists a constant $c$ and an
algorithm $\mathsf{W}$ that, given an integer $n$, a seed $r$ of
$\mathcal{O}(\log^{2}n)$ random bits, and a string $S\in\Sigma^{\leq n}$,
outputs a $3n$-step complete walk $\mathsf{W}(n,r,S)$ over $S$ satisfying the
following property for all $X,Y\in\Sigma^{\leq n}$ and the zip alignment
$\mathcal{A}_{\mathsf{W}}$ of $\mathsf{W}(n,r,X)$ and $\mathsf{W}(n,r,Y)$:

$\Pr_{r}\left[\mathcal{A}_{\mathsf{W}}\in\mathsf{GA}_{c\cdot\mathsf{ed}(X,Y)^{2}}(X,Y)\text{
and }0pt(\mathcal{A}_{\mathsf{W}})\leq c\cdot\mathsf{ed}(X,Y)\right]\geq
1-\delta.$

Moreover, $\mathsf{W}$ is an $\mathcal{O}(\log^{2}n)$-bit streaming algorithm
that costs $\mathcal{O}(n\log n)$ time and reports any element
$s_{t}\in[1\mathinner{.\,.\allowbreak}|S|]$ of $\mathsf{W}(n,r,S)$ while
processing the corresponding character $S[s_{t}]$.

Next, we analyze the structural similarity between $\mathcal{A}_{\mathsf{W}}$
and any alignment $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$. Based on Proposition
3.16, we may assume that
$\mathcal{A}_{\mathsf{W}}\in\mathsf{GA}_{\mathcal{O}(k^{2})}(X,Y)$ and
$0pt(\mathcal{A}_{\mathsf{W}})=\mathcal{O}(k)$. Consider the set
$M=\mathcal{M}(\mathcal{A})\cap\mathcal{M}(\mathcal{A}_{\mathsf{W}})$ of the
common matches of $\mathcal{A}$ and $\mathcal{A}_{\mathsf{W}}$ and the string
$X^{M}$ obtained by masking out the underlying characters of $X$. Whereas
Lemma 3.10 immediately implies that the $\mathsf{LZ}$ factorization of $X^{M}$
consists of $\mathcal{O}(k^{4})$ phrases, a more careful application of the
same technique provides a refined bound of $\mathcal{O}(k^{2})$ phrases.
Furthermore, there are $\mathcal{O}(k)$ dummy segments in $X^{M}$ and, if
$X[x]$ is not masked out in $X^{M}$ (for some
$x\in[1\mathinner{.\,.\allowbreak}|X|]$), then there is a breakpoint
$(x^{\prime},y^{\prime})\in\mathcal{B}_{X,Y}(\mathcal{A}_{\mathsf{W}})$ with
$x^{\prime}\in[1\mathinner{.\,.\allowbreak}x]$ and
$|\mathsf{LZ}(X[x^{\prime}\mathinner{.\,.\allowbreak}x])|=\mathcal{O}(k)$.
Intuitively, this means that $\mathcal{A}$ and $\mathcal{A}_{\mathsf{W}}$
diverge only within highly compressible regions following the breakpoints
$\mathcal{B}_{X,Y}(\mathcal{A}_{\mathsf{W}})$. We call these regions _forward
contexts_ (formally, a forward context is the longest fragment starting at a
given position and satisfying certain compressiblity condition). Since our
choice of $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$ was arbitrary, any two
alignments $\mathcal{A},\mathcal{A}^{\prime}\in\mathsf{GA}_{k}(X,Y)$ diverge
only within these forward contexts. Hence, in order to reconstruct
$\mathsf{GR}_{k}(X,Y)$ and, in particular, $X^{\mathcal{M}_{k}(X,Y)}$, the
sketch should be powerful enough to retrieve all characters in forward
contexts of breakpoints $\mathcal{B}_{X,Y}(\mathcal{A}_{\mathsf{W}})$. Even
though $\mathcal{B}_{X,Y}(\mathcal{A}_{\mathsf{W}})$ could be of size
$\Theta(k^{2})$, due to the aforementioned bounds on $|\mathsf{LZ}(X^{M})|$
and the number of dummy segments in $X^{M}$, it suffices to take
$\mathcal{O}(k)$ among these forward contexts to cover the unmasked regions of
$X^{M}$ and $X^{\mathcal{M}_{k}(X,Y)}$. Each context can be encoded in
$\tilde{\mathcal{O}}(k)$ bits, so this paves a way towards sketches of size
$\tilde{\mathcal{O}}(k^{2})$.

Nevertheless, while processing a string $X\in\Sigma^{\leq n}$, we only have
access to the string $X$ and the $m$-complete walk
$(x_{t})_{t=1}^{m}=\mathsf{W}(n,r,X)$ over $X$. In particular, depending on
$Y$, any position in $X$ could be involved in a breakpoint. A naive strategy
would be to build a _context encoding_
$\mathsf{CE}(X)[1\mathinner{.\,.\allowbreak}m]$ that stores at
$t\in[1\mathinner{.\,.\allowbreak}m]$ (a compressed representation of) the
forward context starting at $X[x_{t}]$, and then post-process it using a
Hamming-distance sketch. This is sufficiently powerful because $X[x_{t}]\neq
Y[y_{t}]$ holds for any
$(x_{t},y_{t})\in\mathcal{B}(\mathcal{A}_{\mathsf{W}})$ (recall that
$\mathcal{A}_{\mathsf{W}}$ is greedy). Unfortunately, this construction does
not guarantee any upper bound on $\mathsf{hd}(\mathsf{CE}(X),\mathsf{CE}(Y))$
in terms of $k$. (For example, if $X$ is compressible, modifying its final
character of $X$ affects the entire $\mathsf{CE}(X)$.) Hence, we sparsify
$\mathsf{CE}(X)$ by placing a blank symbol $\bot$ at some positions
$\mathsf{CE}(X)[t]$ so that just a few forward contexts stored in
$\mathsf{CE}(X)[t]$ cover any single position in $X$.

This brings two further challenges. First, if $X[x]$ is involved in a
breakpoint, then we are only guaranteed that it is covered by some forward
context $X[p\mathinner{.\,.\allowbreak}q)$ of $\mathsf{CE}(X)[t]$ (i.e.,
$x\in[p\mathinner{.\,.\allowbreak}q)$). In particular, the forward context
starting at position $x$ could extend beyond
$X[x\mathinner{.\,.\allowbreak}q)$. Hence, the string $\mathsf{CE}(X)[t]$
actually stores _double forward contexts_
$X[p\mathinner{.\,.\allowbreak}r)=X[p\mathinner{.\,.\allowbreak}q)X[q\mathinner{.\,.\allowbreak}r)$
defined as the concatenation of the forward contexts of $X[p]$ and $X[q]$. We
expect this double forward context $X[p\mathinner{.\,.\allowbreak}r)$ to cover
the entire forward context of $X[x]$. Unfortunately, this is not necessarily
true if we use the Lempel–Ziv factorization to quantify compressibility: we
could have
$|\mathsf{LZ}(X[x\mathinner{.\,.\allowbreak}r))|<|\mathsf{LZ}(X[q\mathinner{.\,.\allowbreak}r))|$
because $\mathsf{LZ}(\cdot)$ is not monotone. Instead, we use an ad-hoc
compressibility measure defined as
$\overline{\mathsf{maxLZ}}(S)=\max_{[\ell\mathinner{.\,.\allowbreak}r)\subseteq[1\mathinner{.\,.\allowbreak}|S|]}\mathsf{LZ}(\overline{S[\ell\mathinner{.\,.\allowbreak}r)})$.
Here, maximization over substrings guarantees monotonicity whereas reversal
helps designing an efficient streaming algorithm constructing contexts (beyond
the scope of this overview).

Another challenge is that the sparsification needs to be consistent between
$\mathsf{CE}(X)$ and $\mathsf{CE}(Y)$: assuming $\mathsf{ed}(X,Y)\leq k$, we
should have
$\mathsf{hd}(\mathsf{CE}(X),\mathsf{CE}(Y))=\tilde{\mathcal{O}}(k)$, which
also accounts for mismatches between $\bot$ and a stored double forward
context. This rules out a naive strategy of covering $X$ from left to right
using disjoint forward contexts: any substitution at the beginning of $X$
could then have a cascade of consequences throughout $\mathsf{CE}(X)$. Hence,
we opt for a memory-less strategy that decides on $\mathsf{CE}(X)[t]$ purely
based on the forward contexts
$X[x_{t-1}\mathinner{.\,.\allowbreak}x^{\prime}_{t-1})$ and
$X[x_{t}\mathinner{.\,.\allowbreak}x^{\prime}_{t})$. For example, we could set
$\mathsf{CE}(X)[t]=\bot$ unless the smallest dyadic interval containing
$[x_{t-1}\mathinner{.\,.\allowbreak}x^{\prime}_{t-1})$ differs from the
smallest dyadic interval containing
$[x_{t}\mathinner{.\,.\allowbreak}x^{\prime}_{t})$ (a dyadic interval is of
the form $[i2^{j}\mathinner{.\,.\allowbreak}(i+1)2^{j})$ for some integers
$i,j\geq 0$). With this approach, each position of $X$ is covered by at least
one and at most $\mathcal{O}(\log|X|)$ forward contexts. Furthermore,
substituting any character in $X$ does not have far-reaching knock-on effects.
Unfortunately, insertions and deletions are still problematic as they shift
the positions $x_{t}$. Thus, the decision concerning $\mathsf{CE}(X)[t]$
should be independent of the numerical value of $x_{t}$. Consequently, instead
of looking at the smallest dyadic interval containing
$[x_{t}\mathinner{.\,.\allowbreak}x^{\prime}_{t})$, we choose the largest
$t^{\prime}$ such that
$[x_{t}\mathinner{.\,.\allowbreak}x^{\prime}_{t})=[x_{t}\mathinner{.\,.\allowbreak}x_{t^{\prime}})$,
and we look at the smallest dyadic interval containing
$[t\mathinner{.\,.\allowbreak}t^{\prime})$.

With each forward context $X[x_{t}\mathinner{.\,.\allowbreak}x^{\prime}_{t})$
retrieved, we also need to determine the value $x_{t}$ (so that we know which
fragment of $X$ we can learn from $\mathsf{CE}(X)[t]$). To avoid knock-on
effects, we actually store differences $x_{t}-x_{u}$ with respect to the
previous index satisfying $\mathsf{CE}(X)[u]\neq\bot$. This completes the
intuitive description of the context encoding $\mathsf{CE}$ studied in Section
6.2.

Our edit-distance sketch contains the Hamming-distance sketch of
$\mathsf{CE}(X)$. For this, we use an existing construction [16], augmented in
a black-box manner to support large alphabets (recall that the each forward
contexts takes $\tilde{\mathcal{O}}(k)$ bits). Furthermore, to retrieve the
starting positions $x_{t}$ (rather than just the differences $x_{t}-x_{u}$),
we use a hierarchical Hamming-distance sketch similar to those used in [6,
37]. This way, given sketches of $X$ and $Y$, we can recover all characters
that remain unmasked in $X^{\mathcal{M}_{k}(X,Y)}$ and
$Y^{\mathcal{M}_{k}(X,Y)}$. The tools of Section 5 are then used to compute
$\mathsf{ed}(X,Y)$ (or certify $\mathsf{ed}(X,Y)>k$) and retrieve the greedy
encoding $\mathsf{GR}_{k}(X,Y)$ (see Section 6.4). We summarize the properties
of the edit distance sketches below:

######  Theorem 3.17.

For every constant $\delta\in(0,1)$, there is a sketch $\mathsf{sk}^{E}_{k}$
(parametrized by integers $n\geq k\geq 1$, an alphabet
$\Sigma=[0\mathinner{.\,.\allowbreak}n^{\mathcal{O}(1)})$, and a seed of
$\mathcal{O}(\log^{2}n)$ random bits) such that:

  1. (a)

The sketch $\mathsf{sk}^{E}_{k}(S)$ of a string $\Sigma^{\leq n}$ takes
$\mathcal{O}(k^{2}\log^{3}n)$ bits. Given streaming access to $S$, it can be
constructed in $\tilde{\mathcal{O}}(nk)$ time using
$\tilde{\mathcal{O}}(k^{2})$ space.

  2. (b)

There exists an $\tilde{\mathcal{O}}(k^{2})$-space decoding algorithm that,
given $\mathsf{sk}^{E}_{k}(X),\mathsf{sk}^{E}_{k}(Y)$ for $X,Y\in\Sigma^{\leq
n}$, with probability at least $1-\delta$ outputs $\mathsf{GR}_{k}(X,Y)$ and
$\min(\mathsf{ed}(X,Y),k+1)$. Retrieving $\mathsf{GR}_{k}(X,Y)$ costs
$\tilde{\mathcal{O}}(k^{5})$ time, whereas computing
$\min(\mathsf{ed}(X,Y),k+1)$ costs $\tilde{\mathcal{O}}(k^{3})$ time.

##  4 Compressed String Representation

In this section, we develop a data structure that stores a string $X$ in
$\mathcal{O}(|\mathsf{LZ}(X)|\log^{2}|X|)$ space, supporting various
operations in a relatively efficient way (the $\log|X|$ factors are not
optimized).

Our data structure can be constructed not only from $\mathsf{LZ}(X)$, but from
any _LZ-like representation_ describing a factorization $X=F_{1}\cdots F_{f}$
into non-empty phrases such that each phrase $F_{j}$ with $|F_{j}|>1$ is a
previous factor (unlike LZ77, the phrases do not need to be a maximal).

######  Observation 4.1.

Every LZ-like factorization of a string $X\in\Sigma^{*}$ has at least
$|\mathsf{LZ}(X)|$ phrases. Moreover,
$|\mathsf{LZ}(X)|\leq|\mathsf{LZ}(XY)|\leq|\mathsf{LZ}(X)|+|\mathsf{LZ}(Y)|$
holds for all strings $X,Y\in\Sigma^{*}$.

######  Proposition 4.2.

In the $w$-bit word RAM model, every string $X\in\Sigma^{n}$ satisfying
$w=\Omega(\log n+\log|\Sigma|)$, $z=|\mathsf{LZ}(X)|$, and
$\overline{z}=|\mathsf{LZ}(\overline{X})|$ has a representation
$\mathsf{D}(X)$ that uses $\mathcal{O}(z\log^{2}n)$ space and supports the
following queries:

  1. (a)

retrieve $n=|X|$, in $\mathcal{O}(1)$ time;

  2. (b)

given $i\in[1\mathinner{.\,.\allowbreak}n]$, retrieve $X[i]$, in
$\mathcal{O}(\log n)$ time;

  3. (c)

given $i,j\in[1\mathinner{.\,.\allowbreak}n]$, compute
$\mathsf{LCE}(X[i\mathinner{.\,.\allowbreak}n],X[j\mathinner{.\,.\allowbreak}n])$,
in $\mathcal{O}(\log n)$ time;

  4. (d)

given $i,j\in[1\mathinner{.\,.\allowbreak}n]$, compute
$\mathsf{LCE}(\overline{X}[i\mathinner{.\,.\allowbreak}n],\overline{X}[j\mathinner{.\,.\allowbreak}n])$,
in $\mathcal{O}(\log n)$ time;

  5. (e)

compute $\mathsf{LZ}(X)$, in $\mathcal{O}(z\log^{4}n)$ time;

  6. (f)

compute $\mathsf{LZ}(\overline{X})$, in $\mathcal{O}(\overline{z}\log^{4}n)$
time;

  7. (g)

given $i,j\in[1\mathinner{.\,.\allowbreak}n]$ with $i\leq j$, compute
$\mathsf{D}(X[i\mathinner{.\,.\allowbreak}j])$, in $\mathcal{O}(z\log^{4}n)$
time.

Moreover, $\mathsf{D}(X)$ can be constructed:

  1. (h)

in $\mathcal{O}(f\log^{2}n)$ time given an $f$-phrase LZ-like representation
of $X$ or $\overline{X}$;

  2. (i)

in $\mathcal{O}(z\log^{4}n)$ time given
$\mathsf{D}(X[1\mathinner{.\,.\allowbreak}i))$ and
$\mathsf{D}(X[i\mathinner{.\,.\allowbreak}n])$ for some
$i\in[1\mathinner{.\,.\allowbreak}n]$.

Before proving Proposition 4.2, we need to introduce several more compression
schemes. These concepts are not used any of the subsequent sections.

A _straight-line grammar_ is a tuple
$\mathcal{G}=(\mathcal{S},\Sigma,\mathsf{rhs},S)$, where $\mathcal{S}$ is a
finite set of _symbols_ , $\Sigma\subseteq\mathcal{S}$ is a set of _terminal
symbols_ , $\mathsf{rhs}:(\mathcal{S}\setminus\Sigma)\to\mathcal{S}^{*}$ is
the _production_ (or _right-hand side_) function, and $S\in\mathcal{S}$ is the
start symbol. We further require existence of an order $\prec$ on
$\mathcal{S}$ such that $B\prec A$ if $B$ occurs in $\mathsf{rhs}(A)$.

The _expansion_ function $\exp:\mathcal{S}\to\Sigma^{+}$ is defined
recursively:

$\exp(A)=\begin{cases}A&\text{if }A\in\Sigma,\\\
\exp(B_{1})\cdots\exp(B_{k})&\text{if }\mathsf{rhs}(A)=B_{1}\cdots
B_{k},\end{cases}$

We say that $\mathcal{G}$ is a _grammar-compressed representation_ of
$\exp(S)$.

The _parse tree_ $\mathcal{T}(A)$ of a symbol $A\in\mathcal{S}$ is a rooted
ordered tree with each node $\nu$ associated to a symbol
$s(\nu)\in\mathcal{S}$. The root of $\mathcal{T}(A)$ is a node $\rho$ with
$s(\rho)=A$. If $A\in\Sigma$, then $\rho$ has no children. Otherwise, if
$\mathsf{rhs}(A)=B_{1}\cdots B_{k}$, then $\rho$ has $k$ children, and the
subtree rooted at the $i$th child is (a copy of) $\mathcal{T}(B_{i})$. The
parse tree of a grammar $\mathcal{G}$ is defined as the parse tree
$\mathcal{T}(S)$ of the starting symbol $S$, and the height of $\mathcal{G}$
is defined as the height of $\mathcal{T}(S)$.

Each node $\nu$ of $\mathcal{T}(A)$ is associated with an occurrence
$\exp(\nu)$ of $\exp(s(\nu))$ in $\exp(A)$. For the root $\rho$, we define
$\exp(\rho)=\exp(A)[1\mathinner{.\,.\allowbreak}|\exp(A)|]$ to be the whole
$\exp(A)$. Moreover, if $\exp(\nu)=\exp(A)[\ell\mathinner{.\,.\allowbreak}r)$,
$\mathsf{rhs}(s(\nu))=B_{1}\cdots B_{k}$, and $\nu_{1},\ldots,\nu_{k}$ are the
children of $\nu$, then
$\exp(\nu_{i})=\exp(A)[r_{i-1}\mathinner{.\,.\allowbreak}r_{i})$, where
$r_{i}=\sum_{j=1}^{i}|\exp(B_{j})|$ for $0\leq i\leq k$. This way, the
fragments $\exp(\nu_{i})$ form a partition of $\exp(\nu)$, and $\exp(\nu_{i})$
is indeed an occurrence $\exp(s(\nu_{i}))$ in $\exp(A)$.

A _straight-line program_ (SLP) is a straight-line grammar
$\mathcal{G}=(\mathcal{S},\Sigma,\mathsf{rhs},S)$ such that
$|\mathsf{rhs}(A)|=2$ holds for each _nonterminal_
$A\in\mathcal{S}\setminus\Sigma$. In a _run-length straight-line program_
(RLSLP), productions of the form $\mathsf{rhs}(A)=B^{k}$, with
$B\in\mathcal{S}$ and $k\in\mathbb{Z}_{\geq 2}$, are also allowed.

An RLSLP $\mathcal{G}$ of size $g$ (with $g$ symbols) representing a string of
length $n$ can be stored in $\mathcal{O}(g)$ space ($\mathcal{O}(g\log(n+g))$
bits) with each non-terminal $A\in\mathcal{S}\setminus\Sigma$ storing
$\mathsf{rhs}(A)$ (represented by $(B,k)$ if $\mathsf{rhs}(A)=B^{k}$) and
$|\exp(A)|$. This representation allows for efficiently traversing the parse
tree $\mathcal{T}_{\mathcal{G}}$: given a node $\nu$ represented as a pair
$(s(\nu),\exp(\nu))$, it is possible to retrieve in constant time an analogous
representation of any child of $\nu$.

######  Fact 4.3.

Let $\mathcal{G}$ be an RLSLP of size $g$ representing a string $X$.

  1. (a)

An LZ-like factorization of $X$ can be constructed in $\mathcal{O}(g)$ time.

  2. (b)

For every fragment $X[i\mathinner{.\,.\allowbreak}j]$, an RLSLP representing
$X[i\mathinner{.\,.\allowbreak}j]$ can be constructed in $\mathcal{O}(g)$
time.

###### Proof.

We traverse the parse tree $\mathcal{T}(S)$ in pre-order, skipping some
subtrees depending on the application.

(a) For each symbol $A$, we maintain an already visited node $\nu$ with symbol
$s(\nu)=A$, if any. When visiting a node $\nu$, we first check whether any
node $\nu^{\prime}$ with $s(\nu^{\prime})=s(\nu)$ has already been visited. If
so, we retrieve the expansion
$\exp(\nu^{\prime})=X[i^{\prime}\mathinner{.\,.\allowbreak}i^{\prime}+\ell)$,
and we output $(i^{\prime},\ell)$ as a part of the LZ-like representation.
Otherwise, we save $\nu$ as an already visited node with symbol $s(\nu)$ and
proceed as follows:

  * •

If $\nu$ is a leaf, then we output $s(\nu)\in\Sigma$ as a part of the LZ-like
representation.

  * •

If $\nu$ has two children, we process them recursively.

  * •

If $\nu$ has $k\geq 3$ children, we process the first child $\nu_{1}$
recursively, retrieve $\exp(\nu_{1})=X[i\mathinner{.\,.\allowbreak}i+\ell)$,
and output $(i,(k-1)\ell)$ as a part of the LZ-like representation.

The overall running time $\mathcal{O}(g)$ is amortized by the number of
distinct symbols visited.

(b) Here, an intermediate goal is to construct a sequence
$(A_{1},m_{1}),\ldots,(A_{t},m_{t})$ with $A_{p}\in\mathcal{S}$ and
$m_{p}\in\mathbb{Z}_{\geq 1}$ such that
$\exp(A_{1})^{m_{1}}\cdots\exp(A_{t})^{m_{t}}=X[i\mathinner{.\,.\allowbreak}j]$
and $t=\mathcal{O}(g)$. We only visit nodes $\nu$ such that $\exp(\nu)$
intersects $X[i\mathinner{.\,.\allowbreak}j]$.

  * •

If $\exp(\nu)$ is contained in $X[i\mathinner{.\,.\allowbreak}j]$, we simply
output $(s(\nu),1)$ and skip the subtree of $\nu$.

  * •

Otherwise, we determine the children $\nu_{\ell},\ldots,\nu_{r}$ of $\nu$
whose expansions intersect $X[i\mathinner{.\,.\allowbreak}j]$. Then, we
recurse into $\nu_{\ell}$, output $(s(\nu_{\ell}),r-\ell-1)$ if $r>\ell+1$,
and recurse into $\nu_{r}$ if $r>\ell$.

The number of visited nodes is proportional to the height of $\mathcal{G}$ and
thus this traversal takes $\mathcal{O}(g)$ time. In the post-processing, for
each pair $(A_{p},m_{p})$, we create a new symbol $B_{p}$ with
$\mathsf{rhs}(B_{p})=A_{p}^{m_{p}}$ (if $m_{p}\geq 2$) or set $B_{p}$ as an
alias of $A_{p}$ (if $m_{p}=1$). Next, we set $C_{1}$ to be an alias of
$B_{1}$ and, for $p\in[2\mathinner{.\,.\allowbreak}t]$, create a new symbol
$C_{p}$ with $\mathsf{rhs}(C_{p})=C_{p-1}B_{p-1}$. Finally, we return the
extended RLSLP with $C_{t}$ as the new starting symbol. ∎

######  Theorem 4.4 (I [35]).

Let $\mathcal{G}$ be a size-$g$ SLP representing a string $X\in\Sigma^{n}$ and
let $g^{*}$ be the minimum size of an SLP representing $X$. Given
$\mathcal{G}$, in $\mathcal{O}(g\log n)$ time, one can construct a
size-$\mathcal{O}(g^{*}\log n)$ RLSLP representing $X$ and a
size-$\mathcal{O}(g^{*}\log n)$ data structure that answers the following
queries in $\mathcal{O}(\log n)$ time:

Access:

Given $i\in[1\mathinner{.\,.\allowbreak}n]$, retrieve $S[i]$;

LCE queries:

Given $i,j\in[1\mathinner{.\,.\allowbreak}n]$, compute
$\mathsf{LCE}(S[i\mathinner{.\,.\allowbreak}n],S[j\mathinner{.\,.\allowbreak}n])$.

###### Proof of Proposition 4.2.

We define $\mathsf{D}(X)$ so that it consists of two instances of the data
structure of Theorem 4.4, one for $X$ and one for $\overline{X}$, including
the RLSLPs representing $X$ and $\overline{X}$. Thus, the size of
$\mathsf{D}(X)$ is $\mathcal{O}(g^{*}\log n)$, where $g^{*}$ is the minimum
size of an SLP representing $X$ (it is the same for $\overline{X}$).

To implement (h), we first use [39, Theorem 6.1] and build a
size-$\mathcal{O}(f\log n)$ SLP representing $X$ or $\overline{X}$. By
reversing the right-hand sides of all the productions, we obtain an analogous
SLP representing $\overline{X}$ or $X$, respectively. Finally, we pass these
SLPs to the construction algorithm of Theorem 4.4. Overall, the running time
is $\mathcal{O}(f\log^{2}n)$.

In (i), given $\mathsf{D}(X[1\mathinner{.\,.\allowbreak}i))$ and
$\mathsf{D}(X[i\mathinner{.\,.\allowbreak}n])$, we convert the underlying
RLSLPs to LZ-like representations (Fact 4.3), concatenate them into an
$\mathcal{O}(g^{*}\log n)$-phrase LZ-like representation of $X$, and apply
(h). Overall, this takes $\mathcal{O}(g^{*}\log^{3}n)=\mathcal{O}(z\log^{4}n)$
time.

As for (a), we note that $|X|$ can be trivially retrieved from the RLSLP
representing $X$. Queries (b), (c), and (d) are implemented directly using
Theorem 4.4.

In (e), we construct an index of [39, Theorem 6.11] that, given a fragment
$X[i\mathinner{.\,.\allowbreak}i+\ell)$, in $\mathcal{O}(\log^{3}n)$ time
locates the leftmost position $i^{\prime}$ with
$X[i^{\prime}\mathinner{.\,.\allowbreak}i^{\prime}+\ell)=X[i\mathinner{.\,.\allowbreak}i+\ell)$.
This index can be constructed in $\mathcal{O}(g^{*}\log^{3}n)$ time: it is
already based on the RLSLP of Theorem 4.4, and the extra construction time is
$\mathcal{O}(\log^{2}n)$ per RLSLP symbol; see [39, Lemma 6.9]. This way, each
phrase $F_{j}$ of the LZ77 parsing of $X$ can be constructed, by binary
search, with $\mathcal{O}(\log n)$ queries to the index, for a total of
$\mathcal{O}(z\log^{4}n)$ time (see also [51, Section 5]). The algorithm for
(f) is symmetric.

As for (g), we construct an $\mathcal{O}(g^{*}\log n)$-phrase LZ-like
representation of $X[i\mathinner{.\,.\allowbreak}j]$ using Fact 4.3, and then
apply (h). Overall, this takes
$\mathcal{O}(g^{*}\log^{3}n)=\mathcal{O}(z\log^{4}n)$ time. ∎

##  5 Greedy Alignments and Encodings

See 3.6

See 3.7

###### Proof.

Let $\mathcal{A}=(x_{t},y_{t})_{t=1}^{m}$ be an optimal alignment maximizing
the sum $\sum_{t=1}^{m}(x_{t}+y_{t})$. For a proof by contradiction, suppose
that $\mathcal{A}$ is not greedy. Then, there exists
$i\in[1\mathinner{.\,.\allowbreak}m]$ such that
$(x_{i},y_{i})\in\mathcal{B}(A)\cap([1\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|])$
and $X[x_{i}]=Y[y_{i}]$. Observe that $x_{i+1}=x_{i}$ or $y_{i+1}=y_{i}$ and,
by symmetry, assume $x_{i+1}=x_{i}$ without loss of generality. Let us define
$j>i$ so that $x_{i}=\cdots=x_{j}<x_{j+1}$ and consider two cases depending on
whether $y_{j}=y_{j+1}$:

  * •

If $y_{j}=y_{j+1}$, we define an alignment $\mathcal{A}^{\prime}$ obtained
from $\mathcal{A}$ by deleting $(x_{j},y_{j})$. It is easy to see that
$\mathcal{A}^{\prime}$ is a valid alignment. Moreover,
$\mathcal{B}(\mathcal{A}^{\prime})\subseteq\mathcal{B}(\mathcal{A})$ and
$\mathcal{B}(\mathcal{A})\setminus\mathcal{B}(\mathcal{A}^{\prime})=\\{(x_{j},y_{j})\\}$,
so $\mathsf{cost}(\mathcal{A}^{\prime})<\mathsf{cost}(\mathcal{A})$,
contradicting the choice of $\mathcal{A}$ as an optimal alignment.

  * •

If $y_{j}<y_{j+1}$, we define an alignment
$\mathcal{A}^{\prime}=(x^{\prime}_{t},y^{\prime}_{t})_{t=1}^{m}$ obtained from
$\mathcal{A}$ by incrementing $x_{t}$ for
$t\in(i\mathinner{.\,.\allowbreak}j]$. Moreover,
$\mathcal{B}(\mathcal{A})\setminus\mathcal{B}(\mathcal{A}^{\prime})\subseteq\\{(x_{t},y_{t}):t\in[i\mathinner{.\,.\allowbreak}j)\\}$
and
$\mathcal{B}(\mathcal{A}^{\prime})\setminus\mathcal{B}(\mathcal{A})=\\{(x^{\prime}_{t},y^{\prime}_{t}):t\in(i\mathinner{.\,.\allowbreak}j]\\}$,
so $\mathsf{cost}(\mathcal{A}^{\prime})\leq\mathsf{cost}(\mathcal{A})$.
Furthermore,
$\sum_{t=1}^{m}(x^{\prime}_{t}+y^{\prime}_{t})=j-i+\sum_{t=1}^{m}(x_{t}+y_{t})$,
contradicting the choice of $\mathcal{A}$ as an optimal alignment maximizing
$\sum_{t=1}^{m}(x_{t}+y_{t})$.∎

For strings $X,Y\in\Sigma^{*}$ and an integer $k\geq\mathsf{ed}(X,Y)$, we
define a set

$\mathcal{M}_{k}(X,Y)=\bigcap_{\mathcal{A}\in\mathsf{GA}_{k}(X,Y)}\mathcal{M}_{X,Y}(\mathcal{A})$

of _common matches_ of all alignments $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$;
note that it forms a non-crossing matching of ${X,Y}$.

See 3.8

Additionally, for a string $Z\in(\Sigma\cup\\#)^{*}$, we define
$\mathsf{num}(Z)$ as a string obtained from $Z$ by replacing the $i$th
leftmost occurrence of $\\#$ in it with a unique dummy symbol
$\\#_{i}\notin\Sigma$.

######  Fact 5.1.

Let $X,Y\in\Sigma^{*}$. For each non-crossing matching $M$ of $X,Y$, we have
$\mathsf{ed}(X,Y)\leq\mathsf{ed}(\mathsf{num}(X^{M}),\mathsf{num}(Y^{M}))$.

###### Proof.

For every
$(x,y)\in[1\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|]$,
if $\mathsf{num}(X^{M})[x]=\mathsf{num}(Y^{M})[y]$, then $X[x]=Y[y]$. Thus,
$\mathsf{cost}_{X,Y}(\mathcal{A})\leq\mathsf{cost}_{\mathsf{num}(X^{M}),\mathsf{num}(Y^{M})}(\mathcal{A})$
holds for all alignments $\mathcal{A}$ of $X,Y$. ∎

See 3.9

###### Proof.

Denote $X^{\prime}=\mathsf{num}(X^{M})$ and $Y^{\prime}=\mathsf{num}(Y^{M})$,
and let $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$. We shall first prove that
$\mathcal{M}_{X,Y}(\mathcal{A})\subseteq\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})$.
Suppose that $(x,y)\in\mathcal{M}_{X,Y}(\mathcal{A})$, i.e.,
$X[x]\simeq_{\mathcal{A}}Y[y]$. Note that $\mathcal{M}_{X,Y}(\mathcal{A})$ is
a non-crossing matching of $X,Y$ and a superset of $M$, so either $(x,y)\in
M$, and then $X^{\prime}[x]=Y^{\prime}[y]$ is a dummy symbol, or $M$ contains
no pair involving $x$ or $y$, and then
$X^{\prime}[x]=X[x]=Y[y]=Y^{\prime}[y]$. In both cases, we have
$X^{\prime}[x]\simeq_{\mathcal{A}}Y^{\prime}[y]$, i.e.,
$(x,y)\in\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})$. This completes the
proof that
$\mathcal{M}_{X,Y}(\mathcal{A})\subseteq\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})$,
from which we derive
$\mathcal{B}_{X^{\prime},Y^{\prime}}(\mathcal{A})\subseteq\mathcal{B}_{X,Y}(\mathcal{A})$
and
$\mathsf{cost}_{X^{\prime},Y^{\prime}}(\mathcal{A})\leq\mathsf{cost}_{X,Y}(\mathcal{A})\leq
k$.

Next, we shall prove that
$\mathcal{A}\in\mathsf{GA}_{k}(X^{\prime},Y^{\prime})$. Suppose that
$X^{\prime}[x]=Y^{\prime}[y]$ holds for some $(x,y)\in\mathcal{A}$. Then, we
have $X[x]=Y[y]$ because either $(x,y)\in M$ or
$X[x]=X^{\prime}[x]=Y^{\prime}[y]=Y[y]$. Since $\mathcal{A}$ is a greedy
alignment of $X,Y$, this implies $(x,y)\in\mathcal{M}_{X,Y}(\mathcal{A})$,
i.e., $X[x]\simeq_{\mathcal{A}}Y[y]$. Due to the assumption
$X^{\prime}[x]=Y^{\prime}[y]$, we conclude that
$X^{\prime}[x]\simeq_{\mathcal{A}}Y^{\prime}[y]$, i.e.,
$(x,y)\in\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})$. This proves
$\mathcal{A}\in\mathsf{GA}_{k}(X^{\prime},Y^{\prime})$.

Now, let $\mathcal{A}\in\mathsf{GA}_{k}(X^{\prime},Y^{\prime})$. We shall
first prove that
$\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})\subseteq\mathcal{M}_{X,Y}(\mathcal{A})$.
Suppose that $(x,y)\in\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})$, i.e.,
$X^{\prime}[x]\simeq_{\mathcal{A}}Y^{\prime}[y]$. In particular,
$X^{\prime}[x]=Y^{\prime}[y]$, which implies $X[x]=Y[y]$ because either
$(x,y)\in M$ or $X[x]=X^{\prime}[x]=Y^{\prime}[y]=Y[y]$. Hence,
$X[x]\simeq_{\mathcal{A}}Y[y]$, i.e.,
$(x,y)\in\mathcal{M}_{X,Y}(\mathcal{A})$. This completes the proof that
$\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})\subseteq\mathcal{M}_{X,Y}(\mathcal{A})$,
from which we derive
$\mathcal{B}_{X,Y}(\mathcal{A})\subseteq\mathcal{B}_{X^{\prime},Y^{\prime}}(\mathcal{A})$
and
$\mathsf{cost}_{X,Y}(\mathcal{A})\leq\mathsf{cost}_{X^{\prime},Y^{\prime}}(\mathcal{A})\leq
k$.

Next, we shall prove that $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$. For a proof by
contradiction, suppose that $X[x]=Y[y]$ holds for some
$(x,y)\in\mathcal{B}_{X,Y}(\mathcal{A})$; if there are several such
breakpoints, let us choose the leftmost one. Note that
$X[1\mathinner{.\,.\allowbreak}x)\sim_{\mathcal{A}}Y[1\mathinner{.\,.\allowbreak}y)$
and
$X[x\mathinner{.\,.\allowbreak}|X|]\sim_{\mathcal{A}}Y[y\mathinner{.\,.\allowbreak}|Y|]$.
Let us construct an alignment $\mathcal{A}^{\prime}$ obtained from
$\mathcal{A}$ by replacing the induced alignment
$\mathcal{A}_{[x\mathinner{.\,.\allowbreak}|X|],[y\mathinner{.\,.\allowbreak}|Y|]}$
with an optimum greedy alignment of
$X[x\mathinner{.\,.\allowbreak}|X|],Y[y\mathinner{.\,.\allowbreak}|Y|]$ (see
Fact 3.7). By the choice of $(x,y)$, the induced alignment
$\mathcal{A}^{\prime}_{[1\mathinner{.\,.\allowbreak}x),[1\mathinner{.\,.\allowbreak}y)}=\mathcal{A}_{[1\mathinner{.\,.\allowbreak}x),[1\mathinner{.\,.\allowbreak}y)}$
is a greedy alignment of
$X[1\mathinner{.\,.\allowbreak}x),Y[1\mathinner{.\,.\allowbreak}y)$ and thus
$\mathcal{A}^{\prime}$ is a greedy alignment of $X,Y$. Due to
$\mathsf{cost}_{X,Y}(\mathcal{A}^{\prime})\leq\mathsf{cost}_{X,Y}(\mathcal{A})\leq
k$, this implies $\mathcal{A}^{\prime}\in\mathsf{GA}_{k}(X,Y)$. Hence,
$\mathcal{M}_{X,Y}(\mathcal{A}^{\prime})$ is a non-crossing matching of $X,Y$
and a superset of $M$. The construction of $\mathcal{A}^{\prime}$ further
guarantees $(x,y)\in\mathcal{M}_{X,Y}(\mathcal{A}^{\prime})$, so either
$(x,y)\in M$, and then $X^{\prime}[x]=Y^{\prime}[y]$ is a dummy symbol, or $M$
contains no pair involving $x$ or $y$, and then
$X^{\prime}[x]=X[x]=Y[y]=Y^{\prime}[y]$. In both cases, we have
$X^{\prime}[x]=Y^{\prime}[y]$ and, since $\mathcal{A}$ is a greedy alignment
of $X^{\prime},Y^{\prime}$, we derive
$X^{\prime}[x]\simeq_{\mathcal{A}}Y^{\prime}[y]$ and
$(x,y)\in\mathcal{M}_{X,Y}(\mathcal{A})$. This contradicts the choice of
$(x,y)$, completing the proof that $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$.

Overall, we conclude that
$\mathsf{GA}_{k}(X,Y)=\mathsf{GA}_{k}(X^{\prime},Y^{\prime})$ and that every
alignment $\mathcal{A}$ in this family satisfies both
$\mathcal{M}_{X,Y}(\mathcal{A})=\mathcal{M}_{X^{\prime},Y^{\prime}}(\mathcal{A})$
and
$\mathsf{cost}_{X,Y}(\mathcal{A})=\mathsf{cost}_{X^{\prime},Y^{\prime}}(\mathcal{A})$.
Consequently, $\mathcal{M}_{k}(X,Y)=\mathcal{M}_{k}(X^{\prime},Y^{\prime})$
and, due to Fact 3.7, $\mathsf{ed}(X,Y)=\mathsf{ed}(X^{\prime},Y^{\prime})$. ∎

######  Proposition 5.2.

Consider a string $S\in(\Sigma\cup\\{\\#\\})^{n}$ with $s$ dummy segments.
Given the sorted list of dummy segments in $S$, one can in $\mathcal{O}(s)$
time construct a data structure $\mathsf{RS}_{\\#}(S)$ supporting the
following queries in $\mathcal{O}(\log s)$ time:

  1. 1.

$\mathbf{\mathsf{rank}}_{\\#}(S,i)$: Given
$i\in[1\mathinner{.\,.\allowbreak}n+1]$, return
$|\\{i^{\prime}\in[1\mathinner{.\,.\allowbreak}i):S[i^{\prime}]=\\#\\}|$.

  2. 2.

$\mathbf{\mathsf{select}}_{\\#}(S,j)$: Given
$j\in[1\mathinner{.\,.\allowbreak}\mathsf{rank}_{\\#}(S,n)]$, return the $j$th
smallest element of $\\{i\in[1\mathinner{.\,.\allowbreak}n]:S[i]=\\#\\}$.

###### Proof.

For each dummy segment $S[\ell\mathinner{.\,.\allowbreak}r)$, the data
structure stores a tuple $(\ell,r,\mathsf{rank}_{\\#}(S,\ell))$. These tuples
are stored in a sorted array (note that the order is the same for all
coordinates). To compute $\mathsf{rank}_{\\#}(S,i)$, we binary search for the
rightmost segment $S[\ell^{*}\mathinner{.\,.\allowbreak}r^{*})$ such that
$\ell^{*}\leq i$. If there is no such segment, we return
$\mathsf{rank}_{\\#}(S,i)=0$. Otherwise,
$\mathsf{rank}_{\\#}(S,i)=\mathsf{rank}_{\\#}(S,\ell^{*})+\min(i,r^{*})-\ell^{*}$.

To compute $\mathsf{select}_{\\#}(S,j)$, we binary search for the rightmost
segment $S[\ell^{*}\mathinner{.\,.\allowbreak}r^{*})$ such that
$\mathsf{rank}_{\\#}(S,\ell^{*})<j$. Then,
$\mathsf{select}_{\\#}(S,j)=\ell^{*}+j-1-\mathsf{rank}_{\\#}(S,\ell^{*})$. ∎

######  Definition 5.3.

For a non-crossing matching $M$ of strings $X,Y\in\Sigma^{*}$ we set (cf.
Proposition 4.2):

$\mathsf{E}^{M}(X,Y):=\left(\mathsf{D}(X^{M}Y^{M}),\mathsf{RS}_{\\#}(X^{M}),\mathsf{RS}_{\\#}(Y^{M})\right).$

######  Lemma 5.4.

Let $X^{\prime}=\mathsf{num}(X^{M})$ and $Y^{\prime}=\mathsf{num}(Y^{M})$ for
a non-crossing matching $M$ of strings $X,Y\in\Sigma^{\leq n}$. The encoding
$\mathsf{E}^{M}(X,Y)$ allows answering $\mathsf{LCE}$ queries on the suffixes
of $X^{\prime},Y^{\prime}$ and on the suffixes of
$\overline{X^{\prime}},\overline{Y^{\prime}}$ in $\mathcal{O}(\log n)$ time.

###### Proof.

Consider a query asking for
$\mathsf{LCE}(X^{\prime}[x\mathinner{.\,.\allowbreak}],Y^{\prime}[y\mathinner{.\,.\allowbreak}])$.
Observe that
$\mathsf{LCE}(X^{\prime}[x\mathinner{.\,.\allowbreak}],Y^{\prime}[y\mathinner{.\,.\allowbreak}])=\mathsf{LCE}(X^{M}[x\mathinner{.\,.\allowbreak}],Y^{M}[y\mathinner{.\,.\allowbreak}])$
if $\mathsf{rank}_{\\#}(X^{M},x)=\mathsf{rank}_{\\#}(Y^{M},y)$. Otherwise,
$\mathsf{LCE}(X^{\prime}[x\mathinner{.\,.\allowbreak}],Y^{\prime}[y\mathinner{.\,.\allowbreak}])=\min(\mathsf{LCE}(X^{M}[x\mathinner{.\,.\allowbreak}],Y^{M}[y\mathinner{.\,.\allowbreak}]),\mathsf{select}_{\\#}(X^{M},\mathsf{rank}_{\\#}(X^{M},x)+1)-x,\mathsf{select}_{\\#}(Y^{M},\mathsf{rank}_{\\#}(Y^{M},y)+1)-y)$.
In either case, the query can be answered in $\mathcal{O}(\log n)$ time using
Propositions 5.2 and 4.2(c). The values
$\mathsf{LCE}(\overline{X^{\prime}}[x\mathinner{.\,.\allowbreak}],\overline{Y^{\prime}}[y\mathinner{.\,.\allowbreak}])$
are answered in a similar way. ∎

######  Corollary 5.5.

Given an integer $k>0$ and the encoding $\mathsf{E}^{M}(X,Y)$ for a non-
crossing matching $M$ of strings $X,Y\in\Sigma^{\leq n}$, one can in
$\mathcal{O}(k^{2}\log n)$ time compute a integer
$d\in[0\mathinner{.\,.\allowbreak}k+1]$ such that

$d=\begin{cases}\mathsf{ed}(X,Y)&\text{if }\mathsf{ed}(X,Y)\leq k\text{ and
}M\subseteq\mathcal{M}_{k}(X,Y),\\\ k+1&\text{if
}\mathsf{ed}(X,Y)>k.\end{cases}$

###### Proof.

We compute $d:=\min(k+1,\mathsf{ed}(\mathsf{num}(X^{M}),\mathsf{num}(Y^{M})))$
using the Landau–Vishkin algorithm [42], with $\mathcal{O}(k^{2})$
$\mathsf{LCE}$ queries on suffixes of
$\mathsf{num}(X^{M}),\mathsf{num}(Y^{M})$ implemented using Lemma 5.4. Due to
Fact 5.1, we have $d\geq\min(k+1,\mathsf{ed}(X,Y))$ and, in particular,
$d=k+1$ if $\mathsf{ed}(X,Y)>k$. If $\mathsf{ed}(X,Y)\leq k$ and
$M\subseteq\mathcal{M}_{k}(X,Y)$, then Lemma 3.9 yields
$d=\min(k+1,\mathsf{ed}(X,Y))=\mathsf{ed}(X,Y)$. ∎

###  5.1 Greedy Encoding and Its Size

######  Definition 5.6.

For strings $X,Y\in\Sigma^{*}$ and an integer $k$, we define the _greedy
encoding_

$\mathsf{GR}_{k}(X,Y)=\begin{cases}\mathsf{E}^{\mathcal{M}_{k}(X,Y)}(X,Y)&\text{if
}k\geq\mathsf{ed}(X,Y),\\\ \bot&\text{otherwise.}\end{cases}$

See 3.10

###### Proof.

We show the claim of the lemma for $X^{M}$, the claim for $Y^{M}$ follows by
symmetry.

As $\mathsf{ed}(X,Y)\leq k$, by Fact 3.7 $\mathsf{GA}_{k}(X,Y)\neq\emptyset$,
and therefore there is an alignment $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$ of
cost at most $k$ between $X$ and $Y$. We consider yet another graphical
representation of an alignment. Namely, we represent $\mathcal{A}$ as a set of
at most $k$ horizontal segments, where a horizontal segment
$I=[i\mathinner{.\,.\allowbreak}j;\Delta]$ from $(i,\Delta)$ to $(j,\Delta)$
means that
$X[i\mathinner{.\,.\allowbreak}j]\simeq_{\mathcal{A}}Y[i+\Delta\mathinner{.\,.\allowbreak}j+\Delta]$
(see Fig. 1). This representation induces a partitioning of $X=f_{1}\cdots
f_{z}$, where $z=\mathcal{O}(k)$, and each factor $f_{\ell}$ is either a
single character deleted under $\mathcal{A}$ or a fragment
$X[i\mathinner{.\,.\allowbreak}j]$ corresponding to a horizontal segment
$I=[i\mathinner{.\,.\allowbreak}j;\Delta]$.

$X$:a1b2b3a4b5c6b7c8b9c10$Y$:a1b2a3b4a5b6c7b8c9b10c11Alignment
$\mathcal{A}$.$X$:a1b2b3a4b5c6b7c8b9c10$Y$:a1b2a3b4a5b6c7b8c9b10c11Alignment
$\mathcal{A}^{\prime\prime}$.$|X|$shift$-1$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$I=[4\mathinner{.\,.\allowbreak}11;-1]$
Figure 1: Graphical representations of two greedy alignments
$\mathcal{A},\mathcal{A}^{\prime\prime}\in\mathsf{GA}_{5}(X,Y)$, where
$X=\mathtt{abababcbcbc}$ and $Y=\mathtt{abbabcbcbc}$. The alignment
$\mathcal{A}$ (red) has cost $1$ (we delete $X[3]$), and the alignment
$\mathcal{A}^{\prime\prime}$ cost $5$ (we delete $X[5]$, $X[10]$, $X[11]$,
$Y[3]$, $Y[6]$). The alignments imply that
$X[6\mathinner{.\,.\allowbreak}9]=Y[7\mathinner{.\,.\allowbreak}10]=X[8\mathinner{.\,.\allowbreak}11]$.

If $|\mathsf{GA}_{k}(X,Y)|=1$, then every factor $f_{\ell}$ with
$|f_{\ell}|\geq 2$ is replaced with an equal length string of dummy symbols.
The upper bound on $|\mathsf{LZ}(X^{M})|$ follows by sub-additivity of the
Lempel–Ziv encoding, and the upper bound on the number of dummy segments is
trivial.

Suppose now that $|\mathsf{GA}_{k}(X,Y)|>1$. We show that in this case the
Lempel–Ziv encoding of any factor $f_{\ell}$ has size $\mathcal{O}(k)$. Fix
$\ell$. If $f_{\ell}$ is a single character, the claim obviously holds.
Suppose now that the factor $f_{\ell}$ of the partitioning defined above
corresponds to a horizontal segment
$I=[i\mathinner{.\,.\allowbreak}j;\Delta]$. Let us show that there is $i\leq
q\leq j$ such that
$X^{M}[i\mathinner{.\,.\allowbreak}q]=X[i\mathinner{.\,.\allowbreak}q]$ and
$X^{M}[q+1\mathinner{.\,.\allowbreak}j]=\\#\\#\ldots\\#$. This follows
immediately from the following observation. Let
$\mathcal{A}^{\prime}\neq\mathcal{A}$ be another alignment
$\in\mathsf{GA}_{k}(X,Y)$. The alignment $\mathcal{A}^{\prime}$ is greedy, and
therefore, if for some $i\leq p\leq j$ the alignment $\mathcal{A}^{\prime}$
matches $X[p]$ and $Y[p+\Delta]$, then it also matches $X[p+1]$ and
$Y[p+1+\Delta]$, …, $X[j]$ and $Y[j+\Delta]$. We obtain an upper bound on the
number of dummy segments as an immediate corollary, but an upper bound on
$\mathsf{LZ}(X^{M})$ requires more work.

Consider an alignment $\mathcal{A}^{\prime\prime}\in\mathsf{GA}_{k}(X,Y)$
realising $q$. We have
$X^{M}[q+1\mathinner{.\,.\allowbreak}j]=\\#\\#\mathinner{.\,.\allowbreak}\\#$,
and therefore
$|\mathsf{LZ}(X^{M}[q+1\mathinner{.\,.\allowbreak}j])|=\mathcal{O}(1)$.
Consider now
$X^{M}[i\mathinner{.\,.\allowbreak}q]=X[i\mathinner{.\,.\allowbreak}q]$.
Consider the set of the horizontal segments corresponding to
$\mathcal{A}^{\prime\prime}$ that contain positions in
$[i\mathinner{.\,.\allowbreak}q]$. We claim that either all segments in the
set have height less than $\Delta$, or all segments have height larger than
$\Delta$. Suppose that there are two consecutive horizontal segments
$[i_{1}\mathinner{.\,.\allowbreak}j_{1};\Delta_{1}]$ and
$[i_{2}\mathinner{.\,.\allowbreak}j_{2};\Delta_{2}]$ such that one of them is
above $I$ and the other is below. $\mathcal{A}^{\prime\prime}$ must delete the
characters $X[j_{1}+1],X[j_{1}+2],\ldots,X[i_{2}-1]$ and
$Y[j_{1}+\Delta_{1}],Y[j_{1}+\Delta_{1}+1],\ldots,Y[i_{2}+\Delta_{2}-1]$ in
some order. As it deletes the characters one by one, at some moment it arrives
to a pair $X[x],Y[x+\Delta]$, where $i<x<q$. However, since
$\mathcal{A}^{\prime\prime}$ is greedy, from this pair it must follow the
segment $I$, a contradiction.

We now use this property to show that
$|\mathsf{LZ}(X[i\mathinner{.\,.\allowbreak}q])|=\mathcal{O}(k)$. First,
consider the case when the segments corresponding to
$\mathcal{A}^{\prime\prime}$ are below $I$. Let
$I^{\prime}=[i^{\prime}\mathinner{.\,.\allowbreak}j^{\prime};\Delta^{\prime}]$
be one such segment, where $i\leq i^{\prime}\leq j^{\prime}\leq q$, and
$-k\leq\Delta^{\prime}<\Delta$. Let
$i^{\prime\prime}=\max\\{i+2k,i^{\prime}\\}$. If $i^{\prime\prime}\leq
j^{\prime}$, we have
$X[i^{\prime\prime}\mathinner{.\,.\allowbreak}j^{\prime}]=Y[i^{\prime\prime}+\Delta^{\prime}\mathinner{.\,.\allowbreak}j^{\prime}+\Delta^{\prime}]$,
and the alignment $\mathcal{A}$ implies that
$Y[i^{\prime\prime}+\Delta^{\prime}\mathinner{.\,.\allowbreak}j^{\prime}+\Delta^{\prime}]=X[i^{\prime\prime}+(\Delta^{\prime}-\Delta)\mathinner{.\,.\allowbreak}j^{\prime}+(\Delta^{\prime}-\Delta)]$.
Consequently,
$X[i^{\prime\prime}\mathinner{.\,.\allowbreak}j^{\prime}]=X[i^{\prime\prime}+(\Delta^{\prime}-\Delta)\mathinner{.\,.\allowbreak}j^{\prime}+(\Delta^{\prime}-\Delta)]$
is a previous factor as $\Delta^{\prime}-\Delta<0$. It follows that
$\mathcal{A}^{\prime\prime}$ defines a partitioning of
$X[i\mathinner{.\,.\allowbreak}q]=t_{1}\cdots t_{z}$, where $z=\mathcal{O}(k)$
and each factor $t_{i}$ is either a single character, or a previous factor. By
Fact 4.1, we obtain that
$|\mathsf{LZ}(X[i\mathinner{.\,.\allowbreak}q])|=\mathcal{O}(k)$.

The proof for the complementary case is similar. There are at most $k$
horizontal segments corresponding to $\mathcal{A}^{\prime}$ that contain
positions in $[i\mathinner{.\,.\allowbreak}q]$, denote them by
$[i^{\prime}_{\ell}\mathinner{.\,.\allowbreak}j^{\prime}_{\ell};\Delta^{\prime}_{\ell}]$.
For all $\ell$, we have $k\geq\Delta^{\prime}_{\ell}>\Delta$. Let
$j^{\prime\prime}_{\ell}=\min\\{j^{\prime}_{\ell},q-2k\\}$. If
$i^{\prime}_{\ell}\leq j^{\prime\prime}_{\ell}$, we have
$X[i^{\prime}_{\ell}\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}]=Y[i^{\prime}_{\ell}+\Delta^{\prime}_{\ell}\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}+\Delta^{\prime}_{\ell}]$
(from the alignment $\mathcal{A}^{\prime\prime}$), and
$Y[i^{\prime\prime}_{\ell}+\Delta^{\prime}_{\ell}\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}+\Delta^{\prime}_{\ell}]=X[i^{\prime}_{\ell}+(\Delta^{\prime}_{\ell}-\Delta)\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}+(\Delta^{\prime}_{\ell}-\Delta)]$.
Consequently,
$X[i^{\prime}_{\ell}+(\Delta^{\prime}_{\ell}-\Delta)\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}+(\Delta^{\prime}_{\ell}-\Delta)]=X[i^{\prime}_{\ell}\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}]$
is a previous factor as $\Delta^{\prime}_{\ell}-\Delta>0$. As the cost of
$\mathcal{A}^{\prime\prime}$ is bounded from above by $k$, we have
$\bigl{|}[i\mathinner{.\,.\allowbreak}q]-\cup_{\ell}[i^{\prime}_{\ell}\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}]\bigr{|}\leq
k$ and $\sum_{\ell}|\Delta^{\prime}_{\ell}-\Delta^{\prime}_{\ell+1}|\leq k$.
Therefore,
$\bigl{|}[i\mathinner{.\,.\allowbreak}q]-\cup_{\ell}[i^{\prime}_{\ell}+(\Delta^{\prime}_{\ell}-\Delta)\mathinner{.\,.\allowbreak}j^{\prime\prime}_{\ell}+(\Delta^{\prime}_{\ell}-\Delta))\bigr{|}=\mathcal{O}(k)$,
and we can conclude as above.

The claim follows. ∎

######  Corollary 5.7.

For every $X,Y\in\Sigma^{\leq n}$ and $k\in\mathbb{Z}_{+}$, the encoding
$\mathsf{GR}_{k}(X,Y)$ takes $\mathcal{O}(k^{2}\log^{2}n)$ space.

###### Proof.

Follows immediately from Propositions 4.2, 5.2 and 3.10. ∎

###  5.2 Construction of greedy encodings

In this section, we give a deterministic approach to construction of
$\mathsf{GR}_{k}(X,Y)$. We start with a combinatorial lemma that is a key to
this approach.

See 3.11

###### Proof 666The authors would like to thank Panagiotis Charalampopoulos
for an early write-up of the proof of this lemma, which was originally meant
to be included into [12]..

We prove $\mathcal{B}_{k}(X,Y)\leq 136k^{5}$ by induction on $|X|$. In the
base case of $|X|\leq 42k^{4}$, we have
$|\mathcal{B}_{k}(X,Y)|\leq(2k+1)|X|\leq 136k^{5}$ since each
$(x,y)\in\mathcal{B}_{k}(X,Y)$ satisfies $|x-y|\leq k$. Thus, we assume that
$|X|>42k^{4}$, $\mathsf{GA}_{k}(X,Y)\neq\emptyset$ (otherwise,
$\mathcal{B}_{k}(X,Y)=\emptyset$), and the claim holds for shorter strings.

_Case 1_. If $\mathcal{M}_{k}(X,Y)$ contains two adjacent pairs
$(x-1,y-1),(x,y)$, then we construct strings $X^{\ast}$ and $Y^{\ast}$ by
deleting $X[x]$ and $Y[y]$, respectively, aiming to prove that
$|\mathcal{B}_{k}(X,Y)|\leq|\mathcal{B}_{k}(X^{\ast},Y^{\ast})|\leq 136k^{5}$.
For this, consider an alignment $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$. Due to
$(x-1,y-1),(x,y)\in\mathcal{M}(\mathcal{A})$, the pairs $(x-1,y-1)$, $(x,y)$,
and $(x+1,y+1)$ are three consecutive elements of $\mathcal{A}$. Let
$X^{\ast}$ be the string obtained by removing $X[x]$ from $X$, and $Y^{\ast}$
be the string obtained by removing $Y[y]$ from $Y$. We define an alignment
$\mathcal{A}^{\ast}$ of $X^{\ast},Y^{\ast}$ by removing $(x,y)$ and shifting
all pairs to the right of $(x,y)$ by one position to the left. Each breakpoint
$(x^{\prime},y^{\prime})\in\mathcal{B}(\mathcal{A})$ is preserved (along with
$X[x^{\prime}]\neq Y[y^{\prime}]$), if it is located to the left of $(x,y)$,
or shifted by 1 position to the left (along with $X[x^{\prime}]\neq
Y[y^{\prime}]$), if it is located to the right of $(x,y)$. Consequently,
$\mathcal{A}^{\ast}\in\mathsf{GA}_{k}(X^{\ast},Y^{\ast})$ and, since the
shifts are independent of $\mathcal{A}$, we derive
$|\mathcal{B}_{k}(X^{\ast},Y^{\ast})|\geq|\mathcal{B}_{k}(X,Y)|$.

_Case 2:_ If $\mathcal{M}_{k}(X,Y)$ does not contain any two adjacent pairs,
we first prove the following claim:

######  Claim 5.8.

There are alignments $\mathcal{A},\mathcal{A}^{\prime}\in\mathsf{GA}_{k}(X,Y)$
such that
$X[a\mathinner{.\,.\allowbreak}a+9k^{2})\simeq_{\mathcal{A}}Y[i\mathinner{.\,.\allowbreak}i+9k^{2})\simeq_{\mathcal{A}^{\prime}}X[b\mathinner{.\,.\allowbreak}b+9k^{2})$
holds for some positions $a\neq b$.

###### Proof.

Consider $k+1$ disjoint fragments of $X$, each of length
$21k^{3}\leq|X|/(k+1)$. Each $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$ aligns at
least one fragment without mismatches:
$X[s\mathinner{.\,.\allowbreak}t]\simeq_{\mathcal{A}}Y[s^{\prime}\mathinner{.\,.\allowbreak}t^{\prime}]$
for some positions $s,t,s^{\prime},t^{\prime}$. Due to $X[t]=Y[t^{\prime}]$,
if $(t-1,t^{\prime}-1)\in\mathcal{M}_{k}(X,Y)$, then
$(t,t^{\prime})\in\mathcal{M}_{k}(X,Y)$ holds by the greedy nature of the
considered alignments. Consequently, there is
$\mathcal{A}^{\prime}\in\mathsf{GA}_{k}(X,Y)$ such that
$X[t-1]\not\simeq_{\mathcal{A}^{\prime}}Y[t^{\prime}-1]$.

Next, consider $k+1$ disjoint parts of $Y[s+k\mathinner{.\,.\allowbreak}t-k)$,
each of length $9k^{2}\leq(21k^{3}-1-2k)/(k+1)$. By Fact 2.3, $\mathcal{A}$
aligns the entire $Y[s+k\mathinner{.\,.\allowbreak}t-k)$ without mismatches to
a fragment of $X[s\mathinner{.\,.\allowbreak}t)$. Moreover,
$\mathcal{A}^{\prime}$ aligns at least one part without mismatches. Denote
this part $Y[i\mathinner{.\,.\allowbreak}i+9k^{2})$, and fix positions $a,b$
so that
$X[a\mathinner{.\,.\allowbreak}a+9k^{2})\simeq_{\mathcal{A}}Y[i\mathinner{.\,.\allowbreak}i+9k^{2})\simeq_{\mathcal{A}^{\prime}}X[b\mathinner{.\,.\allowbreak}b+9k^{2})$.
Note that $a\in[s\mathinner{.\,.\allowbreak}t)$ and thus
$X[a\mathinner{.\,.\allowbreak}t)\simeq_{\mathcal{A}}Y[i\mathinner{.\,.\allowbreak}t^{\prime})$.
Now, if $a=b$, then we would have $X[a]\simeq_{\mathcal{A}^{\prime}}Y[i]$ and
the greedy nature of $\mathcal{A}^{\prime}$ would guarantee
$X[a\mathinner{.\,.\allowbreak}t)\simeq_{\mathcal{A}^{\prime}}Y[i\mathinner{.\,.\allowbreak}t^{\prime})$,
contradicting $X[t-1]\not\simeq_{\mathcal{A}^{\prime}}Y[t^{\prime}-1]$.
Consequently, $a\neq b$. ∎

By Fact 2.3, we have
$p:=\mathsf{per}(Y[i\mathinner{.\,.\allowbreak}i+9k^{2}))\leq|a-b|\leq|i-a|+|i-b|\leq
2k$. Moreover, due to $7k^{2}\geq 2p$, the fragment
$X[i+k^{2}\mathinner{.\,.\allowbreak}i+8k^{2})$ has the same period (up to
cyclic rotation).

######  Claim 5.9.

For every $\mathcal{A}^{\prime\prime}\in\mathsf{GA}_{k}(X,Y)$, we have
$X[i+3k^{2}\mathinner{.\,.\allowbreak}i+8k^{2})\simeq_{\mathcal{A}^{\prime\prime}}Y[v\mathinner{.\,.\allowbreak}v+5k^{2})$
for some $v\in[i+2k^{2}\mathinner{.\,.\allowbreak}i+4k^{2}]$.

###### Proof.

Consider $k+1$ disjoint parts of
$X[i+k^{2}\mathinner{.\,.\allowbreak}i+3k^{2}+p)$, each of length $p$ (note
that $(k+1)p\leq 2k^{2}+p$). Each
$\mathcal{A}^{\prime\prime}\in\mathsf{GA}_{k}(X,Y)$ matches at least one part
without mismatches:
$X[j\mathinner{.\,.\allowbreak}j+p)\simeq_{\mathcal{A}^{\prime\prime}}Y[u\mathinner{.\,.\allowbreak}u+p)$
for some $j\in[i+k^{2}\mathinner{.\,.\allowbreak}i+3k^{2}]$ and
$u\in[j-k\mathinner{.\,.\allowbreak}j+k]$. Note that
$X[j\mathinner{.\,.\allowbreak}i+8k^{2})$ and
$Y[u\mathinner{.\,.\allowbreak}i+9k^{2})$ have, up to cyclic rotation, the
same string period of length $p$. This string period is primitive, so
${X[j\mathinner{.\,.\allowbreak}j+p)}=Y[u\mathinner{.\,.\allowbreak}u+p)$
implies that the periods synchronize, i.e.,
$X[j\mathinner{.\,.\allowbreak}i+8k^{2})=Y[u\mathinner{.\,.\allowbreak}u+(i+8k^{2}-j)]$.
By the greedy nature of $\mathcal{A}^{\prime\prime}$, we must have
$X[j\mathinner{.\,.\allowbreak}i+8k^{2})\simeq_{\mathcal{A}^{\prime\prime}}Y[u\mathinner{.\,.\allowbreak}u+(i+8k^{2}-j)]$,
and therefore
$X[i+3k^{2}\mathinner{.\,.\allowbreak}i+8k^{2})\simeq_{\mathcal{A}^{\prime\prime}}Y[v\mathinner{.\,.\allowbreak}v+5k^{2}]$
for $v=u+i+3k^{2}-j\in[i+3k^{2}-k\mathinner{.\,.\allowbreak}i+3k^{2}+k]$. ∎

Consider fragments $Q:=X[i+3k^{2}\mathinner{.\,.\allowbreak}i+8k^{2})$ and
$F:=Y[i+4k^{2}\mathinner{.\,.\allowbreak}i+7k^{2})$, where $F$ is contained in
all fragments $Y[v\mathinner{.\,.\allowbreak}v+5k^{2})$ with
$v\in[i+2k^{2}\mathinner{.\,.\allowbreak}i+4k^{2}]$. We observe that
$|Q|\geq|F|=3k^{2}>p$ and construct $X^{\ast}$ and $Y^{\ast}$ by removing
$X[i+8k^{2}-p\mathinner{.\,.\allowbreak}i+8k^{2})$ and
$Y[i+7k^{2}-p\mathinner{.\,.\allowbreak}i+7k^{2})$. For every
$\mathcal{A}^{\prime\prime}\in\mathsf{GA}_{k}(X,Y)$, we derive
$\mathcal{A}^{\ast}$ by removing the pairs $(x,y)$ with
$y\in[i+7k^{2}-p\mathinner{.\,.\allowbreak}i+7k^{2})$, and shifting all the
subsequent pairs by $p$ positions to the left. We conclude from 5.9 that the
breakpoints $(x^{\prime},y^{\prime})\in\mathcal{B}(\mathcal{A})$ are preserved
(along with $X[x^{\prime}]\neq Y[y^{\prime}]$), if located to the left of
$(i+3k^{2},i+4k^{2})$, or shifted by $p$ positions to the left (along with
$X[x^{\prime}]\neq Y[y^{\prime}]$), if located to the right of
$(i+8k^{2},i+7k^{2})$. Consequently,
$\mathcal{A}^{\ast}\in\mathsf{GA}_{k}(X^{\ast},Y^{\ast})$ and, since the
shifts are independent of $\mathcal{A}^{\prime\prime}$, we derive
$|\mathcal{B}_{k}(X,Y)|\leq|\mathcal{B}_{k}(X^{\ast},Y^{\ast})|\leq 136k^{5}$
from the inductive assumption. ∎

Algorithm 1 is the key procedure for computing greedy encodings.

1

2

3Greedy(k)

4 $Q=\emptyset$;

5 GreedyMatch(_$Q$ , $1$, $1$, $k$_);

6 while  _$Q$ is not empty_ do

7 $(x,y),\textsf{credit}=Q.\textsf{extract-min}()$;

8 if  _$x\leq|X|$_ then

GreedyMatch(_$Q$ , $x+1$, $y$, $\textsf{credit}-1$_);

// delete $X[x]$

9

10 if  _$y\leq|Y|$_ then

GreedyMatch(_$Q$ , $x$, $y+1$, $\textsf{credit}-1$_);

// delete $Y[y]$

11

12 if  _$x\leq|X|$ and and $y\leq|Y|$_ then

GreedyMatch(_$Q$ , $x+1$, $y+1$, $\textsf{credit}-1$_);

// substitute $X[x]$ for $Y[y]$

13

14

15

16 GreedyMatch(_$Q$ , $x$, $y$, credit_):

17 if
_$\mathsf{ed}(X[x\mathinner{.\,.\allowbreak}],Y[y\mathinner{.\,.\allowbreak}])\leq\textsf{credit}$_
then

$\ell=\mathsf{LCE}(X[x\mathinner{.\,.\allowbreak}],Y[y\mathinner{.\,.\allowbreak}])$;

// match $X[x]$ and $Y[y]$,…, $X[x+\ell-1]$ and $Y[y+\ell-1]$

18 $x=x+\ell$; $y=y+\ell$;

19 Push(_$Q$ , $(x,y)$, credit_);

20 if  _$|Q|=1$_ then output $[x-\ell,x-1]$;

21

22

23

24 Push(_$Q$ , $(x,y)$, credit_)

25 if  _$(x,y)\notin Q$_ then $Q[(x,y)]=\textsf{credit}$;

26 else $Q[(x,y)]=\max\\{Q[(x,y)],\textsf{credit}\\}$;

27 // points are ordered lexicographically.

28

29

30

Algorithm 1 The algorithm receives as an input strings $X,Y$, and integer $k$.
Lexicographic order on points is defined in the following way:
$(x_{1},y_{1})<(x_{2},y_{2})$ if either $x_{1}<x_{2}$ or $x_{1}=x_{2}$ and
$y_{1}<y_{2}$.

######  Lemma 5.10.

Given two strings $X,Y\in\Sigma^{\ast}$ and integer $k\geq\mathsf{ed}(X,Y)$,
Algorithm 1 computes the dummy segments in $X^{\mathcal{M}_{k}(X,Y)}$.
Moreover, it can be implemented in $\mathcal{O}(|\mathcal{B}_{k}(X,Y)|(t+\log
k))$ time and $\tilde{\mathcal{O}}(k)$ space, provided with an oracle that,
given $x\in[1\mathinner{.\,.\allowbreak}|X|+1]$ and
$y\in[1\mathinner{.\,.\allowbreak}|Y|+1]$, in $\mathcal{O}(t)$ time computes
$\mathsf{LCE}(X[x\mathinner{.\,.\allowbreak}],Y[y\mathinner{.\,.\allowbreak}])$
and
$\min(k+1,\mathsf{ed}(X[x\mathinner{.\,.\allowbreak}],Y[y\mathinner{.\,.\allowbreak}]))$.

###### Proof.

To show correctness of Algorithm 1, consider an (imaginary set) of alignments
$\mathcal{G}$ generated by the algorithm. First, associate with each point in
$[1\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|]$ an
empty set of alignments. Let $(x,y)$ be the latest point extracted from $Q$
and $\mathcal{G}[(x,y)]$ the set of alignments associated with it. In line 1
(if the algorithm executes it), we create a new set of alignments containing
all alignments in $\mathcal{G}[(x,y)]$ extended by $(x+1,y)$ (deletion of
$X[x]$), $(x+1,y),(x+2,y+1),\ldots(x+\ell,y+\ell-1)$, where
$\ell=\mathsf{LCE}(X[x+1\mathinner{.\,.\allowbreak}],Y[y\mathinner{.\,.\allowbreak}])$
(matching of $X[x+1\mathinner{.\,.\allowbreak}x+\ell]$ and
$Y[y\mathinner{.\,.\allowbreak}y+\ell-1]$). We union the resulting set of
alignments with $\mathcal{G}[x+\ell,y+\ell-1]$ and push $(x+\ell,y+\ell-1)$ to
$Q$. In lines 1 and 1 we process $\mathcal{G}[(x,y)]$ analogously. Finally, we
define $\mathcal{G}=G[|X|,|Y|]$. We claim that
$\mathcal{G}=\mathsf{GA}_{k}(X,Y)$. First note that all alignments in
$\mathcal{G}$ are greedy by construction: an alignment can only delete $X[x]$,
$Y[y]$, or substitute $X[x]$ for $Y[y]$ if $X[x]\neq Y[y]$. In other words,
for every breakpoint $(x,y)$ we have $X[x]\neq Y[y]$. Additionally, the cost
of every alignment in $\mathcal{G}$ is at most $k$ as at each call of
GreedyMatch credit decreases by one. Hence,
$\mathcal{G}=\mathsf{GA}_{k}(X,Y)$.

We define successors and predecessors in the lexicographic order in a standard
way. For an alignment $\mathcal{A}\in\mathcal{G}$ and a point
$(x,y)\in\mathcal{B}(\mathcal{A})$, define
$\textsf{credit}_{\mathcal{A}}(x,y)$ as the difference between $k$ and the
number of edits that $\mathcal{A}$ makes to reach $(x,y)$. Algorithm 1
satisfies the following properties:

  1. 1.

The set $\mathcal{P}$ of the points that are ever added to $Q$ is equal to
$\mathcal{B}(\mathcal{G})$, and when we process a point $(x,y)$, the credit
associated with it equals
$\max_{\mathcal{A}\in\mathcal{G}:(x,y)\in\mathcal{B}(\mathcal{A})}\textsf{credit}_{\mathcal{A}}(x,y)$;

  2. 2.

When we process a point $(x,y)$,
$Q=\cup_{\mathcal{A}\in\mathcal{G}}\\{(x^{\prime},y^{\prime})\text{ is the
successor of }(x,y)\text{ in }\mathcal{B}(\mathcal{A})\\}$.

  3. 3.

If $Q$ contains points $p_{1}=(x_{1},y_{1})$ and $p_{2}=(x_{2},y_{2})$ such
that $x_{1}-y_{1}=x_{2}-y_{2}$, then $p_{1}=p_{2}$.

To show the properties, we exploit the fact that the points are processed in
the lexicographical order: When we process a point $q\in Q$, it is the
lexicographically smallest point in $Q$, and all the points that we add to $Q$
while processing $q$ are larger than it.

Property 1. We first prove that $\mathcal{P}\supseteq\mathcal{B}(\mathcal{G})$
and that when we process a point $(x,y)$, the credit associated with it is at
least
$\max_{\mathcal{A}\in\mathcal{G}:(x,y)\in\mathcal{B}(\mathcal{G})}\textsf{credit}_{\mathcal{A}}(x,y)$.
Let $(x,y)\in\mathcal{B}(\mathcal{G})$ be the lexicographically smallest point
which either does not belong to $\mathcal{P}$ or such that the credit
associated with it is smaller than
$\max_{\mathcal{A}\in\mathcal{G}:(x,y)\in\mathcal{B}(\mathcal{A})}\textsf{credit}_{\mathcal{A}}(x,y)$.
Consider an alignment $\mathcal{A}\in\mathcal{G}$ such that
$(x,y)\in\mathcal{B}(\mathcal{A})$ and let $(x^{\prime},y^{\prime})$ be the
predecessor of $(x,y)$ in $\mathcal{B}(\mathcal{A})$. When we process
$(x^{\prime},y^{\prime})$, which happens before we process $(x,y)$ as we
process the points in the lexicographic order, the credit associated with it
is at least
$\textsf{credit}_{\mathcal{A}}(x^{\prime},y^{\prime})\geq\mathsf{ed}(X[x^{\prime}\mathinner{.\,.\allowbreak}],Y[y^{\prime}\mathinner{.\,.\allowbreak}])$,
and therefore $(x,y)$ is added to $Q$ with credit at least
$\textsf{credit}_{\mathcal{A}}(x^{\prime},y^{\prime})-1=\textsf{credit}_{\mathcal{A}}(x,y)$.
As it holds for any $\mathcal{A}\in\mathcal{G}$, we obtain a contradiction.

We now show the opposite direction. Consider a point $(x,y)\in Q$ associated
with the edit distance credit $c$. Suppose that $c$ is achieved when we
process a point $(x^{\prime},y^{\prime})$. By the induction assumption, there
is a greedy alignment $\mathcal{A}\in\mathcal{G}$ such that the credit $c+1$
associated with $(x^{\prime},y^{\prime})$ equals
$\textsf{credit}_{\mathcal{A}}(x^{\prime},y^{\prime})$. Consider a greedy
alignment $\mathcal{A}^{\prime}$ that behaves as $\mathcal{A}$ until
$(x^{\prime},y^{\prime})$
($k-\textsf{credit}_{\mathcal{A}}(x^{\prime},y^{\prime})$ edits), then
proceeds to $(x^{\prime},y^{\prime})$ (one edit), and ends as an arbitrary
optimal greedy alignment between $X[x^{\prime}\mathinner{.\,.\allowbreak}]$
and $Y[y^{\prime}\mathinner{.\,.\allowbreak}]$. The cost of the latter is
$\mathsf{ed}(X[x^{\prime}\mathinner{.\,.\allowbreak}],Y[y^{\prime}\mathinner{.\,.\allowbreak}])\leq
c$. Therefore, the cost of $\mathcal{A}^{\prime}$ is at most $k$ and it is in
$\mathcal{G}$. It follows that
$(x^{\prime},y^{\prime})\in\mathcal{B}(\mathcal{A}^{\prime})$ and that
$c=\textsf{credit}_{\mathcal{A}^{\prime}}(x^{\prime},y^{\prime})$, finishing
the proof.

Property 2. Let $(x,y)$ be the lexicographically smallest point in
$\mathcal{B}(\mathcal{G})$ such that when we process it
$Q\ni(u,v)\notin\cup_{\mathcal{A}\in\mathcal{G}}\\{(x^{\prime},y^{\prime})\text{
is the successor of }(x,y)\text{ in }\mathcal{B}(\mathcal{A})\\}$. Suppose
that $(u,v)$ was added to $Q$ when we processed a point
$(u^{\prime},v^{\prime})$. Similarly to above, we can construct an alignment
$\mathcal{A}\in\mathcal{G}$ such that
$(u^{\prime},v^{\prime}),(u,v)\in\mathcal{B}(\mathcal{A})$. As we processed
$(u^{\prime},v^{\prime})$ before $(x,y)$, we must have that
$(u^{\prime},v^{\prime})$ is lexicographically smaller than $(x,y)$, while
$(u,v)$ is lexicographically larger than $(x,y)$, and therefore $(u,v)$ is the
successor of $(x,y)$ in $\mathcal{B}(\mathcal{A})$, a contradiction. On the
other hand, if $(u,v)\text{ is the successor of }(x,y)\text{ in
}\mathcal{B}(\mathcal{A})$ for some $\mathcal{A}\in\mathcal{G}$, then it must
be in $Q$ when we process $(x,y)$: if $(u^{\prime},v^{\prime})$ is the
predecessor of $(u,v)$ in $\mathcal{B}(\mathcal{A})$, then
$(u^{\prime},v^{\prime})$ is at most $(x,y)$, and when we process it, we add
$(u,v)$ to $Q$.

Property 3. We show the property by induction. It is true at initialisation.
Suppose that the property is violated when we process a point $(x,y)\in Q$.
Recall that we extract $(x,y)$ and call GreedyMatch for a subset of points
$\\{(x+1,y+1),(x+1,y),(x,y+1)\\}$. The point $(x+1,y+1)$ is in the same
diagonal as $(x,y)$ that we extract from $Q$, and therefore the call for it
does not violate the property. Consider now the point $(x+1,y)$ (resp.,
$(x,y+1)$) and assume that the diagonal containing it also contains a point
$(x^{\prime},y^{\prime})\in Q$. If we added $(x^{\prime},y^{\prime})$ to $Q$
when we called GreedyMatch for a point $(x^{\prime\prime},y^{\prime\prime})$,
we have that $(x^{\prime\prime},y^{\prime\prime})$ is in the same diagonal,
$X[x^{\prime\prime}\mathinner{.\,.\allowbreak}x^{\prime}-1]=Y[y^{\prime\prime}\mathinner{.\,.\allowbreak}y^{\prime}-1]$,
and $X[x^{\prime}]\neq Y[y^{\prime}]$. As we process the points in the
lexicographic order, at least one of the points
$(x^{\prime\prime}-1,y^{\prime\prime}-1)$,
$(x^{\prime\prime}-1,y^{\prime\prime})$,
$(x^{\prime\prime},y^{\prime\prime}-1)$ is strictly smaller than $(x,y)$. By
considering each of the cases, from the definition we obtain that
$(x^{\prime\prime},y^{\prime\prime})$ is at most $(x+1,y)$ (resp., $(x,y+1)$).
As all three points $(x^{\prime\prime},y^{\prime\prime})$, $(x+1,y)$ (resp.,
$(x,y+1)$), $(x^{\prime},y^{\prime})$ are on the same diagonal, it follows
that GreedyMatch for $(x+1,y)$ outputs $(x^{\prime},y^{\prime})$.

Correctness and complexity. $[x,x^{\prime}]$ is a dummy segment in
$X^{\mathcal{M}_{k}(X,Y)}$ iff there exists $-k\leq\delta\leq k$ such that the
following three conditions are satisfied, where $y=x+\delta$ and
$y^{\prime}=x^{\prime}+\delta$:

  1. 1.

$\mathcal{B}(\mathcal{G})$ does not contain any points with the $x$-coordinate
in $[x\mathinner{.\,.\allowbreak}x^{\prime}]$ or the $y$-coordinate in
$[y\mathinner{.\,.\allowbreak}y^{\prime}]$;

  2. 2.

$\mathcal{B}(\mathcal{G})$ contains $q=(x^{\prime}+1,y^{\prime}+1)$;

  3. 3.

The predecessor $p$ of $q$ in $\mathcal{B}(\mathcal{G})$ is one of the points
$(x-1,y-1),(x-1,y),(x,y-1)$.

Therefore, if $[x,x^{\prime}]$ is a maximal dummy segment, then by Property 2,
after we have processed $p$, $Q$ contains a single point $q$ that is obtained
by calling GreedyMatch for the point $(x,y)$. Hence, the implementation
creates the dummy segment $[x,x^{\prime}]$. On the other hand, if the
implementation creates a segment $[x,x^{\prime}]$, then
$\mathcal{B}(\mathcal{G})$ satisfies all three conditions and hence
$[x,x^{\prime}]$ is a maximal dummy segment.

Algorithm 1 implements the set $Q$ as a binary search tree. By Lemma 3.11 and
Property 1, we process $|\mathcal{B}(\mathcal{G})|=|\mathcal{B}_{k}(X,Y)|$
points, spending $\mathcal{O}(\log k+t)$ time per point, which gives the
desired time complexity. To show the space complexity, it suffices to show
that at any moment $|Q|=\mathcal{O}(k)$. By Fact 2.3, for any $(x,y)\in Q$ we
have $y=x+\delta$ for some $-k\leq\delta\leq k$, in other words, the point
belongs to one of $2k+1$ diagonals of the grid. By Property 3, each of the
diagonals contains at most one point from $Q$, which concludes the proof. ∎

We proceed with an auxiliary claim that allows constructing an edit distance
oracle.

######  Claim 5.11.

Given two strings $U,V$, and a data structure of size $s$ that can answer the
$\mathsf{LCE}$ queries on the suffixes of $\overline{U},\overline{V}$ in $t$
time. We can build in $\mathcal{O}(k^{2}t)$ time a data structure that
occupies $\mathcal{O}(k^{2})$ space and can retrieve
$\min(k+1,\mathsf{ed}(U[u\mathinner{.\,.\allowbreak}],V[v\mathinner{.\,.\allowbreak}]))$
in $\mathcal{O}(\log n)$ time.

###### Proof.

The data structure is based on the Landau–Myers–Schmidt algorithm [41].
Consider a table $D$ of size $|U|\times|V|$ such that
$D[i,j]=\mathsf{ed}(U[|U|-i+1\mathinner{.\,.\allowbreak}],V[|V|-j+1\mathinner{.\,.\allowbreak}])=\mathsf{ed}(\overline{U}[1\mathinner{.\,.\allowbreak}i],\overline{V}[1\mathinner{.\,.\allowbreak}j])$.
By Fact 2.3, if $D[i,i+\delta]\leq h$, then $-h\leq\delta\leq h$. Let
$L^{h}(\delta)=\max\\{i:D[i,i+\delta]\leq h\\}$. The data structure consists
of $2k+1$ sorted arrays containing
$L^{0}(\delta),L^{1}(\delta),\ldots,L^{k}(\delta)$, $-k\leq\delta\leq k$. The
arrays occupy $\mathcal{O}(k^{2})$ space and allow to retrieve
$\mathsf{ed}(U[u\mathinner{.\,.\allowbreak}],V[v\mathinner{.\,.\allowbreak}])$
in $\tilde{\mathcal{O}}(1)$ time by simple binary search. The data structure
can be computed via the following recurrence, where
$\textsc{Slide}_{\delta}(u)=u+\mathsf{LCE}(\overline{U}[u\mathinner{.\,.\allowbreak}],\overline{V}[u+\delta\mathinner{.\,.\allowbreak}])$.

$L^{h}(\delta)=\textsc{Slide}_{\delta}\left(\max\begin{cases}L^{h-1}(\delta-1),&\delta>-h;\\\
L^{h-1}(\delta)+1,&\text{always};\\\ L^{h-1}(\delta+1)+1,&\delta<h.\\\
\end{cases}\right)$ (1)

Therefore, given $L^{h-1}$, $L^{h}(\delta)$ can be computed via three
$\mathsf{LCE}$ queries on the suffixes of $\overline{U},\overline{V}$. As a
corollary, the arrays
$\\{L^{0}(\delta),L^{1}(\delta),\ldots,L^{k}(\delta)\\}$, $-k\leq\delta\leq
k$, can be built in $\tilde{\mathcal{O}}(k^{2})$ time. ∎

######  Proposition 5.12.

Consider a non-crossing matching $M$ of strings $X,Y\in\Sigma^{\leq n}$ and an
integer $k\in\mathbb{Z}_{+}$ such that $M\subseteq\mathcal{M}_{k}(X,Y)$ holds
if $\mathsf{ed}(X,Y)\leq k$. Given $k$ and $\mathsf{E}^{M}(X,Y)$, the greedy
encoding $\mathsf{GR}_{k}(X,Y)$ can be computed in
$\tilde{\mathcal{O}}(zk+k^{2}+|\mathcal{B}_{k}(X,Y)|)$ time and
$\tilde{\mathcal{O}}(z+k^{2})$ space, where $z=|\mathsf{LZ}(X^{M}Y^{M})|$.

###### Proof.

First, we pass $k$ and $\mathsf{E}^{M}(X,Y)$ to the procedure of Corollary
5.5. Observe that the returned value $d$ satisfies $d\leq k$ if and only if
$\mathsf{ed}(X,Y)\leq k$. If $\mathsf{ed}(X,Y)>k$, then we simply return
$\mathsf{GR}_{k}(X,Y)=\bot$. In this case, the running time and the space
complexity are $\tilde{\mathcal{O}}(k^{2})$.

Otherwise, our strategy is to compute $\mathcal{M}_{k}(X,Y)$ and then mask out
the corresponding characters of $X^{M}$ and $Y^{M}$ to obtain
$X^{\mathcal{M}_{k}(X,Y)}$ and $Y^{\mathcal{M}_{k}(X,Y)}$. By Lemma 3.9, we
have $\mathcal{M}_{k}(X,Y)=\mathcal{M}_{k}(X^{\prime},Y^{\prime})$, where
$X^{\prime}=\mathsf{num}(X^{M})$ and $Y^{\prime}=\mathsf{num}(Y^{M})$. Hence,
we shall use Lemma 3.11 to compute the dummy segments corresponding to
$\mathcal{M}_{k}(X^{\prime},Y^{\prime})$. For this, we need to support
$\mathsf{LCE}$ queries and edit distance queries on the suffixes of
$X^{\prime},Y^{\prime}$. As for $\mathsf{LCE}$ queries, we rely on Lemma 5.4,
which provides $\mathcal{O}(\log n)$-time $\mathsf{LCE}$ queries on the
suffixes of $X^{\prime},Y^{\prime}$ and on the suffixes of
$\overline{X^{\prime}},\overline{Y^{\prime}}$. We use the latter queries to
build a component of 5.11 for the edit distance queries. After
$\mathcal{O}(k^{2}\log n)$-time preprocessing, these queries can be answered
in $\mathcal{O}(\log k)$ time. Overall, constructing the dummy segments
corresponding to $\mathcal{M}_{k}(X^{\prime},Y^{\prime})$ costs
$\tilde{\mathcal{O}}(k^{2}+|\mathcal{B}_{k}(X,Y)|)$ time and
$\mathcal{O}(k^{2})$ working space.

Our next goal is to convert $\mathsf{D}(X^{M}Y^{M})$ to
$\mathsf{D}(X^{\mathcal{M}_{k}(X,Y)}Y^{\mathcal{M}_{k}(X,Y)})$. For this, we
need to place $\\#$s within each of the computed dummy segments. Consider
updating a working string $Z$ by setting
$Z[\ell\mathinner{.\,.\allowbreak}r):=\\#^{r-\ell}$. To implement this
operation, we build $\mathsf{LZ}(\\#^{r-\ell})$ (of size at most 2), derive
$\mathsf{D}(\\#^{r-\ell})$ (Proposition 4.2(h)), extract
$\mathsf{D}(Z[1\mathinner{.\,.\allowbreak}\ell))$ and
$\mathsf{D}(Z[r\mathinner{.\,.\allowbreak}|Z|])$ (Proposition 4.2(g)), and
finally concatenate into
$\mathsf{D}(Z[1\mathinner{.\,.\allowbreak}\ell)\\#^{r-\ell}Z[r\mathinner{.\,.\allowbreak}|Z|])$
(Proposition 4.2(i)). Overall, each dummy segment is processed in
$\mathcal{O}((z+k)\log^{4}n)$ time and space, for a total of
$\tilde{\mathcal{O}}(zk+k^{2})$ time and $\tilde{\mathcal{O}}(z+k)$ space
across all segments.

Finally, $\mathsf{RS}_{\\#}(X^{\mathcal{M}_{k}(X,Y)})$ and
$\mathsf{RS}_{\\#}(Y^{\mathcal{M}_{k}(X,Y)})$ are constructed in
$\mathcal{O}(k)$ time and space using Proposition 5.2. ∎

######  Corollary 5.13.

Given an integer $k\in\mathbb{Z}_{+}$ and two strings $X,Y\in\Sigma^{\leq
k^{2}}$, one can compute $\mathsf{GR}_{k}(X,Y)$ in
$\tilde{\mathcal{O}}(k^{3})$ time and $\tilde{\mathcal{O}}(k^{2})$ space.

###### Proof.

We shall construct $\mathsf{E}^{\emptyset}(X,Y)$ and then derive
$\mathsf{GR}_{k}(X,Y)$ from Proposition 5.12. Hence, we build a trivial LZ-
like representation of $XY$ (with length-1 phrases) and derive
$\mathsf{D}(XY)=\mathsf{D}(X^{\emptyset}Y^{\emptyset})$ using Proposition
4.2(h). This costs $\mathcal{O}(k^{2}\log^{2}k)$ time and space. The
components $\mathsf{RS}_{\\#}(X^{\emptyset})$ and
$\mathsf{RS}_{\\#}(Y^{\emptyset})$ are trivial (there are no dummy segments).
Using Proposition 5.12 costs
$\tilde{\mathcal{O}}(k^{3}+|\mathcal{B}_{k}(X,Y)|)$ time and
$\tilde{\mathcal{O}}(k^{2})$ space. To finish the proof, note that
$\mathcal{B}_{k}(X,Y)$ can only contain pairs $(x,y)$ such that $1\leq
x\leq|X|$, $1\leq y\leq|Y|$, and $|x-y|\leq k$, which implies
$|\mathcal{B}_{k}(X,Y)|=\mathcal{O}(|X|k)=\mathcal{O}(k^{3})$. ∎

###  5.3 Concatenations and Quasi-greedy Alignments

######  Definition 5.14 (Quasi-greedy alignment).

We say that an alignment $\mathcal{A}$ of two strings $X,Y\in\Sigma^{*}$ is
_quasi-greedy_ if it satisfies at least one of the following symmetric
conditions:

  * •

there exists $\delta\in[1\mathinner{.\,.\allowbreak}|X|+1]$ such that
$(\delta,1)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([\delta\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|])$;

  * •

there exists $\delta\in[1\mathinner{.\,.\allowbreak}|Y|+1]$ such that
$(1,\delta)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([1\mathinner{.\,.\allowbreak}|X|]\times[\delta\mathinner{.\,.\allowbreak}|Y|])$;

Given $k\geq 0$, we denote by $\mathsf{qGA}_{k}(X,Y)$ the set of all quasi-
greedy alignments $\mathcal{A}$ of $X,Y$ with $\mathsf{cost}(\mathcal{A})\leq
k$.

######  Lemma 5.15.

Consider an alignment $\mathcal{A}\in\mathsf{qGA}_{k}(X_{p}X_{s},Y_{p}Y_{s})$,
where $X_{p},X_{s},Y_{p},Y_{s}\in\Sigma^{*}$ and $k\in\mathbb{Z}_{\geq 0}$.
Then,
$\mathcal{A}_{[1\mathinner{.\,.\allowbreak}|X_{p}|+1),[1\mathinner{.\,.\allowbreak}|Y_{p}|+1)}\in\mathsf{qGA}_{k+||X_{s}|-|Y_{s}||}(X_{p},Y_{p})$
and
$\mathcal{A}_{[|X_{p}|+1\mathinner{.\,.\allowbreak}],[|Y_{p}|+1\mathinner{.\,.\allowbreak}]}\in\mathsf{qGA}_{k+||X_{p}|-|Y_{p}||}(X_{s},Y_{s})$.

###### Proof.

For brevity, let $X=X_{p}X_{s}$, $Y=Y_{p}Y_{s}$; $n_{p}=|X_{p}|$,
$n_{s}=|X_{s}|$, $n=|X|$, $m_{p}=|Y_{p}|$, $m_{s}=|Y_{s}|$, $m=|Y|$.

Let $\mathcal{A}=(x_{t},y_{t})_{t=1}^{q}$ and let $(x_{i_{p}},y_{i_{p}})$ be
the leftmost pair $(x,y)\in\mathcal{A}$ such that $x>n_{p}$ or $y>m_{p}$. By
symmetry, we assume without loss of generality that $x_{i_{p}}=n_{p}+1$; see
Fig. 2. Observe that
$\mathcal{A}_{p}:=\mathcal{A}_{[1\mathinner{.\,.\allowbreak}n_{p}+1),[1\mathinner{.\,.\allowbreak}m_{p}+1)}$
is the union of $(x_{t},y_{t})_{t=1}^{i_{p}-1}$ and
$(n_{p}+1,y)_{y=y_{i_{p}}}^{m_{p}+1}$. Furthermore,
$\mathcal{B}(\mathcal{A}_{p})=\\{(x_{t},y_{t})\in\mathcal{B}(\mathcal{A}):t\in[1\mathinner{.\,.\allowbreak}p)\\}\cup\\{(n_{p}+1,y):y\in[y_{p}\mathinner{.\,.\allowbreak}m_{p}+1]\\}$.
Let $k_{p}$ be the size of the former component. Then,
$k\geq\mathsf{cost}(\mathcal{A})\geq
k_{p}+\mathsf{ed}(X_{s},Y_{p}[y_{i_{p}}\mathinner{.\,.\allowbreak}]Y_{s})\geq
k_{p}+|Y_{p}[y_{i_{p}}\mathinner{.\,.\allowbreak}]|+m_{s}-n_{s}$, so that
$\mathsf{cost}(\mathcal{A}_{p})=k_{p}+|Y_{p}[y_{p}\mathinner{.\,.\allowbreak}]|\leq
k+n_{s}-m_{s}\leq k-\big{|}|X_{s}|-|Y_{s}|\big{|}$. It remains to prove that
$\mathcal{A}_{p}$ is a quasi-greedy alignment. By Definition 3.6 applied to
$\mathcal{A}$, we have two possibilities:

  * •

There exists $\delta\in[1\mathinner{.\,.\allowbreak}n+1]$ such that
$(\delta,1)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([\delta\mathinner{.\,.\allowbreak}n]\times[1\mathinner{.\,.\allowbreak}m])$.
If $\delta\leq n_{p}+1$, then we also have that $(\delta,1)\in\mathcal{A}_{p}$
and $X_{p}[x]\neq Y_{p}[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A}_{p})\cap([\delta\mathinner{.\,.\allowbreak}n_{p}]\times[1\mathinner{.\,.\allowbreak}m_{p}])$.
Otherwise, $(x_{i_{p}},y_{i_{p}})=(n_{p}+1,1)\in\mathcal{A}_{p}$, so
$\mathcal{A}_{p}$ is trivially quasi-greedy.

  * •

There exists $\delta\in[1\mathinner{.\,.\allowbreak}m+1]$ such that
$(1,\delta)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([1\mathinner{.\,.\allowbreak}n]\times[\delta\mathinner{.\,.\allowbreak}m])$.
If $\delta\leq y_{i_{p}}$, then we also have that
$(1,\delta)\in\mathcal{A}_{p}$ and $X_{p}[x]\neq Y_{p}[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A}_{p})\cap([1\mathinner{.\,.\allowbreak}n_{p}]\times[\delta\mathinner{.\,.\allowbreak}m_{p}])$.
Otherwise, $n_{p}=0$ because $(1,\delta)$ cannot cross $(n_{p}+1,y_{p})$.
Hence, $\mathcal{A}_{p}$ is trivially quasi-greedy.

Now, let $(x_{i_{s}},y_{i_{s}})$ be the leftmost pair $(x,y)\in\mathcal{A}$
such that $x>n_{p}$ and $y>m_{p}$. By symmetry, we assume without loss of
generality that $y_{i_{s}}=m_{p}+1$; see Fig. 2. Observe that
$\mathcal{A}_{s}:=\mathcal{A}_{[n_{p}+1\mathinner{.\,.\allowbreak}],[m_{p}+1\mathinner{.\,.\allowbreak}]}$
is the union of $(x,1)_{x=1}^{x_{i_{s}}-n_{p}-1}$ and
$(x_{t}-n_{p},y_{t}-m_{p})_{t={i_{s}}}^{q}$. Furthermore,
$\mathcal{B}(\mathcal{A}_{s})=\\{(x_{t}-n_{s},y_{t}-m_{s})\in\mathcal{B}(\mathcal{A}):t\in[i_{s}\mathinner{.\,.\allowbreak}q]\\}\cup\\{(x,1):x\in[1\mathinner{.\,.\allowbreak}x_{i_{s}}-n_{p})\\}$.
Let $k_{s}$ be the size of the former component. Then,
$k\geq\mathsf{cost}(\mathcal{A})\geq
k_{s}-1+\mathsf{ed}(X_{p}X_{s}[1\mathinner{.\,.\allowbreak}x_{i_{s}}-n_{p}),Y_{p})\geq
k_{s}-1+x_{i_{s}}-m_{p}$, so that
$\mathsf{cost}(\mathcal{A}_{s})=k_{s}-1+x_{i_{s}}-n_{p}\leq k+m_{p}-n_{p}\leq
k-\big{|}|X_{p}|-|Y_{p}|\big{|}$. It remains to prove that $\mathcal{A}_{s}$
is a quasi-greedy alignment. By Definition 3.6 applied to $\mathcal{A}$, we
have two possibilities:

  * •

There exists $\delta\in[1\mathinner{.\,.\allowbreak}n+1]$ such that
$(\delta,1)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([\delta\mathinner{.\,.\allowbreak}n]\times[1\mathinner{.\,.\allowbreak}m])$.
If $\delta\leq x_{i_{s}}$, then $(x_{i_{s}}-n_{p},1)\in\mathcal{A}_{s}$ and
$X_{s}[x]\neq Y_{s}[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A}_{s})\cap([x_{i_{s}}-n_{p}\mathinner{.\,.\allowbreak}n_{s}]\times[1\mathinner{.\,.\allowbreak}m_{s}])$.
Otherwise, $(\delta-n_{p},1)\in\mathcal{A}_{s}$ and $X_{s}[x]\neq Y_{s}[y]$
holds for every $(x,y)\in\mathcal{B}(\mathcal{A}_{s})\cap([\delta-
n_{p}\mathinner{.\,.\allowbreak}n_{s}]\times[1\mathinner{.\,.\allowbreak}m_{s}])$.

  * •

There exists $\delta\in[1\mathinner{.\,.\allowbreak}m+1]$ such that
$(1,\delta)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([1\mathinner{.\,.\allowbreak}n]\times[\delta\mathinner{.\,.\allowbreak}m])$.
If $\delta\leq m_{p}+1$, then $(x_{i_{s}}-n_{p},1)\in\mathcal{A}_{s}$ and
$X_{s}[x]\neq Y_{s}[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A}_{s})\cap([x_{i_{s}}-n_{p}\mathinner{.\,.\allowbreak}n_{s}]\times[1\mathinner{.\,.\allowbreak}m_{s}])$.
Otherwise, $x_{i_{s}}=1$ and $n_{p}=0$ because $(1,\delta)$ cannot cross
$(x_{i_{s}},m_{p}+1)$. Hence, $(1,\delta-m_{p})\in\mathcal{A}$ and
$X_{s}[x]\neq Y_{s}[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A}_{s})\cap([1\mathinner{.\,.\allowbreak}n_{s}]\times[\delta-
m_{p}\mathinner{.\,.\allowbreak}m_{s}])$.∎

$n_{p}+1$$x_{i_{s}}$$1$$X_{p}X_{s}:$$1$$m_{p}+1$$y_{i_{p}}$$Y_{p}Y_{s}:$
Figure 2: Alignment $\mathcal{A}\in\mathsf{qGA}_{k}(X_{p}X_{s},Y_{p}Y_{s})$.

For strings $X,Y\in\Sigma^{*}$ and an integer $k\geq\mathsf{ed}(X,Y)$, we
define a set

$\mathsf{q}\mathcal{M}_{k}(X,Y)=\bigcap_{\mathcal{A}\in\mathsf{qGA}_{k}(X,Y)}\mathcal{M}_{X,Y}(\mathcal{A})$

of _common matches_ of all alignments $\mathcal{A}\in\mathsf{qGA}_{k}(X,Y)$.

######  Definition 5.16.

For strings $X,Y\in\Sigma^{*}$ and an integer $k$, we define the _quasi-greedy
encoding_

$\mathsf{qGR}_{k}(X,Y)=\begin{cases}\mathsf{E}^{\mathsf{q}\mathcal{M}_{k}(X,Y)}(X,Y)&\text{if
}\mathsf{ed}(X,Y)\leq k,\\\ \bot&\text{otherwise.}\end{cases}$

######  Corollary 5.17.

Consider strings $X,Y\in\Sigma^{\leq n}$. Define $X^{\prime}=\$_{1}X$ and
$Y^{\prime}=\$_{2}Y$, where $\$_{1}\neq\$_{2}$ are special symbols not in
$\Sigma$. Let $M^{\prime}=\mathcal{M}_{k+1}(X^{\prime},Y^{\prime})$ and
$M=\mathsf{q}\mathcal{M}_{k}(X,Y)$. The following properties hold:

  1. (a)

Given the dummy segments for one of the strings
$X^{M},(X^{\prime})^{M^{\prime}}$, the dummy segments for the other string can
be constructed in $\mathcal{O}(k)$ time and space;

  2. (b)

Given one of the encodings
$\mathsf{qGR}_{k}(X,Y),\mathsf{GR}_{k+1}(X^{\prime},Y^{\prime})$, the other
encoding can be constructed in $\mathcal{O}(k^{2}\log^{4}n)$ time and space;

  3. (c)

The quasi-greedy encoding $\mathsf{qGR}_{k}(X,Y)$ occupies
$\mathcal{O}(k^{2}\log^{4}n)$ space.

###### Proof.

Let us first show that
$\mathcal{A}^{\prime}\mapsto\mathcal{A}^{\prime}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$
bijectively maps $\mathsf{GA}_{k+1}(X^{\prime},Y^{\prime})$ to
$\mathsf{qGA}_{k}(X,Y)$.

Consider a greedy alignment
$\mathcal{A}^{\prime}\in\mathsf{GA}_{k+1}(X^{\prime},Y^{\prime})$ and let
$\mathcal{A}=\mathcal{A}^{\prime}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$.
Lemma 5.15 yields $\mathcal{A}\in\mathsf{qGA}_{k+1}(X,Y)$. However, we
actually have $\mathsf{cost}(\mathcal{A})\leq k$ because
$\mathcal{M}(\mathcal{A}^{\prime})=\\{(x,y):(x+1,y+1)\in\mathcal{M}(\mathcal{A})\\}$
holds due to $X^{\prime}[1]\neq Y^{\prime}[1]$.

We now show the opposite direction. Let $\mathcal{A}\in\mathsf{qGA}_{k}(X,Y)$.
Suppose that there is $\delta\in[1\mathinner{.\,.\allowbreak}|Y|]$ such that
$(1,\delta)\in\mathcal{A}$ and $X[x]\neq Y[y]$ holds for every
$(x,y)\in\mathcal{B}(\mathcal{A})\cap([1\mathinner{.\,.\allowbreak}|X|]\times[\delta\mathinner{.\,.\allowbreak}|Y|])$
(the other case is symmetrical). It follows in particular that $\mathcal{A}$
contains elements $\\{(1,1),(1,2),\ldots,(1,\delta)\\}$. We start by replacing
each element $(x,y)$ of $\mathcal{A}$ with $(x+1,y+1)$. We add an element
$(1,1)$ to $\mathcal{A}$ and replace each element $(2,i)$, $2\leq
i\leq\delta+1$, with $(1,i)$. Finally, we add an element $(2,\delta+1)$. We
claim that the resulting alignment $\mathcal{A}^{\prime}$, that we treat as an
alignment of $X^{\prime}$ and $Y^{\prime}$, is greedy. For every element
$(x,y)\in\mathcal{B}(\mathcal{A}^{\prime})\cap([2\mathinner{.\,.\allowbreak}|X^{\prime}|]\times[\delta+1\mathinner{.\,.\allowbreak}|Y^{\prime}|])$
we have
$(x-1,y-1)\in\mathcal{B}(\mathcal{A})\cap([1\mathinner{.\,.\allowbreak}|X|]\times[\delta\mathinner{.\,.\allowbreak}|Y|])$
and hence from quasi-greediness of $\mathcal{A}$ we obtain
$X^{\prime}[x]=X[x-1]\neq Y[y-1]=Y^{\prime}[y]$. For every element
$(1,i)\in\mathcal{A}^{\prime}$ we have $X^{\prime}[1]=\$_{1}\neq Y[i]$. It
follows that $\mathcal{A}^{\prime}$ is greedy. In addition, the cost of
$\mathcal{A}^{\prime}$ equals the cost of $\mathcal{A}$ plus one and hence is
bounded by $k+1$. Finally, note that
$\mathcal{M}(\mathcal{A}^{\prime})=\\{(x,y):(x-1,y-1)\in\mathcal{M}(\mathcal{A})\\}$.

Let $M^{\prime}=\mathcal{M}_{k+1}(X^{\prime},Y^{\prime})$ and
$M=\mathsf{q}\mathcal{M}_{k}(X,Y)$. From above, we obtain
$M^{\prime}=\\{(x+1,y+1):(x,y)\in M\\}$. Therefore,
$(X^{\prime})^{M^{\prime}}[2\mathinner{.\,.\allowbreak}]=X^{M}$ and
$(Y^{\prime})^{M^{\prime}}[2\mathinner{.\,.\allowbreak}]=Y^{M}$.

It follows that we can obtain the dummy segments for $X^{M}$ by subtracting
one from the endpoints of each dummy segment of $(X^{\prime})^{M^{\prime}}$,
and analogously for $Y^{M}$. The reverse claim is obtained analogously, by
adding one to the endpoints. As the number of the dummy segments in $X^{M}$
and $(X^{\prime})^{M^{\prime}}$ is $\mathcal{O}(k)$ by Lemma 3.10, (a)
follows.

From (a) it follows that given the rank data structures for one pair of
strings $X^{M},Y^{M}$ and
$(X^{\prime})^{M^{\prime}},(Y^{\prime})^{M^{\prime}}$, the rank data
structures for the other pair can be built in $\mathcal{O}(k)$ time and space.
We now must show that given the $\mathsf{D}$ data structure for one of the two
strings $X^{M}Y^{M},(X^{\prime})^{M^{\prime}}(Y^{\prime})^{M^{\prime}}$, we
can construct the $\mathsf{D}$ data structure for the other string
efficiently. Assume that we are given
$\mathsf{D}((X^{\prime})^{M^{\prime}}(Y^{\prime})^{M^{\prime}})$, the other
case is analogous. We extract all non-dummy segments using Proposition 4.2(g)
and concatenate them using Proposition 4.2(i). In total, it takes
$\mathcal{O}(k^{2}\log^{4}n)$ time and space, giving (b).

(c) follows immediately from (b). ∎

From Corollaries 5.13 and 5.17 it immediately follows that:

######  Claim 5.18.

Given an integer $k\in\mathbb{Z}_{+}$ and strings $X,Y\in\Sigma^{\leq k^{2}}$,
one can compute $\mathsf{qGR}_{k}(X,Y)$ in $\tilde{\mathcal{O}}(k^{3})$ time
and $\tilde{\mathcal{O}}(k^{2})$ space.

######  Corollary 5.19.

Consider a non-crossing matching $M$ of strings $X,Y\in\Sigma^{\leq n}$ and an
integer $k\in\mathbb{Z}_{+}$ such that
$M\subseteq\mathsf{q}\mathcal{M}_{k}(X,Y)$ if $\mathsf{ed}(X,Y)\leq k$. Given
$k$ and $\mathsf{E}^{M}(X,Y)$, the quasi-greedy encoding
$\mathsf{qGR}_{k}(X,Y)$ can be computed in $\tilde{\mathcal{O}}(k^{5}+zk)$
time and $\tilde{\mathcal{O}}(k^{2}+z)$ space, where
$z=|\mathsf{LZ}(X^{M}Y^{M})|$.

###### Proof.

Let $\$_{1}\neq\$_{2}$ be auxiliary symbols not in $\Sigma\cup\\{\\#\\}$. We
construct $M^{\prime}=\\{(x+1,y+1):(x,y)\in M\\}$ and
$\mathsf{E}^{M^{\prime}}(\$_{1}X,\$_{2}Y)$. Note that $M^{\prime}$ is a non-
crossing matching of $\$_{1}X,\$_{2}Y$. Moreover, if
$M\subseteq\mathsf{q}\mathcal{M}_{k}(X,Y)$, then
$M^{\prime}\subseteq\mathcal{M}_{k+1}(\$_{1}X,\$_{2}Y)$ holds by Corollary
5.17. Hence, we can construct $\mathsf{GR}_{k+1}(\$_{1}X,\$_{2}Y)$ using
Proposition 5.12. Then, we derive $\mathsf{qGR}_{k}(X,Y)$ using Corollary 5.17
again. By Lemma 3.11, we have
$|\mathcal{B}_{k+1}(\$_{1}X,\$_{2}Y)|=\mathcal{O}(k^{5})$, which gives the
desired time bound. ∎

######  Observation 5.20.

Let $k^{\prime}\leq k$. Given $\mathsf{qGR}_{k}(X,Y)$, the encoding
$\mathsf{qGR}_{k^{\prime}}(X,Y)$ can be computed in
$\tilde{\mathcal{O}}(k^{5})$ time and $\tilde{\mathcal{O}}(k^{2})$ space.

###### Proof.

For $k^{\prime}\leq k$, we have
$\mathsf{q}\mathcal{M}_{k}(X,Y)\subseteq\mathsf{q}\mathcal{M}_{k^{\prime}}(X,Y)$
by definition. The claim follows from Corollary 5.19. ∎

We now show that the quasi-greedy encodings are _concatenatable_.

######  Lemma 5.21.

Consider strings $X_{p},Y_{p},X_{s},Y_{s}\in\Sigma^{\leq n}$ and
$k\in\mathbb{Z}_{+}$. Assume
$\max\\{\bigl{|}|X_{p}|-|Y_{p}|\bigr{|},\bigl{|}|X_{s}|-|Y_{s}|\bigr{|}\\}=\mathcal{O}(k)$.
Given $\mathsf{qGR}_{k+||X_{s}|-|Y_{s}||}(X_{p},Y_{p})$ and
$\mathsf{qGR}_{k+||X_{p}|-|Y_{p}||}(X_{s},Y_{s})$, one can compute
$\mathsf{qGR}_{k}(X_{p}X_{s},Y_{p}Y_{s})$ in $\tilde{\mathcal{O}}(k^{5})$ time
and $\tilde{\mathcal{O}}(k^{2})$ space.

###### Proof.

For brevity, let
$M_{p}=\mathsf{q}\mathcal{M}_{k+||X_{s}|-|Y_{s}||}(X_{p},Y_{p})$ and
$M_{s}=\mathsf{q}\mathcal{M}_{k+||X_{p}|-|Y_{p}||}(X_{s},Y_{s})$. Let also
$X=X_{p}X_{s}$, $Y=Y_{p}Y_{s}$.

By Lemma 5.15, if $\mathsf{ed}(X,Y)\leq k$, then
$M:=M_{p}\cup\\{(x+|X_{p}|,y+|Y_{p}|):(x,y)\in
M_{s}\\}\subseteq\mathsf{q}\mathcal{M}_{k}(X,Y)$. Hence, we shall construct
$\mathsf{E}^{M}(X,Y)$ and then apply Corollary 5.19.

For this, we extract
$\mathsf{D}(X_{p}^{M_{p}}),\mathsf{D}(X_{s}^{M_{s}}),\mathsf{D}(Y_{p}^{M_{p}}),\mathsf{D}(Y_{s}^{M_{s}})$
using Proposition 4.2(g), and then concatenate them to
$\mathsf{D}(X^{M}Y^{M})=\mathsf{D}(X_{p}^{M_{p}}X_{s}^{M_{s}}Y_{p}^{M_{p}}Y_{s}^{M_{s}})$
using Proposition 4.2(i). Overall, this takes $\mathcal{O}(k^{2}\log^{4}n)$
time. Then, we use Proposition 5.2 to build $\mathsf{RS}_{\\#}(X^{M})$ and
$\mathsf{RS}_{\\#}(Y^{M})$ in $\tilde{\mathcal{O}}(k)$ time.

Finally, we note that using Corollary 5.19 costs $\tilde{\mathcal{O}}(k^{5})$
time and $\tilde{\mathcal{O}}(k^{2})$ space (here we use the fact that
$\bigl{|}|X_{p}|-|Y_{p}|\bigr{|}=\mathcal{O}(k)$). ∎

Finally, as a corollary we derive an algorithm that can compute the quasi-
greedy encoding of arbitrarily long strings.

######  Corollary 5.22.

Assuming constant-time random access to a string $X\in\Sigma^{\ell}$ and
streaming access to a string $Y\in\Sigma^{\ell}$, where $\ell\leq n$, there is