an algorithm that constructs $\mathsf{qGR}_{k}(X,Y)$ with a delay of at most
$k^{2}$ characters in $\tilde{\mathcal{O}}(k^{3})$ amortised time per
character and $\tilde{\mathcal{O}}(k^{2})$ space. The delay means that at the
moment when the $y$-th character of $Y$ arrives, the algorithm knows
$\mathsf{qGR}_{k}(X[\mathinner{.\,.\allowbreak}y^{\prime}],Y[\mathinner{.\,.\allowbreak}y^{\prime}])$,
where $|y-y^{\prime}|\leq k^{2}$.

###### Proof.

If $\ell\leq k^{2}$, construct $\mathsf{qGR}_{k}(X,Y)$ via 5.18 in
$\tilde{\mathcal{O}}(k^{3})$ (total) time and $\tilde{\mathcal{O}}(k^{2})$
space. Otherwise, partition the strings into non-overlapping blocks
$X=X_{1}\cdots X_{p}$ and $Y=Y_{1}\cdots Y_{p}$ so that
$|X_{i}|=|Y_{i}|=k^{2}$ for all $i\in[1\mathinner{.\,.\allowbreak}p)$ and
$|X_{p}|=|Y_{z}|=\ell\bmod k^{2}$. Suppose that we have computed
$\mathsf{qGR}_{k}(X_{1}\cdots X_{i-1},Y_{1}\cdots Y_{i-1})$ for
$i\in[1\mathinner{.\,.\allowbreak}p)$. Compute $\mathsf{qGR}_{k}(X_{1}\cdots
X_{i},Y_{1}\cdots Y_{i})$ in the following manner: first, compute
$\mathsf{qGR}_{k}(X_{i},Y_{i})$ in $\mathcal{O}(k^{5})$ time and
$\mathcal{O}(k^{2})$ space via 5.18, and then compute
$\mathsf{qGR}_{k}(X_{1}\cdots X_{i},Y_{1}\cdots Y_{i})$ in
$\tilde{\mathcal{O}}(k^{5})$ time and $\tilde{\mathcal{O}}(k^{2})$ space via
Lemma 5.21. ∎

###  5.4 Products of Greedy Alignments

See 3.12

See 3.13

###### Proof.

We proceed by induction on $|X|+|Y|+|Z|$. In the base case, when at least one
of the strings $X,Y,Z$ is empty, we set $\mathcal{A}^{X,Y}$ and
$\mathcal{A}^{Y,Z}$ to be any greedy optimal alignments of $X,Y$ and $Y,Z$,
respectively, so that $\mathsf{cost}(\mathcal{A}^{X,Y})=\mathsf{ed}(X,Y)$ and
$\mathsf{cost}(\mathcal{A}^{Y,Z})=\mathsf{ed}(Y,Z)\leq\mathsf{ed}(X,Y)+\mathsf{ed}(X,Z)\leq\mathsf{ed}(X,Y)+\mathsf{cost}(\mathcal{A}^{X,Z})$.
Moreover, it easy to check that $\mathcal{A}^{X,Z}$ is a product of
$\mathcal{A}^{X,Y}$ and $\mathcal{A}^{Y,Z}$ because two out of these three
alignments simply delete all characters of the non-empty string.

In the inductive step, we assume that all strings $X,Y,Z$ are non-empty, and
we consider several cases.

  1. 1.

$\mathbf{X[1]=Z[1]=Y[1]}$.
We recurse on $X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$,
$Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$,
$Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$,
which is greedy due to $X[1]\simeq_{\mathcal{A}^{X,Z}}Z[1]$. This yields
greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
at most $d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})+\mathsf{ed}(X,Y)=d$. We
extend them so that $X[1]\simeq_{\mathcal{A}^{X,Y}}Y[1]$ and
$Y[1]\simeq_{\mathcal{A}^{Y,Z}}Z[1]$, obtaining alignments of cost up to $d$.

  2. 2.

$\mathbf{X[1]=Z[1]\neq Y[1]}$.
In this case, we have
$\mathsf{ed}(X,Y)>\min(\mathsf{ed}(X[2\mathinner{.\,.\allowbreak}],Y[2\mathinner{.\,.\allowbreak}]),\mathsf{ed}(X[2\mathinner{.\,.\allowbreak}],Y),\mathsf{ed}(X,Y[2\mathinner{.\,.\allowbreak}]))$.

    1. (a)

If
$\mathsf{ed}(X,Y)>\mathsf{ed}(X[2\mathinner{.\,.\allowbreak}],Y[2\mathinner{.\,.\allowbreak}])$,
we recurse on $X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$,
$Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$,
$Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$,
which is greedy due to $X[1]\simeq_{\mathcal{A}^{X,Z}}Z[1]$. This yields
greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
at most $d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})+\mathsf{ed}(X,Y)-1=d-1$.
We extend them so that $X[1]\sim_{\mathcal{A}^{X,Y}}Y[1]$ and
$Y[1]\sim_{\mathcal{A}^{Y,Z}}Z[1]$, obtaining alignments of cost up to $d$.

    2. (b)

If $\mathsf{ed}(X,Y)>\mathsf{ed}(X[2\mathinner{.\,.\allowbreak}],Y)$, we
recurse on $X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$, $Y^{\prime}=Y$,
$Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$,
which is greedy due to $X[1]\simeq_{\mathcal{A}^{X,Z}}Z[1]$. This yields
greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
at most $d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})+\mathsf{ed}(X,Y)-1=d-1$.
We extend them so that $\mathcal{A}^{X,Y}$ deletes $X[1]$ and
$\mathcal{A}^{Y,Z}$ deletes $Z[1]$, obtaining alignments of cost up to $d$.

    3. (c)

If $\mathsf{ed}(X,Y)>\mathsf{ed}(X,Y[2\mathinner{.\,.\allowbreak}])$, we
recurse on $X^{\prime}=X$, $Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$,
$Z^{\prime}=Z$, and $\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
at most $d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})+\mathsf{ed}(X,Y)-1=d-1$.
We extend them so that $\mathcal{A}^{X,Y}$ and $\mathcal{A}^{Y,Z}$ both delete
$Y[1]$, obtaining alignments of cost up to $d$.

  3. 3.

$\mathbf{X[1]\neq Z[1]=Y[1]}$.

    1. (a)

If $\mathcal{A}^{X,Z}$ deletes $X[1]$, we recurse on
$X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$, $Y^{\prime}=Y$, $Z^{\prime}=Z$,
and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[1\mathinner{.\,.\allowbreak}]}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
$\leq
d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})-2+\mathsf{ed}(X^{\prime},Y^{\prime})\leq
d-1$. We derive $\mathcal{A}^{Y,Z}=\mathcal{A}^{Y^{\prime},Z^{\prime}}$ and
extend $\mathcal{A}^{X^{\prime},Y^{\prime}}$ so that $\mathcal{A}^{X,Y}$
deletes $X[1]$, obtaining an alignment of cost up to $d$.

    2. (b)

If $\mathcal{A}^{X,Z}$ deletes $Z[1]$, we recurse on $X^{\prime}=X$,
$Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$,
$Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[1\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
$\leq
d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})-2+\mathsf{ed}(X^{\prime},Y^{\prime})\leq
d-1$. We extend them so that $\mathcal{A}^{X,Y}$ deletes $Y[1]$ and
$Y[1]\simeq_{\mathcal{A}^{Y,Z}}Z[1]$, obtaining alignments of cost up to $d$.

    3. (c)

If $X[1]\sim_{\mathcal{A}^{X,Z}}Z[1]$, we recurse on
$X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$,
$Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$,
$Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
$\leq
d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})-2+\mathsf{ed}(X^{\prime},Y^{\prime})\leq
d-1$. We extend them so that $X[1]\sim_{\mathcal{A}^{X,Y}}Y[1]$ and
$Y[1]\simeq_{\mathcal{A}^{Y,Z}}Z[1]$, obtaining alignments of cost up to $d$.

  4. 4.

$\mathbf{X[1]\neq Z[1]\neq Y[1]}$. (Note that this case allows both
$X[1]=Y[1]$ and $X[1]\neq Y[1]$.)

    1. (a)

If $\mathcal{A}^{X,Z}$ deletes $X[1]$, we recurse on
$X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$,
$Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$, $Z^{\prime}=Z$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[1\mathinner{.\,.\allowbreak}]}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
at most
$d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})-2+\mathsf{ed}(X^{\prime},Y^{\prime})\leq
d-2$. We extend them so that $X[1]\sim_{\mathcal{A}^{X,Y}}Y[1]$ and
$\mathcal{A}^{Y,Z}$ deletes $Y[1]$, obtaining alignments of cost up to $d-1$.

    2. (b)

If $\mathcal{A}^{X,Z}$ deletes $Z[1]$, we recurse on $X^{\prime}=X$,
$Y^{\prime}=Y$, $Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[1\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
$\leq d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})-2+\mathsf{ed}(X,Y)=d-2$. We
derive $\mathcal{A}^{X,Y}=\mathcal{A}^{X^{\prime},Y^{\prime}}$ and extend
$\mathcal{A}^{Y^{\prime},Z^{\prime}}$ so that $\mathcal{A}^{Y,Z}$ deletes
$Z[1]$, obtaining an alignment of cost up to $d-1$.

    3. (c)

If $X[1]\sim_{\mathcal{A}^{X,Z}}Z[1]$, we recurse on
$X^{\prime}=X[2\mathinner{.\,.\allowbreak}]$,
$Y^{\prime}=Y[2\mathinner{.\,.\allowbreak}]$,
$Z^{\prime}=Z[2\mathinner{.\,.\allowbreak}]$, and
$\mathcal{A}^{X^{\prime},Z^{\prime}}=\mathcal{A}^{X,Z}_{[2\mathinner{.\,.\allowbreak}],[2\mathinner{.\,.\allowbreak}]}$.
This yields greedy alignments
$\mathcal{A}^{X^{\prime},Y^{\prime}}\\!\\!,A^{Y^{\prime},Z^{\prime}}$ of cost
$\leq
d^{\prime}=2\mathsf{cost}(\mathcal{A}^{X,Z})-2+\mathsf{ed}(X^{\prime},Y^{\prime})\leq
d-2$. We extend them so that $X[1]\sim_{\mathcal{A}^{X,Y}}Y[1]$ and
$Y[1]\sim_{\mathcal{A}^{Y,Z}}Z[1]$, obtaining alignments of cost up to $d-1$.

In all the cases above, $\mathcal{A}^{X,Y}$ is greedy because
$\mathcal{A}^{X^{\prime},Y^{\prime}}$ is greedy and $\mathcal{A}^{X,Y}$
matches $X[1]$ with $Y[1]$ whenever $X[1]=Y[1]$. Similarly,
$\mathcal{A}^{Y,Z}$ is greedy because $\mathcal{A}^{Y^{\prime},Z^{\prime}}$ is
greedy and $\mathcal{A}^{Y,Z}$ matches $Y[1]$ with $Z[1]$ whenever
$Y[1]=Z[1]$. Moreover, $\mathcal{A}^{X,Z}$ is a product of $\mathcal{A}^{X,Y}$
and $\mathcal{A}^{Y,Z}$ because each alignment starts with $(1,1)$ and since
$\mathcal{A}^{X^{\prime},Z^{\prime}}$ is a product of
$\mathcal{A}^{X^{\prime},Y^{\prime}}$ and
$\mathcal{A}^{Y^{\prime},Z^{\prime}}$. ∎

Assume that we are given three strings $X,Y,Z$. Let $d=\mathsf{ed}(X,Y)+2k$,
and define $\mathcal{G}_{X}=\mathsf{GR}_{d}(X,Y)$ and
$\mathcal{G}_{Z}=\mathsf{GR}_{d}(Y,Z)$. We show that given $\mathcal{G}_{X}$
and $\mathcal{G}_{Z}$, we can compute an optimal alignment between $X$ and $Z$
efficiently if its cost is at most $k$. Let $M=\\{(x,z):\exists y\text{ such
that }(x,y)\in\mathcal{M}_{d}(X,Y)\text{ and
}(y,z)\in\mathcal{M}_{d}(Y,Z)\\}$.

######  Lemma 5.23.

If $\mathsf{ed}(X,Z)\leq k$, then $M\subseteq\mathcal{M}_{k}(X,Z)$.

###### Proof.

Suppose that $(x,y)\in\mathcal{M}_{d}(X,Y)$ and
$(y,z)\in\mathcal{M}_{d}(Y,Z)$. For a proof by contradiction, suppose that
$X[x]\not\sim_{\mathcal{A}}Z[z]$ for some
$\mathcal{A}\in\mathsf{GA}_{k}(X,Z)$. Then, there exists
$(x^{\prime},z^{\prime})\in\mathcal{A}$ such that either $x^{\prime}\leq x$
and $z^{\prime}>z$, or $x^{\prime}>x$ and $z^{\prime}\leq z$. By symmetry,
without loss of generality, we consider the first alternative. By Lemma 3.13,
$\mathcal{A}$ is a product $\mathcal{A}^{X,Y}\in\mathsf{GA}_{d}(X,Y)$ and
$\mathcal{A}^{Y,Z}\in\mathsf{GA}_{d}(Y,Z)$. According to Definition 3.12, this
means that there exists $y^{\prime}$ such that
$(x^{\prime},y^{\prime})\in\mathcal{A}^{X,Y}$ and
$(y^{\prime},z^{\prime})\in\mathcal{A}^{Y,Z}$. If $y^{\prime}\leq y$, then
$(y,z),(y^{\prime},z^{\prime})\in\mathcal{A}^{Y,Z}$ implies that
$\mathcal{A}^{Y,Z}$ deletes $Z[z]$, contradicting
$(y,z)\in\mathcal{M}(\mathcal{A}^{Y,Z})$. Similarly, if $y^{\prime}>y$, then
$(x,y),(x^{\prime},y^{\prime})\in\mathcal{A}^{X,Y}$ implies that
$\mathcal{A}^{X,Y}$ deletes $Y[y]$, contradicting
$(x,y)\in\mathcal{M}(\mathcal{A}^{X,Y})$. This completes the proof that
$X[x]\sim_{\mathcal{A}}Z[z]$ for every $\mathcal{A}\in\mathsf{GA}_{k}(X,Z)$.
Due to $X[x]=Y[y]=Z[z]$, we also have $X[x]\simeq_{\mathcal{A}}Z[z]$ for every
$\mathcal{A}\in\mathsf{GA}_{k}(X,Z)$, i.e., $(x,y)\in\mathcal{M}_{k}(X,Z)$
holds as claimed. ∎

######  Lemma 5.24.

If $\mathsf{ed}(X,Y)=\mathcal{O}(k)$ and
$\mathcal{G}_{X},\mathcal{G}_{Z}\neq\bot$, $\mathsf{E}^{M}(X,Z)$ can be
computed in $\tilde{\mathcal{O}}(k^{3})$ time and $\tilde{\mathcal{O}}(k^{2})$
space.

###### Proof.

Let us first explain how $X^{M}$ can be constructed. Consider a position
$x\in[1\mathinner{.\,.\allowbreak}|X|]$ such that $(x,z)\notin M$ for every
$z\in[1\mathinner{.\,.\allowbreak}|Z|]$. If
$X^{\mathcal{M}_{d}(X,Y)}[x]\neq\\#$, then
$X^{M}[x]=X[x]=X^{\mathcal{M}_{d}(X,Y)}[x]$. Otherwise,
$(x,y)\in\mathcal{M}_{d}(X,Y)$ for some
$y\in[1\mathinner{.\,.\allowbreak}|Y|]$. By Lemma 5.23, we have
$(y,z)\notin\mathcal{M}_{d}(Y,Z)$ for every
$z\in[1\mathinner{.\,.\allowbreak}|Z|]$. Hence,
$Y^{\mathcal{M}_{d}(Y,Z)}[y]\neq\\#$, and we have
$X[x]=Y[y]=Y^{\mathcal{M}_{d}(Y,Z)}[y]$. In words, non-dummy characters of
$X^{M}$ can be retrieved from non-dummy characters of
$X^{\mathcal{M}_{d}(X,Y)}$ and non-dummy characters of
$Y^{\mathcal{M}_{d}(Y,Z)}$.

Thus, for each dummy segment $[\ell\mathinner{.\,.\allowbreak}r)$ in
$X^{\mathcal{M}_{d}(X,Y)}$ and its counterpart
$[\ell^{\prime}\mathinner{.\,.\allowbreak}r^{\prime})$ in
$Y^{\mathcal{M}_{d}(X,Y)}$, we need to set
$X^{M}[\ell\mathinner{.\,.\allowbreak}r):=Y^{\mathcal{M}_{d}(Y,Z)}[\ell^{\prime}\mathinner{.\,.\allowbreak}r^{\prime})$.
Such a copy-paste operation can be implemented using Proposition 4.2(g)(i), in
$\mathcal{O}(k^{2}\log^{4}n)$ time per dummy segment. We can also keep track
of the dummy segments in $X^{M}$ within the same procedure. The algorithm for
$Z^{M}$ is symmetric, and thus we can construct $\mathsf{D}(X^{M}Z^{M})$ along
with the dummy segments in $\tilde{\mathcal{O}}(k^{3})$ time and
$\tilde{\mathcal{O}}(k^{2})$ space. Finally, we build
$\mathsf{RS}_{\\#}(X^{M})$ and $\mathsf{RS}_{\\#}(Z^{M})$ in $\mathcal{O}(k)$
time. ∎

######  Corollary 5.25.

Given $\mathcal{G}_{X}$ and $\mathcal{G}_{Z}$. If
$\mathsf{ed}(X,Y)=\mathcal{O}(k)$, then we can compute
$\min(k+1,\mathsf{ed}(X,Z))$ in $\tilde{\mathcal{O}}(k^{3})$ time and
$\tilde{\mathcal{O}}(k^{2})$ space.

###### Proof.

If $\mathcal{G}_{X}$ or $\mathcal{G}_{Z}$ equals to $\bot$, then
$\mathsf{ed}(X,Z)>k$ by Lemma 3.13. Otherwise, construct $\mathsf{E}^{M}(X,Z)$
using Lemma 5.24. Finally, we pass $k$ and $\mathsf{E}^{M}(X,Z)$ to the
algorithm of Corollary 5.5, and we return the resulting value $d$.

Note that $M$ is a non-crossing matching of $X,Z$, so $d=k+1$ is correctly
returned if $\mathsf{ed}(X,Z)>k$. If $\mathsf{ed}(X,Z)\leq k$, then Lemma 5.23
implies $M\subseteq\mathcal{M}_{k}(X,Z)$, and thus $d=\mathsf{ed}(X,Z)$ holds
as claimed.

The overall runtime and space complexity are dominated by the procedure of
Lemma 5.24. ∎

######  Remark 5.26.

Using Proposition 5.12 instead of Corollary 5.5, we could construct
$\mathsf{GR}_{k}(X,Z)$.

######  Corollary 5.27.

Consider three strings $X,Y,Z$. Let $d=\mathsf{ed}(X,Y)+2k$, and assume that
we are given $\mathsf{qGR}_{d}(X,Y)$ and $\mathsf{qGR}_{d}(Y,Z)$. If
$\mathsf{ed}(X,Y)=\mathcal{O}(k)$, then we can compute
$\min(k+1,\mathsf{ed}(X,Z))$ in $\tilde{\mathcal{O}}(k^{3})$ time and
$\tilde{\mathcal{O}}(k^{2})$ space.

###### Proof.

We compute $\mathcal{G}_{X}=\mathsf{GR}_{d+1}(\$_{1}X,\$_{2}Y)$ and
$\mathsf{qGR}_{d+1}(\$_{2}Y,\$_{3}Z)$ in $\tilde{\mathcal{O}}(k^{2})$ time and
space via Corollary 5.17, and apply Corollary 5.25 to compute
$\min(k+2,\mathsf{ed}(\$_{1}X,\$_{2}Z))-1=\min(k+1,\mathsf{ed}(X,Z))$ in
$\tilde{\mathcal{O}}(k^{3})$ time and $\tilde{\mathcal{O}}(k^{2})$ space. ∎

##  6 Edit Distance Sketches

###  6.1 CGK embedding

In this section, we prove Proposition 3.16 based on the CGK embedding
introduced in [10]. Recall that the Hamming distance between the embeddings of
two strings $X,Y\in\Sigma^{\leq n}$ is bounded in terms of the edit distance
$\mathsf{ed}(X,Y)$, which allows using Hamming distance sketches to
approximate edit distance.

######  Definition 6.1 (CGK embedding [10]).

Consider an alphabet $\Sigma$, a sentinel character $\bot\notin\Sigma$, and a
2-independent family $\mathcal{H}$ of hash functions $h:\Sigma\to\\{0,1\\}$.
For an integer $n\in\mathbb{Z}_{+}$, a (uniformly random) sequence
$R\in\mathcal{H}^{3n}$, and a string $S\in\Sigma^{\leq n}$, the _CGK walk_
$W_{\mathsf{CGK}}(S)=(s_{t})_{t=1}^{3n+1}$ and the _CGK embedding_
$\mathsf{CGK}(S)\in(\Sigma\cup\\{\bot\\})^{3n}$ are defined by the following
algorithm:

Input: An integer $n\in\mathbb{Z}_{+}$, a string $S\in\Sigma^{\leq n}$.

Randomness: A sequence $R\in\mathcal{H}^{3n}$ of 2-independent hash functions
$\Sigma\to\\{0,1\\}$.

Output: The CGK walk $W_{\mathsf{CGK}}(S)=(s_{t})_{t=1}^{3n+1}$ and the CGK
embedding $\mathsf{CGK}(S)$.

1 $s_{1}:=1$;

2 for  _$t:=1$ to $3n$_ do

3 if  _$s_{t}\leq|S|$_ then

4 $\mathsf{CGK}(S)[t]:=S[s_{t}]$;

5 $s_{t+1}:=s_{t}+R_{t}(S[s_{t}])$;

6

7 else

8 $\mathsf{CGK}(S)[t]:=\bot$;

9 $s_{t+1}:=s_{t}$;

10

11

Algorithm 2 The CGK algorithm

Recall from Definition 3.14 that an $m$-step walk over $S$ is complete if
$s_{m+1}=|S|+1$.

######  Fact 6.2 ([10, Theorem 4.1]).

Each $S\in\Sigma^{\leq n}$ satisfies $\Pr_{R}[W_{\mathsf{CGK}}(S)\text{ is
complete}]\geq 1-e^{-\Omega(n)}$.

The following result summarizes the central property of the CGK embedding.

######  Fact 6.3 ([10, Theorem 4.3]).

For every $X,Y\in\Sigma^{\leq n}$ and every constant $c>0$, the embeddings
$\mathsf{CGK}(X)$, $\mathsf{CGK}(Y)$ satisfy
$\Pr_{R\in\mathcal{H}^{3n}}[\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))>c\cdot\mathsf{ed}(X,Y)^{2}]<\frac{12}{\sqrt{c}}$.

If $W_{\mathsf{CGK}}(X)$ and $W_{\mathsf{CGK}}(Y)$ are complete, Definition
3.15 yields an edit-distance alignment of $X,Y$, which we call the _CGK
alignment_ of $X,Y$. that they induce an edit-distance alignment

######  Fact 6.4 (see also [10, Theorem 4.2]).

If $W_{\mathsf{CGK}}(X)$ and $W_{\mathsf{CGK}}(Y)$ are complete for some
$X,Y\in\Sigma^{\leq n}$ and $R\in\mathcal{H}^{3n}$, then the CGK alignment of
$X,Y$ belongs to
$\mathsf{GA}_{\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))}(X,Y)$.

###### Proof.

Let $\mathcal{A}$ be the CGK alignment of $X,Y$, i.e., the zip alignment of
$W_{\mathsf{CGK}}(X)=(x_{t})_{t=1}^{3n+1}$ and
$W_{\mathsf{CGK}}(Y)=(y_{t})_{t=1}^{3n+1}$. Consider
$(x_{t},y_{t})\in\mathcal{B}(\mathcal{A})$, with
$t\in[1\mathinner{.\,.\allowbreak}3n+1]$ chosen so that $t=3n+1$ or
$(x_{t+1},y_{t+1})\neq(x_{t},y_{t})$. If $t=3n+1$, then
$(x_{t},y_{t})=(|X|+1,|Y|+1)$ by the assumption that $W_{\mathsf{CGK}}(X)$ and
$W_{\mathsf{CGK}}(Y)$ are complete. If $(x_{t+1},y_{t+1})=(x_{t}+1,y_{t}+1)$,
then we have $\mathsf{CGK}(X)[t]=X[x_{t}]\neq Y[y_{t}]=\mathsf{CGK}(Y)[t]$.
The remaining possibility $x_{t+1}-x_{t}\neq y_{t+1}-y_{t}$ holds only in the
following three cases: if $x_{t}=|X|+1$ and $y_{t}\leq|Y|$ (when
$\mathsf{CGK}(X)[t]=\bot\neq\mathsf{CGK}(Y)[t]=Y[y_{t}]$), if $x_{t}\leq|X|$
and $y_{t}=|Y|+1$ (when
$X[x_{t}]=\mathsf{CGK}(X)[t]\neq\bot=\mathsf{CGK}(Y)[t]$), or if
$x_{t}\leq|X|$, $y_{t}\leq|Y|$, and $R_{t}(X[x_{t}])\neq R_{t}(Y[y_{t}])$
(when $\mathsf{CGK}(X)[t]=X[x_{t}]\neq Y[y_{t}]=\mathsf{CGK}(Y)[t]$). Overall,
we have $X[x_{t}]\neq Y[y_{t}]$ whenever
$(x_{t},y_{t})\in[1\mathinner{.\,.\allowbreak}|X|]\times[1\mathinner{.\,.\allowbreak}|Y|]$,
and $\mathsf{CGK}(X)[t]\neq\mathsf{CGK}(Y)[t]$ whenever
$t\in[1\mathinner{.\,.\allowbreak}3n]$. Consequently,
$\mathcal{A}\in\mathsf{GA}_{\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))}(X,Y)$.
∎

The final property of the CGK alignment required in this work is that its
width is within $\mathcal{O}(\mathsf{ed}(X,Y))$ with good probability. For
this, we first prove a fact about random walks:

######  Fact 6.5.

Let $(w_{i})_{i\geq 0}$ be an unbiased lazy random walk (that is, $w_{0}=0$,
and, for every $i\geq 1$, we have $\Pr[w_{i+1}=w_{i}\mid
w_{0},\ldots,w_{i}]=\frac{1}{2}$, $\Pr[w_{i+1}=w_{i}+1\mid
w_{0},\ldots,w_{i}]=\Pr[w_{i+1}=w_{i}-1\mid w_{0},\ldots,w_{i}]=\frac{1}{4}$).
Then, for every $m,\ell\in\mathbb{Z}_{+}$, we have
$\Pr[\max_{i=0}^{m}|w_{i}|\geq\ell]\leq\frac{m}{\ell^{2}}$.

###### Proof.

By the reflection principle [44, Excercise 2.10], we have
$\Pr[\max_{i=0}^{m}|w_{i}|\geq\ell]\leq
2\Pr[|w_{m}|\geq\ell]=2\Pr[w_{m}^{2}\geq\ell^{2}]$. By Markov’s inequality,

$2\Pr[w_{m}^{2}\geq\ell^{2}]\leq\frac{2\mathbb{E}[w_{m}^{2}]}{\ell^{2}}=\frac{2\mathbb{E}[(w_{1}-w_{0})^{2}+\cdots+(w_{m}-w_{m-1})^{2}]}{\ell^{2}}=\frac{m}{\ell^{2}}.\qed$

######  Corollary 6.6.

For every constant $\delta\in(0,1)$, there exists a constant $c$ such that for
sufficiently large $n$, all strings $X,Y\in\Sigma^{\leq n}$, and their CGK
alignment $\mathcal{A}$, the probability over $R\in\mathcal{H}^{3n}$ that
$W_{\mathsf{CGK}}(X),W_{\mathsf{CGK}}(Y)\text{ are complete,
}\mathcal{A}\in\mathsf{GA}_{c\cdot\mathsf{ed}(X,Y)^{2}}(X,Y)\text{, and
}0pt(\mathcal{A})\leq c\cdot\mathsf{ed}(X,Y)$ is at least $1-\delta$.

###### Proof.

By Fact 6.2, $\Pr[W_{\mathsf{CGK}}(S)\text{ is
incomplete}]\leq\frac{\delta}{4}$ holds for every $S\in\Sigma^{\leq n}$ and
sufficiently large $n=\Omega(\log\frac{1}{\delta})$. By Fact 6.3, there is a
constant $c$ such that
$\Pr[\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))>c\cdot\mathsf{ed}(X,Y)^{2}]\leq\frac{\delta}{4}$.
We may take arbitrarily large $c$, so we shall also assume that
$c\geq\frac{4}{\delta}$. Moreover, by Fact 6.4, if $W_{\mathsf{CGK}}(X)$ and
$W_{\mathsf{CGK}}(Y)$ are complete and
$\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))\leq c\cdot\mathsf{ed}(X,Y)^{2}$,
then $\mathcal{A}\in\mathsf{GA}_{c\cdot\mathsf{ed}(X,Y)^{2}}(X,Y)$.

To bound $0pt(\mathcal{A})$, let us analyze the CGK walks
$W_{\mathsf{CGK}}(X)=(x_{t})_{t=1}^{3n+1}$ and
$W_{\mathsf{CGK}}(Y)=(y_{t})_{t=1}^{3n+1}$. Let $T$ be the first step such
that $x_{T}=|X|+1$, $y_{T}=|Y|+1$, or $T=3n+1$. Note that it suffices to bound
$\Pr[\max_{t=1}^{T}|x_{t}-y_{t}|\geq ck]$, where $k=\mathsf{ed}(X,Y)$.

Let $A=\\{1\\}\cup\\{t+1:t\in[1\mathinner{.\,.\allowbreak}T)\text{ and
}X[x_{t}]\neq Y[y_{t}]\\}$. Observe that $x_{t}-y_{t}=x_{t-1}-y_{t-1}$ holds
for $t\in[1\mathinner{.\,.\allowbreak}T]\setminus A$, so we may focus on
bounding $\Pr[\max_{t\in A}|x_{t}-y_{t}|\geq ck]$. Let
$A=\\{t_{0},\ldots,t_{a}\\}$ with $t_{0}<\cdots<t_{a}$, and let
$d_{i}=x_{t_{i}}-y_{t_{i}}$ for $i\in[0\mathinner{.\,.\allowbreak}a]$. Observe
that $(d_{i})_{i=0}^{a}$ is an $a$-step unbiased lazy random walk and that
$a\leq\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))$. Moreover, if we extend
$(d_{i})_{i=0}^{a}$ to an infinite unbiased lazy random walk
$(d_{i})_{i=0}^{\infty}$, then Fact 6.5 yields $\Pr[\max_{i=0}^{\lfloor
ck^{2}\rfloor}|d_{i}|\geq
ck]\leq\frac{ck^{2}}{c^{2}k^{2}}=\frac{1}{c}\leq\frac{\delta}{4}$. Therefore,

$\Pr\left[\max_{i=0}^{a}|d_{i}|\geq
ck\right]\leq\Pr\left[\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))>ck^{2}\right]+\Pr\left[{\max_{i=0}^{\lfloor
ck^{2}\rfloor}|d_{i}|\geq ck}\right].$

Consequently, if $\mathsf{CGK}(X)$ and $\mathsf{CGK}(Y)$ are complete,
$\mathsf{hd}(\mathsf{CGK}(X),\mathsf{CGK}(Y))\leq ck^{2}$, and the random walk
satisfies $\Pr\big{[}{\max_{i=0}^{\lfloor ck^{2}\rfloor}|d_{i}|<ck}\big{]}$,
then the alignment $\mathcal{A}$ satisfies the lemma. The total probability of
the complementary events is at most $\delta$, so this completes the proof. ∎

To complete the proof of Proposition 3.16 (repeated below), it remains to
reduce the number of random bits using Nisan’s pseudorandom generator [50].

See 3.16

###### Proof.

Let $c_{\ref{cor:CGK}}$ and $n_{\ref{cor:CGK}}$ be the constant and threshold
(respectively) of Corollary 6.6 for $\delta_{\ref{cor:CGK}}=\frac{\delta}{2}$.

If $n<\max(\frac{10}{\delta},n_{\ref{cor:CGK}})$, we set
$\mathsf{W}(n,r,S)=(\min(t,|S|+1))_{t=1}^{3n+1}$ for all $S\in\Sigma^{\leq n}$
so that $\mathsf{W}(n,r,S)$ is trivially a $3n$-step complete walk over $S$.
Now, consider strings $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)$.
Observe that $\mathcal{A}_{\mathsf{W}}\in\mathsf{GA}_{0}(X,Y)$ if $X=Y$ and
$\mathcal{A}_{\mathsf{W}}\in\mathsf{GA}_{n}(X,Y)$ otherwise. Moreover,
$0pt(\mathcal{A}_{\mathsf{W}})=\big{|}|X|-|Y|\big{|}\leq\mathsf{ed}(X,Y)$.
Consequently, the claimed conditions are (deterministically) satisfied for
$c\geq n_{\ref{cor:CGK}}$. The construction algorithm uses $\mathcal{O}(\log
n)$ bits and $\mathcal{O}(n)$ time.

If $n\geq\max(\frac{10}{\delta},n_{\ref{cor:CGK}})$, we first develop an
algorithm $\mathsf{W}^{\prime}$ that uses $\Theta(n\log\sigma)$ random bits,
interpreted as a sequence $R\in\mathcal{H}^{3n}$. Specifically, each hash
function $R_{t}$ is specified by an $\lceil\log\sigma\rceil$-bit integer
$h_{t}$ so that $R_{t}(a)$ counts (modulo 2) the set bits in $a\textsf{ xor
}h_{t}$.

We set $\mathsf{W}^{\prime}(n,R,S)=(\max(t-3n+|S|,s_{t}))_{t=1}^{3n+1}$ based
on the CGK walk $W_{\mathsf{CGK}}(S)=(s_{t})_{t=1}^{3n+1}$ for all
$S\in\Sigma^{\leq n}$. Observe that this modification guarantees that
$\mathsf{W}^{\prime}(n,R,S)$ is a complete walk over $S$ and that
$\mathsf{W}^{\prime}(n,R,S)=W_{\mathsf{CGK}}(S)$ if $W_{\mathsf{CGK}}(S)$ is
already complete. Consequently, by Corollary 6.6, the claimed conditions are
satisfied with probability at least
$1-\delta_{\ref{cor:CGK}}=1-\frac{\delta}{2}$ for $c\geq c_{\ref{cor:CGK}}$.
The construction algorithm uses $\mathcal{O}(\log n)$ bits, costs
$\mathcal{O}(n)$ time, reads the random bits $(h_{t})_{t=1}^{3n+1}$ from left
to right, and outputs the elements of $\mathsf{W}^{\prime}(n,R,S)$ when
required.

In order to use Nisan’s pseudorandom generator [50], we need to argue that we
only care about properties testable using $\mathcal{O}(\log n)$-bit algorithms
with one-way access to the randomness $R$. As in [10], our testers are given
two (read-only) strings $X,Y\in\Sigma^{\leq n}$ and a stream of random bits
representing $R$ (the sequence $(h_{t})_{t=1}^{3n}$). Observe that the
following properties of the zip alignment $\mathcal{A}^{\prime}$ of
$\mathsf{W}^{\prime}(n,R,X)=(x_{t})_{t=1}^{3n+1}$ and
$\mathsf{W}^{\prime}(n,R,Y)=(y_{t})_{t=1}^{3n+1}$ are testable in
$\mathcal{O}(\log n)$ bits and $\mathcal{O}(n)$ time:

  * •

whether $\mathcal{A}^{\prime}$ is greedy;

  * •

whether $\mathsf{cost}(\mathcal{A}^{\prime})\leq k$ for a given integer
$k\in[0\mathinner{.\,.\allowbreak}n]$;

  * •

whether $0pt(\mathcal{A}^{\prime})\leq w$ for a given integer
$w\in[0\mathinner{.\,.\allowbreak}n]$.

All these testers simply construct triples $(t,x_{t},y_{t})$ for subsequent
$t\in[1\mathinner{.\,.\allowbreak}3n+1]$.

In this setting, Nisan’s pseudorandom generator [50], given a sequence $r$ of
$\mathcal{O}(\log^{2}n)$ random bits, constructs a sequence $\mathsf{PRG}(r)$
of pseudorandom bits in $\mathcal{O}(1)$ amortized time per bit, using
$\mathcal{O}(\log^{2}n)$ bits of working space. Moreover, for every tester,
the probabilities of accepting a given input $\mathcal{I}$ with randomness $R$
and $\mathsf{PRG}(r)$ differ by at most $\frac{1}{n^{2}}$ [10, Theorem 5].
Consequently, setting
$\mathsf{W}(n,r,S)=\mathsf{W}^{\prime}(n,\mathsf{PRG}(r),S)$, we can guarantee
that the claimed condition is satisfied with probability at least
$1-\frac{1}{2}\delta-\frac{(2n+3)}{n^{2}}\geq 1-\delta$. The streaming
construction algorithm takes $\mathcal{O}(\log^{2}n)$ bits and
$\mathcal{O}(n\log n)$ time, dominated by the generation of $\mathsf{PRG}(r)$.
∎

###  6.2 Context encoding

For a string $S\in\Sigma^{*}$, define
$\overline{\mathsf{maxLZ}}(S)=\max_{[\ell\mathinner{.\,.\allowbreak}r)\subseteq[1\mathinner{.\,.\allowbreak}|S|]}|\mathsf{LZ}(\overline{S[\ell\mathinner{.\,.\allowbreak}r)})|$.

######  Observation 6.7.

Consider a string $S\in\Sigma^{*}$ and an integer $k\in\mathbb{Z}_{+}$. If
$\overline{\mathsf{maxLZ}}(S[\ell\mathinner{.\,.\allowbreak}r))\leq k$ holds
for a non-empty fragment $S[\ell\mathinner{.\,.\allowbreak}r)$, then:

  1. (a)

$\overline{\mathsf{maxLZ}}(S[\ell\mathinner{.\,.\allowbreak}r])\leq k$ if and
only if $\mathsf{LZ}(\overline{S[\ell\mathinner{.\,.\allowbreak}r]})\leq k$;

  2. (b)

$\overline{\mathsf{maxLZ}}(S[\ell+1\mathinner{.\,.\allowbreak}r))\leq k$;

  3. (c)

$\overline{\mathsf{maxLZ}}(S[\ell\mathinner{.\,.\allowbreak}r])\leq k+1$.

###### Proof.

The first two parts follow from the fact that the size of the
$\mathsf{LZ}$-factorisation of a prefix of a string is bounded by the size of
the $\mathsf{LZ}$-factorisation of the string itself. The third claim follows
from the optimality of the LZ77 parsing among all LZ-like parsings (4.1). ∎

######  Definition 6.8 ((Double) Context).

Consider a string $S\in\Sigma^{*}$ and an integer $k\in\mathbb{Z}_{+}$. For a
position $p\in[1\mathinner{.\,.\allowbreak}|S|]$, we define the _context_
$C_{k}(S,p)$ as the longest prefix $S[p\mathinner{.\,.\allowbreak}q)$ of
$S[p\mathinner{.\,.\allowbreak}|S|]$ such that
$\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}q))\leq k$ and the
_double context_ $C^{2}_{k}(S,p)$ as the longest prefix
$S[p\mathinner{.\,.\allowbreak}q)$ of $S[p\mathinner{.\,.\allowbreak}|S|]$
such that $\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}r))\leq k$
and $\overline{\mathsf{maxLZ}}(S[r\mathinner{.\,.\allowbreak}q))\leq k$ for
some $r\in[p\mathinner{.\,.\allowbreak}q]$.

For integers $t<v$, let $\mu(t,v)$ denote the integer
$w\in[t\mathinner{.\,.\allowbreak}v)$ divisible by the largest power of 2.

Input: An integer $k\in\mathbb{Z}_{\geq 0}$, a string $S\in\Sigma^{*}$, and a
complete walk $(s_{t})_{t=1}^{m+1}$ over $S$.

Output: The string $\mathsf{CE}_{k}(W)[1\mathinner{.\,.\allowbreak}m]$.

1 $\mathsf{CE}_{k}(W):=\bot^{m}$, where $\bot=(\mathsf{LZ}(\varepsilon),0)$;

2 $s_{0}:=0;\;\mu_{0}:=0;\;u:=0$;

3 for  _$t:=1$ to $m$_ do

4 if  _$s_{t}\leq|S|$_ then

5
$\mu_{t}:=\mu(t,\min\\{v\in[1\mathinner{.\,.\allowbreak}m+1]:s_{v}=s_{t}+|C_{k}(S,s_{t})|\\})$;

6 if  _$\mu_{t} >\mu_{t-1}$_ then

7
$\mathsf{CE}_{k}(W)[t]:=\left(\mathsf{LZ}\left(\overline{C^{2}_{k}(S,s_{t})}\right),s_{t}-s_{u}\right)$;

8 $u:=t$;

9

10

11

12 return _$\mathsf{CE}_{k}(W)$_ ;

Algorithm 3 Function $\mathsf{CE}$

We say that a position $S[s]$ is covered by a fragment
$S[\ell\mathinner{.\,.\allowbreak}r)$ if $\ell\leq s<r$.

######  Lemma 6.9.

Consider $\mathsf{CE}_{k}(W)$ constructed for an integer $k\in\mathbb{Z}_{\geq
0}$ and an $m$-complete walk $W=(s_{t})_{t=1}^{m+1}$ over $S\in\Sigma^{*}$.
Each position $s\in[1\mathinner{.\,.\allowbreak}|S|]$ satisfies

$1\leq|\\{t\in[1\mathinner{.\,.\allowbreak}m]:\mathsf{CE}_{k}(W)[t]\neq\bot\text{
and }C_{k}(S,s_{t})\text{ covers }S[s]\\}|\leq\\\
\leq|\\{t\in[1\mathinner{.\,.\allowbreak}m]:\mathsf{CE}_{k}(W)[t]\neq\bot\text{
and }C^{2}_{k}(S,s_{t})\text{ covers }S[s]\\}|\leq\mathcal{O}(\log m)$

###### Proof.

Let us first bound the covering number from below. Consider an index
$t\in[1\mathinner{.\,.\allowbreak}m]$ such that $s=s_{t}$, and let
$t^{\prime}\in[1\mathinner{.\,.\allowbreak}m]$ be the smallest index such that
$\mu_{t^{\prime}}=\mu_{t}$. Note that
$s_{\mu_{t^{\prime}}}<s_{t^{\prime}}+|C_{k}(S,s_{t^{\prime}})|$ and
$s_{\mu_{t}}\geq s_{t}$ by definition of $\mu$ and monotonicity of the walk
$W$. Due to $\mu_{t^{\prime}}=\mu_{t}$, this implies $s_{t^{\prime}}\leq
s_{t}<s_{t^{\prime}}+|C_{k}(S,s_{t^{\prime}})|$, i.e., that $S[s_{t}]$ is
covered by $C_{k}(S,s_{t^{\prime}})$. Due to $\mu_{t^{\prime}-1}\neq\mu_{t}$,
this guarantees $\mathsf{CE}_{k}(S)[t^{\prime}]\neq\bot$.

As for the upper bound, note that the indexes
$t\in[1\mathinner{.\,.\allowbreak}m]$ with $\mathsf{CE}_{k}(S)[t]\neq\bot$
have distinct values $\mu_{t}$. Let us further classify them into
$\mathcal{O}(\log n)$ groups depending on the largest power of two dividing
$\mu_{t}$. Consider two indexes $t<t^{\prime}$ in the same group. Since
$\mu_{t}<\mu_{t^{\prime}}$ are divisible by the same largest power of two,
there is a number $\nu\in(\mu_{t}\mathinner{.\,.\allowbreak}\mu_{t^{\prime}})$
divisible by a strictly larger power of two. By definition of $\mu_{t}$, we
have $s_{\nu}\geq s_{t}+|C_{k}(S,s_{t})|$ and, by definition of
$\mu_{t^{\prime}}$, we have $s_{\nu}<s_{t^{\prime}}$. Consequently,
$s_{t^{\prime}}>s_{t}+|C_{k}(S,s_{t})|$, i.e., the contexts $C_{k}(S,s_{t})$
and $C_{k}(S,s_{t^{\prime}})$ are disjoint. By monotonicity of
$\overline{\mathsf{maxLZ}}$, this also means that
$s_{t}+|C^{2}_{k}(S,s_{t})|\leq s_{t^{\prime}}+|C_{k}(S,s_{t^{\prime}})|$. In
particular, each position $s\in[1\mathinner{.\,.\allowbreak}|S|]$ is covered
by at most one context $C_{k}(S,s_{t})$ and at most two double contexts
$C^{2}_{k}(S,s_{t})$ for $t\in[1\mathinner{.\,.\allowbreak}m]$ belonging to a
single group. ∎

Let $\mathcal{A}$ be an alignment between $X,Y\in\Sigma^{*}$. We define
$\mathcal{B}_{X}(\mathcal{A})=\\{x:(x,y)\in\mathcal{B}(\mathcal{A})\\}\cap[1\mathinner{.\,.\allowbreak}|X|]$.
Moreover, for two alignments $\mathcal{A},\mathcal{A}^{\prime}$ between
$X,Y\in\Sigma^{*}$, we define $\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})$
to contain $x\in[1\mathinner{.\,.\allowbreak}|X|]$ unless
$(x,y)\in\mathcal{M}(\mathcal{A})\cap\mathcal{M}(\mathcal{A}^{\prime})$ for
some $y\in[1\mathinner{.\,.\allowbreak}|Y|]$.

######  Lemma 6.10.

Let $b\in\mathbb{Z}_{+}$ and $\mathcal{A},\mathcal{A}^{\prime}$ be greedy
alignments of strings $X$ and $Y$. The positions in
$\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})$ can be covered by at most
$\mathsf{cost}(\mathcal{A})+\frac{1}{b}\mathsf{cost}(\mathcal{A}^{\prime})$
contexts $C_{0pt(\mathcal{A})+0pt(\mathcal{A}^{\prime})+2b}(X,\cdot)$.

Moreover, if $b>\mathsf{cost}(\mathcal{A}^{\prime})$, then the positions in
$\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})$ can be covered by contexts
$C_{0pt(\mathcal{A})+0pt(\mathcal{A}^{\prime})+2b}(X,x)$ with
$x\in\mathcal{B}_{X}(\mathcal{A})$.

###### Proof.

Let $w=0pt(\mathcal{A})$ and $w^{\prime}=0pt(\mathcal{A}^{\prime})$. Without
loss of generality, we may trim the longest common prefix of $X$ and $Y$; this
is feasible because both $\mathcal{A}$ and $\mathcal{A}^{\prime}$ match the
common prefix, so $\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})$ only contains
positions following the prefix. Moreover, we assume that $X\neq\varepsilon$;
otherwise $\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})=\emptyset$ and the
lemma is trivial.

In the remaining case, we are guaranteed that
$1\in\mathcal{B}_{X}(\mathcal{A})$. Let
$\mathcal{B}_{X}(\mathcal{A})=\\{x_{1},\ldots,x_{m}\\}$, where
$1=x_{1}<\cdots<x_{m}$, and let $x_{m+1}=|X|+1$. This yields a decomposition
$X=X_{1}\cdots X_{m}$ into $m$ non-empty substrings
$X_{i}:=X[x_{i}\mathinner{.\,.\allowbreak}x_{i+1})$. The alignment
$\mathcal{A}^{\prime}$ further yields a decomposition $Y=Y_{1}\cdots Y_{m}$
into $m$ (possibly empty) substrings
$Y_{i}:=Y[y_{i}\mathinner{.\,.\allowbreak}y_{i+1})$ so that
$X_{i}\sim_{\mathcal{A}^{\prime}}Y_{i}$ and $|x_{i}-y_{i}|\leq w^{\prime}$ for
$i\in[1\mathinner{.\,.\allowbreak}m]$. Moreover, the cost of
$\mathcal{A}^{\prime}$ can be expressed as
$\mathsf{cost}(\mathcal{A}^{\prime})=\sum_{i=1}^{m}c^{\prime}_{i}$, where
$c^{\prime}_{i}$ denotes the cost of $\mathcal{A}^{\prime}$ restricted to
$X_{i}$ and $Y_{i}$.

######  Claim 6.11.

For every $i\in[1\mathinner{.\,.\allowbreak}m]$, the set
$\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})\cap[x_{i}\mathinner{.\,.\allowbreak}x_{i+1})$
can be covered by at most $\lceil\frac{1}{b}(c^{\prime}_{i}+1)\rceil$ contexts
$C_{w+w^{\prime}+2b}(X,\cdot)$ including $C_{w+w^{\prime}+2b}(X,x_{i})$.

###### Proof.

Let
$q_{i}=\max(\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})\cap[x_{i}\mathinner{.\,.\allowbreak}x_{i+1}))$.
We may assume that $q_{i}\geq x_{i}+w+w^{\prime}$; otherwise, the claim holds
trivially. We shall prove that
$X[x_{i}+1\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})]$ can be decomposed
into at most $2c^{\prime}_{i}+1$ phrases, each of which is a single character
or has another occurrence at most $w+w^{\prime}$ positions to the right.
Accounting for $X[x_{i}]$, this yields a decomposition of
$X[x_{i}\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})]$ into at most
$2c^{\prime}_{i}+2$ such phrases. The $\overline{\mathsf{maxLZ}}$ measure of
the concatenation of every $2b$ subsequent phrases and $w+w^{\prime}$
following single characters does not exceed $w+w^{\prime}+2b$. Hence,
$X[x_{i}\mathinner{.\,.\allowbreak}q_{i}]$ can be covered by
$\lceil\frac{1}{b}(c^{\prime}_{i}+1)\rceil$ contexts
$C_{w+w^{\prime}+2b}(X,\cdot)$ including $C_{w+w^{\prime}+2b}(X,x_{i})$.

Thus, it remains to construct the decomposition of
$X[x_{i}+1\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})]$ into phrases. By
definition of $\mathcal{B}_{X}(\mathcal{A})$, we have
${X[x_{i}+1\mathinner{.\,.\allowbreak}x_{i+1})\simeq_{\mathcal{A}}Y[x_{i}+1+d\mathinner{.\,.\allowbreak}x_{i+1}+d)}$
for some shift $d\in[-w\mathinner{.\,.\allowbreak}w]$. We consider two cases.

In the first case, we assume that $(x_{i}+1,\bar{y})\in\mathcal{A}^{\prime}$
holds for some $\bar{y}\geq x_{i}+1+d$. The greedy nature of
$\mathcal{A}^{\prime}$ then guarantees that if $(x,y)\in\mathcal{A}^{\prime}$
with $x\in[x_{i}+1\mathinner{.\,.\allowbreak}q_{i})$, then $y>x+d$. We
decompose $X[x_{i}+1\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})]$ (which
is contained in $X_{i}$) into maximal phrases
$X[x\mathinner{.\,.\allowbreak}x^{\prime}]$ satisfying
$X[x\mathinner{.\,.\allowbreak}x^{\prime}]\simeq_{\mathcal{A}^{\prime}}Y[x+d^{\prime}\mathinner{.\,.\allowbreak}x^{\prime}+d^{\prime}]$
for some $d^{\prime}\in(d\mathinner{.\,.\allowbreak}w^{\prime}]$ and remaining
single characters (deleted or substituted by $\mathcal{A}^{\prime}$). Observe
that this yields at most $1+c^{\prime}_{i}$ phrases and at most
$c^{\prime}_{i}$ single characters. Moreover, we have
$X[x\mathinner{.\,.\allowbreak}x^{\prime}]\simeq_{\mathcal{A}^{\prime}}Y[x+d^{\prime}\mathinner{.\,.\allowbreak}x^{\prime}+d^{\prime}]\simeq_{\mathcal{A}}X[x+(d^{\prime}-d)\mathinner{.\,.\allowbreak}x^{\prime}+(d^{\prime}-d)]$
due to $x_{i}+1\leq x\leq x+(d^{\prime}-d)$ and $x^{\prime}+(d^{\prime}-d)\leq
x^{\prime}+(w^{\prime}+w)\leq q_{i}$. Hence, each phrase
$X[x\mathinner{.\,.\allowbreak}x^{\prime}]$ has another occurrence located
$d^{\prime}-d\in[1\mathinner{.\,.\allowbreak}w+w^{\prime}]$ positions to the
right.

In the second case, we assume that $(x_{i}+1,\bar{y})\in\mathcal{A}^{\prime}$
holds for some $\bar{y}\leq x_{i}+1+d$. The greedy nature of
$\mathcal{A}^{\prime}$ then guarantees that if $(x,y)\in\mathcal{A}^{\prime}$
with $x\in[x_{i}+1\mathinner{.\,.\allowbreak}q_{i})$, then $y<x+d$. We
decompose $Y[x_{i}+1+d\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})+d]$
(which is contained in $Y_{i}$) into maximal phrases
$Y[y\mathinner{.\,.\allowbreak}y^{\prime}]$ satisfying
$Y[y\mathinner{.\,.\allowbreak}y^{\prime}]\simeq_{\mathcal{A}^{\prime}}X[y-d^{\prime}\mathinner{.\,.\allowbreak}y^{\prime}-d^{\prime}]$
for some $d^{\prime}\in[-w\mathinner{.\,.\allowbreak}d)$ and remaining single
characters (deleted or substituted by $\mathcal{A}^{\prime}$). Observe that
this yields at most $1+c^{\prime}_{i}$ phrases and at most $c^{\prime}_{i}$
single characters. Moreover, we have
$Y[y\mathinner{.\,.\allowbreak}y^{\prime}]\simeq_{\mathcal{A}^{\prime}}X[y-d^{\prime}\mathinner{.\,.\allowbreak}y^{\prime}-d^{\prime}]\simeq_{\mathcal{A}}Y[y+(d-d^{\prime})\mathinner{.\,.\allowbreak}y+(d-d^{\prime})]$
due to $x_{i}+1\leq x_{i}+1+d-d^{\prime}\leq y-d^{\prime}$ and
$y^{\prime}-d^{\prime}\leq q_{i}-(w+w^{\prime})+d-d^{\prime}\leq q_{i}$.
Hence, each phrase $Y[y\mathinner{.\,.\allowbreak}y^{\prime}]$ has another
occurrence located $d-d^{\prime}\in[1\mathinner{.\,.\allowbreak}w+w^{\prime}]$
characters to the right. Since
$Y[x_{i}+1+d\mathinner{.\,.\allowbreak}q_{i}+d]=X[x_{i}+1\mathinner{.\,.\allowbreak}q_{i}]$,
this decomposition of
$Y[x_{i}+1+d\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})+d]$ gives an
analogous decomposition of
$X[x_{i}+1\mathinner{.\,.\allowbreak}q_{i}-(w+w^{\prime})]$. ∎

The set $\Delta_{X}(\mathcal{A},\mathcal{A}^{\prime})$ can be covered by
$\sum_{i=1}^{m}\lceil\frac{1}{b}(c^{\prime}_{i}+1)\rceil\leq
m+\frac{\mathsf{cost}(\mathcal{A}^{\prime})}{b}\leq\mathsf{cost}(\mathcal{A})+\frac{\mathsf{cost}(\mathcal{A}^{\prime})}{b}$
contexts $C_{w+w^{\prime}+2b}(X,\cdot)$. If
$b\geq\mathsf{cost}(\mathcal{A}^{\prime})+1$, then the contexts starting at
positions in $\mathcal{B}_{X}(\mathcal{A})$ are sufficient. ∎

######  Lemma 6.12.

Let $\mathcal{A}_{W}$ be the zip alignment of $m$-complete walks
$W_{X}=(x_{t})_{t=1}^{m+1}$, $W_{Y}=(y_{t})_{t=1}^{m+1}$ over strings
$X,Y\in\Sigma^{*}$, and let $k^{\prime}\in\mathbb{Z}_{+}$. If
$\mathcal{A}_{W}$ is greedy, then $\mathcal{B}_{X}(\mathcal{A}_{W})\subseteq
P_{X}$, where $P_{X}$ is the set of positions
$x\in[1\mathinner{.\,.\allowbreak}|X|]$ such that $X[x]$ is covered by
$C^{2}_{k^{\prime}}(X,x_{t})$ for some $t\in[1\mathinner{.\,.\allowbreak}m]$
with
$\bot\neq\mathsf{CE}_{k^{\prime}}(W_{X})[t]\neq\mathsf{CE}_{k^{\prime}}(W_{Y})[t]$.
Moreover, for every positive integer $k\geq\mathsf{ed}(X,Y)$ such that
$k^{\prime}\geq 0pt(\mathcal{A}_{W})+5k$:

  * •

every $\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$ satisfies
$\Delta_{X}(\mathcal{A},\mathcal{A}_{W})\subseteq P_{X}$,

  * •

$\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(X),\mathsf{CE}_{k^{\prime}}(Y))\leq
c(k+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))\log m$ holds for a sufficiently
large constant $c$.

###### Proof.

Consider a position $x\in\mathcal{B}_{X}(\mathcal{A}_{W})$. By Lemma 6.9,
there is an index $t\in[1\mathinner{.\,.\allowbreak}m]$ such that
$\mathsf{CE}_{k^{\prime}}(W_{X})[t]\neq\bot$ and $C^{2}_{k^{\prime}}(X,x_{t})$
covers $X[x]$. To conclude that $x\in P_{X}$, it remains to prove
$\mathsf{CE}_{k^{\prime}}(W_{X})[t]\neq\mathsf{CE}_{k^{\prime}}(W_{Y})[t]$.
For a proof by contradiction, suppose that
$\mathsf{CE}_{k^{\prime}}(W_{X})[t]=\mathsf{CE}_{k^{\prime}}(W_{Y})[t]$. This
implies $C^{2}_{k^{\prime}}(X,x_{t})=C^{2}_{k^{\prime}}(Y,y_{t})$. Since
$\mathcal{A}_{W}$ is greedy, we derive
$X[x_{t}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|)\simeq_{\mathcal{A}_{W}}Y[y_{t}\mathinner{.\,.\allowbreak}y_{t}+|C^{2}_{k^{\prime}}(Y,y_{t})|)$,
which contradicts $x\in\mathcal{B}_{X}(\mathcal{A}_{W})$.

In the remainder of the proof, we assume that $k\geq\mathsf{ed}(X,Y)$ and
$k^{\prime}\geq 0pt(\mathcal{A}_{W})+5k$. Next, consider a greedy alignment
$\mathcal{A}$ with $\mathsf{cost}(\mathcal{A})\leq k$ and a position
$x\in\Delta_{X}(\mathcal{A},\mathcal{A}_{W})$. Due to $k^{\prime}\geq
0pt(\mathcal{A}_{W})+0pt(\mathcal{A})+4k$, Lemma 6.10 shows that there exists
a position $r\in\mathcal{B}_{X}(\mathcal{A}_{W})$ such that
$C_{k^{\prime}}(X,r)$ covers $X[x]$ and, by Lemma 6.9, there exists a position
$t\in[1\mathinner{.\,.\allowbreak}m]$ such that
$\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot$ and $C_{k^{\prime}}(X,x_{t})$ covers
$X[r-1]$. Since
$\overline{\mathsf{maxLZ}}(X[x_{t}\mathinner{.\,.\allowbreak}r)),\overline{\mathsf{maxLZ}}(X[r\mathinner{.\,.\allowbreak}x])\leq
k^{\prime}$, we conclude that both $r$ and $x$ are covered by
$C^{2}_{k^{\prime}}(X,x_{t})$. We shall prove that
$\mathsf{CE}_{k^{\prime}}(X)[t]\neq\mathsf{CE}_{k^{\prime}}(Y)[t]$. For a
proof by contradiction, suppose that
$\mathsf{CE}_{k^{\prime}}(W_{X})[t]=\mathsf{CE}_{k^{\prime}}(W_{Y})[t]$, which
implies $C^{2}_{k^{\prime}}(X,x_{t})=C^{2}_{k^{\prime}}(Y,y_{t})$. Let us fix
the smallest $t^{\prime}\in[t\mathinner{.\,.\allowbreak}m+1]$ such that
$(x_{t^{\prime}},y_{t^{\prime}})\in\mathcal{B}(\mathcal{A}_{W})$. Observe that
$X[x_{t}\mathinner{.\,.\allowbreak}x_{t^{\prime}})\simeq_{\mathcal{A}_{W}}Y[y_{t}\mathinner{.\,.\allowbreak}y_{t^{\prime}})$
and, by the greedy nature of $\mathcal{A}_{W}$,
$X[x_{t}\mathinner{.\,.\allowbreak}x_{t^{\prime}})=Y[y_{t}\mathinner{.\,.\allowbreak}y_{t^{\prime}})$
is the longest common prefix of $X[x_{t}\mathinner{.\,.\allowbreak}]$ and
$Y[y_{t}\mathinner{.\,.\allowbreak}]$. At the same time, due to
$x_{t}<r\in\mathcal{B}_{X}(\mathcal{A}_{W})$, we have $x_{t^{\prime}}\leq r$,
so $X[x_{t}\mathinner{.\,.\allowbreak}x_{t^{\prime}}]$ is a prefix of
$C^{2}_{k^{\prime}}(X,x_{t})$. However,
$X[x_{t}\mathinner{.\,.\allowbreak}x_{t^{\prime}}]$ is not a prefix
$Y[y_{t}\mathinner{.\,.\allowbreak}]$, so $C^{2}_{k^{\prime}}(X,x_{t})$ is not
a prefix of $Y[y_{t}\mathinner{.\,.\allowbreak}]$ and
$C^{2}_{k^{\prime}}(X,x_{t})\neq C^{2}_{k^{\prime}}(Y,y_{t})$. The
contradiction completes the proof.

Finally, we bound
$\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(X),\mathsf{CE}_{k^{\prime}}(Y))$ using
several claims. Consider a set $M$ of indices
$t\in[1\mathinner{.\,.\allowbreak}m]$ such that
$\mathsf{CE}_{k^{\prime}}(X)[t]$ and $\mathsf{CE}_{k^{\prime}}(Y)[t]$ differ
on the first coordinate.

######  Claim 6.13.

If $t\in M$ satisfies $\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot$, then

$[x_{t-1}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|]\cap(\mathcal{B}_{X}(\mathcal{A}_{W})\cup\\{|X|+1\\})\neq\emptyset.$

###### Proof.

For a proof by contradiction, suppose that
$[x_{t-1}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|]\cap(\mathcal{B}_{X}(\mathcal{A}_{W})\cup\\{|X|+1\\})=\emptyset$.
Let $L$ be the length of the longest common prefix of
$X[x_{t}\mathinner{.\,.\allowbreak}]$ and
$Y[y_{t}\mathinner{.\,.\allowbreak}]$. Note that
$(x_{t}+L,y_{t}+L)\in\mathcal{B}(\mathcal{A}_{W})$, so
$x_{t}+L\in\mathcal{B}_{X}(\mathcal{A}_{W})\cup\\{|X|+1\\}$. Consequently,
$L>|C^{2}_{k^{\prime}}(X,x_{t})|\geq|C_{k^{\prime}}(X,x_{t})|$, and therefore
$X[x_{t}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|]=Y[y_{t}\mathinner{.\,.\allowbreak}y_{t}+|C^{2}_{k^{\prime}}(Y,y_{t})|]$
and
$X[x_{t}\mathinner{.\,.\allowbreak}x_{t}+|C_{k^{\prime}}(X,x_{t})|]=Y[y_{t}\mathinner{.\,.\allowbreak}y_{t}+|C_{k^{\prime}}(Y,y_{t})|]$.
In particular, $C^{2}_{k^{\prime}}(X,x_{t})=C^{2}_{k^{\prime}}(Y,y_{t})$.

If $t=1$, then we note that
$\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot\neq\mathsf{CE}_{k^{\prime}}(Y)[t]$, so
$C^{2}_{k^{\prime}}(X,x_{t})=C^{2}_{k^{\prime}}(Y,y_{t})$ contradicts $t\in
M$.

In the following, we assume that $t\geq 2$. Due to
$(x_{t-1},y_{t-1})\notin\mathcal{B}(\mathcal{A}_{W})$, either
$(x_{t-1},y_{t-1})=(x_{t},y_{t})$, or $(x_{t-1},y_{t-1})=(x_{t}-1,y_{t}-1)$
and $X[x_{t}-1]=Y[y_{t}-1]$. In either case, we have
$X[x_{t-1}\mathinner{.\,.\allowbreak}x_{t-1}+|C_{k^{\prime}}(X,x_{t-1})|]=Y[y_{t-1}\mathinner{.\,.\allowbreak}y_{t-1}+|C_{k^{\prime}}(Y,y_{t-1})|]$
due to
$X[x_{t-1}\mathinner{.\,.\allowbreak}x_{t}+|C_{k^{\prime}}(X,x_{t})|]=Y[y_{t-1}\mathinner{.\,.\allowbreak}y_{t}+|C_{k^{\prime}}(Y,y_{t})|]$
and by 6.7. Consequently,
$\min\\{u\in[1\mathinner{.\,.\allowbreak}m]:x_{u}=x_{t-1}+|C_{k^{\prime}}(X,x_{t-1})|\\}=\min\\{u\in[1\mathinner{.\,.\allowbreak}m]:y_{u}=y_{t-1}+|C_{k^{\prime}}(Y,y_{t-1})|\\}$
and, by a similar reasoning,
$\min\\{u\in[1\mathinner{.\,.\allowbreak}m]:x_{u}=x_{t}+|C_{k^{\prime}}(X,x_{t})|\\}=\min\\{u\in[1\mathinner{.\,.\allowbreak}m]:y_{u}=y_{t}+|C_{k^{\prime}}(Y,y_{t})|\\}$.
Hence, the assumption $\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot$ implies
$\mathsf{CE}_{k^{\prime}}(Y)[t]\neq\bot$. Therefore,
$C^{2}_{k^{\prime}}(X,x_{t})=C^{2}_{k^{\prime}}(Y,y_{t})$ contradicts $t\in
M$. ∎

######  Claim 6.14.

There are $\mathcal{O}((k+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))\log m)$
positions $t\in M$ such that $\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot$.

###### Proof.

Let $\mathcal{O}$ be an optimum greedy alignment between $X$ and $Y$. Due to
$k^{\prime}\geq 0pt(\mathcal{O})+0pt(\mathcal{A}_{W})+4k$, from Lemma 6.10 it
follows that $\Delta_{X}(\mathcal{O},\mathcal{A}_{W})$ can be covered by
$\mathcal{O}(\mathsf{cost}(\mathcal{O})+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))=\mathcal{O}(k+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))$
contexts $C_{k^{\prime}}(X,\cdot)$. Let us fix such the smallest family
$\mathcal{C}$ of contexts covering
$\mathcal{B}_{X}(\mathcal{A}_{W})\subseteq\Delta_{X}(\mathcal{O},\mathcal{A}_{W})$.

Define a set
$R_{X}=\\{|X|\\}\cup\bigcup_{X[q\mathinner{.\,.\allowbreak}r]\in\mathcal{C}}\\{q-1,r+1\\}$
and note that $|R_{X}|=\mathcal{O}(|\mathcal{C}|)$. We shall prove that, if
$t\in M$ and $\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot$, then
$C^{2}_{k^{\prime}}(X,x_{t})$ covers at least one position in $R_{X}$. This is
sufficient to derive the claim because, by Lemma 6.9, every position in $X$ is
covered by at most $\mathcal{O}(\log m)$ double contexts
$C^{2}_{k^{\prime}}(X,x_{t})$ with $\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot$.

By 6.13, we have
$[x_{t-1}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|]\cap(\mathcal{B}_{X}(\mathcal{A}_{W})\cup\\{|X|+1\\})\neq\emptyset$.
If
$\\{|X|+1\\}\in[x_{t-1}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|]$,
then $|X|+1=x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|$. Hence,
$C^{2}_{k^{\prime}}(X,x_{t})$ covers the position $|X|\in R_{X}$. Thus, we may
assume that
$[x_{t-1}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|]$
contains a position in $\mathcal{B}_{X}(\mathcal{A}_{W})$. Note that the
fragment $X[q\mathinner{.\,.\allowbreak}r]\in\mathcal{C}$ covering that
position in $\mathcal{B}_{X}(\mathcal{A}_{W})$ satisfies $r\geq x_{t-1}$ and
$q\leq x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|$. In particular, $r+1\geq x_{t}$
and $q-1<x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|$. Now, if
$C^{2}_{k^{\prime}}(X,x_{t})$ covers $q-1$ or $r+1$, then we are done.
Otherwise, $q-1<x_{t}$ and $r+1\geq x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|$, so
$q\leq x_{t}$ and $r\geq x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|$, i.e.,
$C^{2}_{k^{\prime}}(X,x_{t})$ is contained in
$X[q\mathinner{.\,.\allowbreak}r]$ and, since $\overline{\mathsf{maxLZ}}$ is
monotone, $\overline{\mathsf{maxLZ}}(C^{2}_{k^{\prime}}(X,x_{t}))\leq
k^{\prime}$. Consequently,
$C^{2}_{k^{\prime}}(X,x_{t})=C_{k^{\prime}}(X,x_{t})$ is a suffix of $X$, so
$C^{2}_{k^{\prime}}(X,x_{t})$ covers the position $|X|\in R_{X}$. ∎

A symmetric argument shows that there are
$\mathcal{O}((k+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))\log m)$ positions
$t\in M$ such that $\mathsf{CE}_{k^{\prime}}(Y)[t]\neq\bot$. Consequently,
$|M|=\mathcal{O}((k+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))\log m)$. We
bound $\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(X),\mathsf{CE}_{k^{\prime}}(Y))$
using the following claim.

######  Claim 6.15.

$\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(X),\mathsf{CE}_{k^{\prime}}(Y))\leq
2|M|$.

###### Proof.

Let
$M^{\prime}=\\{t\in[1\mathinner{.\,.\allowbreak}m]:\mathsf{CE}_{k^{\prime}}(X)[t]\neq\mathsf{CE}_{k^{\prime}}(Y)[t]\\}$.
Note that $M\subseteq M^{\prime}$, so the claim is equivalent to
$|M^{\prime}\setminus M|\leq|M|$. For every $t\in M^{\prime}\setminus M$, we
shall prove that $t$ is not the leftmost position in $M^{\prime}$ and that the
preceding position in $M^{\prime}$ belongs to $M$.

The assumption $t\in M^{\prime}\setminus M$ implies
$\mathsf{CE}_{k^{\prime}}(X)[t]\neq\bot\neq\mathsf{CE}_{k^{\prime}}(Y)[t]$. We
define $t^{\prime}$ as the largest position in
$[1\mathinner{.\,.\allowbreak}t)$ such that
$\mathsf{CE}_{k^{\prime}}(X)[t^{\prime}]\neq\bot$ or
$\mathsf{CE}_{k^{\prime}}(Y)[t^{\prime}]\neq\bot$. To see that $t^{\prime}$ is
well defined, note that $t>1$ and $\mathsf{CE}_{k^{\prime}}(X)[1]\neq\bot$.

Now, suppose that $t^{\prime}\notin M$. Consequently, we have
$\mathsf{CE}_{k^{\prime}}(X)[t^{\prime}]\neq\bot\neq\mathsf{CE}_{k^{\prime}}(Y)[t^{\prime}]$.
Due to
$\mathsf{CE}_{k^{\prime}}(X)[t^{\prime}+1\mathinner{.\,.\allowbreak}t)=\bot^{t-t^{\prime}-1}$,
Lemma 6.9 implies that $C_{k^{\prime}}(X,x_{t^{\prime}})$ covers $X[x_{t}-1]$,
that is,
$\overline{\mathsf{maxLZ}}(X[x_{t^{\prime}}\mathinner{.\,.\allowbreak}x_{t}))\leq
k^{\prime}$, and hence $X[x_{t^{\prime}}\mathinner{.\,.\allowbreak}x_{t}]$ is
a prefix of $C^{2}_{k^{\prime}}(X,x_{t^{\prime}})$. Moreover,
$C^{2}_{k^{\prime}}(X,x_{t^{\prime}})=C^{2}_{k^{\prime}}(Y,y_{t^{\prime}})$
implies
$X[x_{t^{\prime}}\mathinner{.\,.\allowbreak}x_{t}]\simeq_{\mathcal{A}_{W}}Y[y_{t^{\prime}}\mathinner{.\,.\allowbreak}y_{t^{\prime}}+x_{t}-x_{t^{\prime}}]$
by the greedy nature of $\mathcal{A}_{W}$. As
$(x_{t},y_{t})\in\mathcal{A}_{W}$, we conclude that
$y_{t}=y_{t^{\prime}}+x_{t}-x_{t^{\prime}}$. At the same time, since
$\mathsf{CE}_{k^{\prime}}(X)[t^{\prime}+1\mathinner{.\,.\allowbreak}t)=\bot^{t-t^{\prime}-1}=\mathsf{CE}_{k^{\prime}}(Y)[t^{\prime}+1\mathinner{.\,.\allowbreak}t)$,
we have
$\mathsf{CE}_{k^{\prime}}(X)[t]=(\mathsf{LZ}(\overline{C^{2}_{k^{\prime}}(X,x_{t})}),x_{t}-x_{t^{\prime}})$
and
$\mathsf{CE}_{k^{\prime}}(Y)[t]=(\mathsf{LZ}(\overline{C^{2}_{k^{\prime}}(Y,y_{t})}),y_{t}-y_{t^{\prime}})$.
Thus, $\mathsf{CE}_{k^{\prime}}(X)[t]=\mathsf{CE}_{k^{\prime}}(Y)[t]$, which
contradicts $t\in M^{\prime}$.

Consequently, $t^{\prime}\in M$. In this case,
$M^{\prime}\cap[t^{\prime}\mathinner{.\,.\allowbreak}t]=\\{t^{\prime},t\\}$,
so $t^{\prime}$ is the position of $M^{\prime}$ preceding $t$. Our goal was to
show that such a position exists and belongs to $M$, so this completes the
proof of the claim. ∎

Overall, we conclude that
$\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(X),\mathsf{CE}_{k^{\prime}}(Y))\leq
2|M|=\mathcal{O}((k+\frac{1}{k}\mathsf{cost}(\mathcal{A}_{W}))\log m)$. ∎

######  Lemma 6.16.

Given integers $n\geq k\geq 1$, a seed $r$ of $\mathcal{O}(\log^{2}n)$ random
bits, and streaming access to a string $S\in\Sigma^{\leq n}$, the string
$\mathsf{CE}_{k}(\mathsf{W}(S,n,r))$ can be computed in
$\tilde{\mathcal{O}}(k)$ space and $\tilde{\mathcal{O}}(nk)$ time.

###### Proof.

Let us start with an auxiliary subroutine:

######  Claim 6.17.

There is a streaming algorithm that computes $\mathsf{D}(C_{k}(S,p))$ for
subsequent positions $p\in[1\mathinner{.\,.\allowbreak}|S|]$. The algorithm
uses $\tilde{\mathcal{O}}(k)$ space and $\tilde{\mathcal{O}}(nk)$ time.
Moreover, if $C_{k}(S,p)=S[p\mathinner{.\,.\allowbreak}q)$, then
$\mathsf{D}(C_{k}(S,p))$ is reported while the algorithm processes $S[q]$ (or
the end-of-string token if $q=|S|+1$).

###### Proof.

The algorithm maintains a fragment $S[p\mathinner{.\,.\allowbreak}q)$
satisfying $\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}q))\leq k$
and the encoding $\mathsf{D}(S[p\mathinner{.\,.\allowbreak}q))$. Initially,
$S[p\mathinner{.\,.\allowbreak}q)=S[1\mathinner{.\,.\allowbreak}1)=\varepsilon$.

In each iteration, we read $S[q]$, compute
$\mathsf{D}(S[p\mathinner{.\,.\allowbreak}q])$ (using Proposition 4.2(i)), and
check whether $|\mathsf{LZ}(\overline{S[p\mathinner{.\,.\allowbreak}q]})|\leq
k$ (using Proposition 4.2(f)). By 6.7(a), this condition is equivalent to
$\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}q])\leq k$. If
$\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}q])\leq k$, we
discard $\mathsf{D}(S[p\mathinner{.\,.\allowbreak}q))$ and increment $q$.
Otherwise, we are guaranteed that
$S[p\mathinner{.\,.\allowbreak}q)=C_{k}(S,p)$, so we output
$\mathsf{D}(S[p\mathinner{.\,.\allowbreak}q))$, compute
$\mathsf{D}(S[p+1\mathinner{.\,.\allowbreak}q))$ (using Proposition 4.2(g)),
discard $\mathsf{D}(S[p\mathinner{.\,.\allowbreak}q))$ and
$\mathsf{D}(S[p\mathinner{.\,.\allowbreak}q])$, and increment $p$. By 6.7(b),
we are guaranteed that the invariant
$\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}q))\leq k$ remains
satisfied. In the special case of $q=|S|+1$, we proceed as if
$\overline{\mathsf{maxLZ}}(S[p\mathinner{.\,.\allowbreak}q])>k$.

By 6.7(c), we store $\mathsf{D}(X)$ only for strings $X$ satisfying
$|\overline{\mathsf{maxLZ}}(X)|\leq k+1$, so the space usage and the per-
iteration running time is $\tilde{\mathcal{O}}(k)$. Each iteration increments
either $p$ or $q$, so the algorithm reads $S$ in a streaming fashion and the
amortized running time is $\tilde{\mathcal{O}}(k)$ per character. ∎

We maintain two instances of the algorithm of 6.17 and two instances of the
algorithm of Proposition 3.16. We feed the first instance of 6.17 with the
input stream $S$, obtaining $\mathsf{D}(C_{k}(S,q))$ for subsequent positions
$q\in[1\mathinner{.\,.\allowbreak}|S|]$. Upon retrieving
$\mathsf{D}(C_{k}(S,q))$, we extract $S[q]$ using Proposition 4.2(b) and
forward $S[q]$ to the first instance of Proposition 3.16, which lists indices
$v\in[1\mathinner{.\,.\allowbreak}3n]$ such that $s_{v}=q$. We also forward
$S[q]$ to the second instance of 6.17, obtaining $\mathsf{D}(C_{k}(S,p))$ for
all subsequent positions $p$ such that
$\mathsf{D}(C_{k}(S,p))=S[p\mathinner{.\,.\allowbreak}q)$. Upon retrieving
$\mathsf{D}(C_{k}(S,p))$, we extract $S[p]$ using Proposition 4.2(b) and
forward $S[p]$ to the second instance of Proposition 3.16, which lists indices
$t\in[1\mathinner{.\,.\allowbreak}3n]$ such that $s_{t}=q$. For each such
position $t$, we have $C^{2}_{k}(S,s_{t})=C_{k}(S,p)C_{k}(S,q)$. We compute
$\mu_{t}=\mu(t,\min\\{v\in[1\mathinner{.\,.\allowbreak}3n]:s_{v}=q\\})$ based
on the output of the first instance of Proposition 3.16. If
$\mu_{t}>\mu_{t-1}$, we construct
$\mathsf{LZ}\left(\overline{C^{2}_{k}(S,s_{t})}\right)$ using Proposition
4.2(i) and Proposition 4.2(f).

By Propositions 4.2, 3.16 and 6.17, the algorithm uses
$\tilde{\mathcal{O}}(k)$ space and $\tilde{\mathcal{O}}(nk)$ time. ∎

###  6.3 Applications of Hamming distance sketches

Let us start by reminding the fingerprints (sketches) for testing string
equality.

######  Fact 6.18 (see e.g. [38]).

There exists a fingerprint $\psi$ (parameterized by an integer
$n\in\mathbb{Z}_{+}$, a threshold $\delta$ with $1\geq\delta\geq
n^{-\mathcal{O}(1)}$, an alphabet
$\Sigma=[0\mathinner{.\,.\allowbreak}n^{\mathcal{O}(1)})$, and a seed of
$\mathcal{O}(\log n)$ random bits) such that:

  1. 1.

The fingerprint $\psi(S)$ of a string $S\in\Sigma^{\leq n}$ takes
$\mathcal{O}(\log\delta^{-1})$ bits. Given streaming access to $S$, it can be
constructed in $\mathcal{O}(|S|)$ time using $\mathcal{O}(\log n)$ bits of
space.

  2. 2.

For all strings $X,Y\in\Sigma^{\leq n}$, we have
$\Pr[\psi(X)=\psi(Y)]\leq\delta$ if $X\neq Y$ (and $\psi(X)=\psi(Y)$
otherwise).

For two equal-length strings $X,Y$, the set of _mismatch positions_ is defined
as $\mathsf{MP}(X,Y)=\\{i\in[1\mathinner{.\,.\allowbreak}|X|]:X[i]\neq
Y[i]\\}$ and the _mismatch information_
$\mathsf{MI}(X,Y)=\\{(i,X[i],Y[i]):i\in\mathsf{MP}(X,Y)\\}$. Below, we adapt
the Hamming sketches of [16] to large alphabets.

######  Theorem 6.19.

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

  1. 1.

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

  2. 2.

There exists a decoding algorithm that, given $\mathsf{sk}^{H}_{k}(X)$ and
$\mathsf{sk}^{H}_{k}(Y)$ for strings $X,Y\in\Sigma^{n}$, with probability at
least $1-\delta$ either returns $\mathsf{MI}(X,Y)$ or certifies that
$\mathsf{hd}(X,Y)>k$. The algorithm uses
$\mathcal{O}(k\log(n\sigma)\log^{2}(n\log\sigma))$ time and
$\mathcal{O}(k\log(n\sigma))$ bits of space.

###### Proof.

The construction of [16] satisfies the required conditions provided that
$\sigma=n^{\mathcal{O}(1)}$. Henceforth, we assume without loss of generality
that $\sigma$ is a power of two satisfying $\sigma\geq n\log\sigma$.

We interpret each character in $\Sigma$ as a block of
$b=\lceil\log_{n\log\sigma}\sigma\rceil$ characters in
$[0\mathinner{.\,.\allowbreak}n\log\sigma)$. Moreover, we consider the
fingerprints $\psi$ of Fact 6.18 with
$\delta_{\ref{fact:kr}}=\frac{\delta}{2n}$ and
$n_{\ref{fact:kr}}=\sigma_{\ref{fact:kr}}=n\log\sigma$. This construction uses
$\mathcal{O}(\log n_{\ref{fact:kr}})=\mathcal{O}(\log(n\log\sigma))$ random
bits and produces fingerprints of
$\mathcal{O}(\log\delta^{-1}_{\ref{fact:kr}})=\mathcal{O}(\log n)$ bits.

Given a string $S\in\Sigma^{n}$, we define a string
$\bar{S}[1\mathinner{.\,.\allowbreak}nb]$ so that
$\bar{S}[ib-j+1]=(S[i][j],\psi(S[i]))$ for
$i\in[1\mathinner{.\,.\allowbreak}|S|]$ and
$j\in[1\mathinner{.\,.\allowbreak}b]$. Consequently, we set
$\mathsf{sk}^{H}_{k}(S):=\mathsf{sk}^{H}_{\bar{k}}(\bar{S})$ using the the
sketch of [16] with $\bar{\delta}=\frac{\delta}{2}$, $\bar{n}=nb$,
$\bar{k}=kb$, and $\bar{\sigma}\leq n^{\mathcal{O}(1)}\log\sigma$. Note that
this is feasible since $\bar{\sigma}\leq
n^{\mathcal{O}(1)}\leq\bar{n}^{\mathcal{O}(1)}$ if $n\leq\log\sigma$ and
$\bar{\sigma}\leq\log^{\mathcal{O}(1)}\sigma\leq(\log_{\log^{2}\sigma}\sigma)^{\mathcal{O}(1)}\leq
b^{\mathcal{O}(1)}\leq\bar{n}^{\mathcal{O}(1)}$ otherwise. This construction
uses $\mathcal{O}(\log\bar{n})=\mathcal{O}(\log(n\log\sigma))$ further random
bits and produces a sketch of
$\mathcal{O}(\bar{k}\log\bar{n})=\mathcal{O}(kb\log(nb))=\mathcal{O}(k\log_{n\log\sigma}\sigma\log(n\log\sigma)=\mathcal{O}(k\log\sigma)$
bits.

The auxiliary string $\bar{S}$ is constructed in
$\mathcal{O}(\bar{n})=\mathcal{O}(n\log\sigma)$ time using
$\mathcal{O}(\log(n\sigma))$ bits of space. The stream representing $\bar{S}$
is passed to the encoding algorithm of [16], which takes
$\mathcal{O}(\bar{n}\log^{2}\bar{n})=\mathcal{O}(n\log_{n\log\sigma}\sigma\log^{2}(n\log\sigma))=\mathcal{O}(n\log(n\sigma)\log(n\log\sigma))$
time and $\mathcal{O}(\bar{k}\log\bar{n})=\mathcal{O}(k\log\sigma)$ bits of
space.

The decoding algorithm, given $\mathsf{sk}^{H}_{\bar{k}}(\bar{X})$ and
$\mathsf{sk}^{H}_{\bar{k}}(\bar{Y})$, runs the decoding algorithm of [16]. If
the latter certifies $\mathsf{hd}(\bar{X},\bar{Y})>\bar{Y}$, we certify that
$\mathsf{hd}(X,Y)>k$. Otherwise, we interpret the output as
$\mathsf{MI}(\bar{X},\bar{Y})$. For each position
$i\in[1\mathinner{.\,.\allowbreak}|X|]$ such that
$(ib-b\mathinner{.\,.\allowbreak}ib]\subseteq\mathsf{MP}(\bar{X},\bar{Y})$ we
retrieve $X[i][j]$ and $Y[i][j]$ for each
$j\in[1\mathinner{.\,.\allowbreak}b]$ from
$(ib-j+1,\bar{X}[ib-j+1],\bar{Y}[ib-j+1])\in\mathsf{MI}(\bar{X},\bar{Y})$, and
then we output $(i,X[i],Y[i])\in\mathsf{MI}(X,Y)$.

As for correctness, with at most $\delta_{\ref{fact:kr}}+n\bar{\delta}=\delta$
probability loss, we may assume that the decoder of [16] is successful and
that, for all $i\in[1\mathinner{.\,.\allowbreak}|X|]$, we have
$\psi(X[i])=\psi(Y[i])$ if and only if $X[i]=Y[i]$. The latter assumption
yields
$\mathsf{MP}(\bar{X},\bar{Y})=\bigcup_{i\in\mathsf{MP}(X,Y)}(ib-b\mathinner{.\,.\allowbreak}ib]$
and thus $\mathsf{hd}(\bar{X},\bar{Y})=b\cdot\mathsf{hd}(X,Y)$. Hence, we
correctly certify $\mathsf{hd}(X,Y)>k$ if
$\mathsf{hd}(\bar{X},\bar{Y})>\bar{k}$, and we correctly reconstruct
$\mathsf{MI}(X,Y)$ otherwise.

The decoder uses
$\mathcal{O}(\bar{k}\log^{3}\bar{n})=\mathcal{O}(k\log_{n\log\sigma}\sigma\log^{3}(n\log\sigma))=\mathcal{O}(k\log\sigma\log^{2}(n\log\sigma))$
time and $\mathcal{O}(\bar{k}\log\bar{n})=\mathcal{O}(k\log\sigma)$ bits of
space. ∎

Next, consider an alphabet $\hat{\Sigma}:=\Sigma\times\mathbb{Z}_{\geq 0}$ and
a function $\pi:\hat{\Sigma}\to\mathbb{Z}_{\geq 0}$ defined so that
$\pi((a,v))=v$ for $(a,v)\in\hat{\Sigma}$ and
$\pi(S)=\sum_{i=1}^{|S|}\pi(S[i])$ for $S\in\hat{\Sigma}^{*}$. For two strings
$X,Y\in\hat{\Sigma}^{*}$ of the same length, we define the _prefix mismatch
information_

$\mathsf{PMI}(X,Y)=\\{(i,\pi(X[1\mathinner{.\,.\allowbreak}i)),\pi(Y[1\mathinner{.\,.\allowbreak}i))):i\in\mathsf{MP}(X,Y)\\}.$

######  Proposition 6.20.

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

  1. 1.

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

  2. 2.

There exists a decoding algorithm that, given the sketches
$\mathsf{sk}^{P}_{k}(X)$ and $\mathsf{sk}^{P}_{k}(Y)$ of strings
$X,Y\in\hat{\Sigma}^{n}$ satisfying $\pi(X),\pi(Y)<n$, with probability at
least $1-\delta$ either returns $\mathsf{PMI}(X,Y)$ or certifies that
$\mathsf{hd}(X,Y)>k$. The algorithm uses $\mathcal{O}(k\log^{4}n)$ time and
$\mathcal{O}(k\log^{2}n)$ bits of space.

###### Proof.

Let us fix a complete binary tree $\mathcal{T}$ with $n$ leaves, numbered with
$[1\mathinner{.\,.\allowbreak}n]$ in the left-to-right order, and let
$v_{1},\ldots,v_{2n-1}$ denote the nodes of $\mathcal{T}$ in the pre-order.
For each node $v_{i}\in\mathcal{T}$, let
$[p_{i}\mathinner{.\,.\allowbreak}q_{i})\subseteq[1\mathinner{.\,.\allowbreak}n]$
be the indices of the leaves in the subtree of $v_{i}$. Consider the
fingerprints $\psi$ of Fact 6.18 parameterized by
$\delta_{\ref{fact:kr}}=\frac{\delta}{4n-2}$,
$n_{\ref{fact:kr}}=\mathcal{O}(n\log(n\sigma))$, and
$\sigma_{\ref{fact:kr}}=2$: Given a string $S\in\hat{\Sigma}^{n}$, we define a
string $\mathcal{T}(S)[1\mathinner{.\,.\allowbreak}2n)$ so that
$\mathcal{T}(S)[i]=(\pi(S[p_{i}\mathinner{.\,.\allowbreak}q_{i})),\psi(S[p_{i}\mathinner{.\,.\allowbreak}q_{i})))$
for every $i\in[1\mathinner{.\,.\allowbreak}2n)$, where $\psi$ expands each
character of $\hat{\Sigma}$ into a sequence of $\mathcal{O}(\log(n\sigma))$
bits. We set
$\mathsf{sk}^{P}_{k}(S):=\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}(\mathcal{T}(S))$,
where $\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}$ is the sketch of Theorem 6.19 with
$\delta_{\ref{thm:skH}}=\frac{\delta}{2}$, $n_{\ref{thm:skH}}=2n-1$,
$k_{\ref{thm:skH}}=\min(k\lceil{\log(2n)}\rceil,n_{\ref{thm:skH}})$, and
$\sigma_{\ref{thm:skH}}\leq
2^{\mathcal{O}(\log(n/\delta_{\ref{fact:kr}}))}\leq n^{\mathcal{O}(1)}$.

This construction uses $\mathcal{O}(\log
n_{\ref{fact:kr}}+\log(n_{\ref{thm:skH}}\log\sigma_{\ref{thm:skH}}))=\mathcal{O}(\log(n\log\sigma))$
random bits and produces sketches of
$\mathcal{O}(k_{\ref{thm:skH}}\log(n_{\ref{thm:skH}}\sigma_{\ref{thm:skH}}))=\mathcal{O}(k\log^{2}n)$
bits.

The encoding algorithm transforms $S$ into $\mathcal{T}(S)$ and feeds
$\mathcal{T}(S)$ into the encoding procedure of Theorem 6.19. Construction of
$\mathcal{T}(S)$ is organized in $\mathcal{O}(\log n)$ layers, each
responsible for nodes $v_{i}\in\mathcal{T}$ at a fixed level. The intervals
$[p_{i}\mathinner{.\,.\allowbreak}q_{i})$ corresponding to these nodes are
disjoint so, at any time, a layer produces a single character
$\mathcal{T}(S)[i]$ and, by Fact 6.18, spends $\mathcal{O}(n\log\sigma)$
amortized time and uses $\mathcal{O}(\log n)$ bits of space to process a
single character $S[j]$. Since the tree $\mathcal{T}$ is linearized in the
post-order fashion, all levels can read the string $S$ with a common left-to-
right pass and outputting $\mathcal{T}(S)$ does not require any buffers.
Overall, construction of $\mathcal{T}(S)$ takes $\mathcal{O}(n\log
n\log(n\log\sigma))$ time and uses $\mathcal{O}(\log n\log(n\log\sigma))$ bits
of space. The encoder of Theorem 6.19 takes
$\mathcal{O}(n_{\ref{thm:skH}}\log(n_{\ref{thm:skH}}\sigma_{\ref{thm:skH}})\log(n_{\ref{thm:skH}}\log\sigma_{\ref{thm:skH}}))=\mathcal{O}(n\log^{2}n)$
time and uses
$\mathcal{O}(k_{\ref{thm:skH}}\log(n_{\ref{thm:skH}}\sigma_{\ref{thm:skH}}))=\mathcal{O}(k\log^{2}n)$
bits of space.

The decoding algorithm first retrieves
$\mathsf{MI}(\mathcal{T}(X),\mathcal{T}(Y))$ from
$\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}(\mathcal{T}(X))$ and
$\mathsf{sk}^{H}_{\ref{thm:skH}}(\mathcal{T}(Y))$ using the decoder of Theorem
6.19. If the output of that subroutine can be interpreted as
$\mathsf{MI}(\mathcal{T}(X),\mathcal{T}(Y))$, then we use 6.21 below to
retrieve $\mathsf{MI}(X,Y)$. If the size of the obtained set does not exceed
$k$, we return the set. In the remaining cases, we certify that
$\mathsf{hd}(X,Y)>k$.

######  Claim 6.21.

For every $X,Y\in\hat{\Sigma}^{n}$, the set $\mathsf{PMI}(X,Y)$ can be
extracted from $\mathsf{MI}(\mathcal{T}(X),\mathcal{T}(Y))$ in time and space
$\mathcal{O}(\mathsf{hd}(X,Y)\log n)$ with success probability at least
$1-\frac{\delta}{2}$.

###### Proof.

We assume that, for every $i\in[1\mathinner{.\,.\allowbreak}2n)$, the equality
$\psi(X[p_{i}\mathinner{.\,.\allowbreak}q_{i}))=\psi(Y[p_{i}\mathinner{.\,.\allowbreak}q_{i}))$
implies
$X[p_{i}\mathinner{.\,.\allowbreak}q_{i})=Y[p_{i}\mathinner{.\,.\allowbreak}q_{i})$.
By Fact 6.18, each of the implications fails with probability at most
$\delta_{\ref{fact:kr}}$, so the overall failure probability can be bounded by
$\delta_{\ref{fact:kr}}\cdot(2n-1)=\frac{\delta}{2}$.

Our assumption yields

$\mathsf{MP}(\mathcal{T}(X),\mathcal{T}(Y))=\\{i\in[1\mathinner{.\,.\allowbreak}2n):[p_{i}\mathinner{.\,.\allowbreak}q_{i})\cap\mathsf{MP}(X,Y)\neq\emptyset\\}.$

In particular, $\mathsf{MP}(X,Y)=\\{p_{i}:v_{i}\text{ is a leaf and
}i\in\mathsf{MP}(\mathcal{T}(X),\mathcal{T}(Y))\\}$. Thus, it remains to
describe how to extract $\pi(X[1\mathinner{.\,.\allowbreak}p))$ and
$\pi(Y[1\mathinner{.\,.\allowbreak}p))$ for each $p\in\mathsf{MP}(X,Y)$; by
symmetry, we focus on $\pi(X[1\mathinner{.\,.\allowbreak}p))$. For this, we
process subsequent nodes $v_{i}$ on the path from the root of $\mathcal{T}$ to
the leaf $v_{j}$ such that $\\{p\\}=[p_{j}\mathinner{.\,.\allowbreak}q_{j})$
maintaining $\pi(X[1\mathinner{.\,.\allowbreak}p_{i}))$. Note that the values
$\pi(X[p_{i}\mathinner{.\,.\allowbreak}q_{i}))$ can be extracted from
$\mathsf{MI}(\mathcal{T}(X),\mathcal{T}(Y))$ due to
$p\in[p_{i}\mathinner{.\,.\allowbreak}q_{i})$.

If $v_{i}$ is the root, then
$\pi(X[1\mathinner{.\,.\allowbreak}p_{i}))=\pi(\varepsilon)=0$. If $v_{i}$ is
the left child of $v_{i^{\prime}}$, then $p_{i}=p_{i^{\prime}}$, so
$\pi(X[1\mathinner{.\,.\allowbreak}p_{i}))=\pi(X[1\mathinner{.\,.\allowbreak}p_{i^{\prime}}))$
has already been computed. If $v_{i}$ is the right child of $v_{i^{\prime}}$,
then $q_{i}=q_{i^{\prime}}$, so
$\pi(X[1\mathinner{.\,.\allowbreak}p_{i}))+\pi(X[p_{i}\mathinner{.\,.\allowbreak}q_{i}))=\pi(X[1\mathinner{.\,.\allowbreak}q_{i}))=\pi(X[1\mathinner{.\,.\allowbreak}q_{i^{\prime}}))=\pi(X[1\mathinner{.\,.\allowbreak}p_{i^{\prime}}))+\pi(X[p_{i^{\prime}}\mathinner{.\,.\allowbreak}q_{i^{\prime}}))$.
Consequently, $\pi(X[1\mathinner{.\,.\allowbreak}p_{i}))$ can be retrieved
from $\pi(X[1\mathinner{.\,.\allowbreak}p_{i^{\prime}}))$, which has already
been computed, as well as $\pi(X[p_{i}\mathinner{.\,.\allowbreak}q_{i}))$ and
$\pi(X[p_{i^{\prime}}\mathinner{.\,.\allowbreak}q_{i^{\prime}}))$, which are
available in $\mathsf{MI}(\mathcal{T}(X),\mathcal{T}(Y))$. When this process
reaches $v_{j}$, it results in the sought value
$\pi(X[1\mathinner{.\,.\allowbreak}p))=\pi(X[1\mathinner{.\,.\allowbreak}p_{j}))$.
∎

It remains to analyze correctness of the decoding algorithm. The decoder of
Theorem 6.19 fails with probability at most
$\delta_{\ref{thm:skH}}=\frac{\delta}{2}$ and the procedure of 6.21 fails with
probability at most $\frac{\delta}{2}$. Thus, with at most $\delta$
probability loss, we may assume that both calls are successful.

If $\mathsf{hd}(\mathcal{T}(X),\mathcal{T}(Y))\leq k_{\ref{thm:skH}}$, then
the decoder of Theorem 6.19 retrieves
$\mathsf{MI}(\mathcal{T}(X),\mathcal{T}(Y))$ and the procedure of 6.21 results
in $\mathsf{MI}(X,Y)$. Depending on whether
$\mathsf{hd}(X,Y)=|\mathsf{MI}(X,Y)|\leq k$ or not, our decoding algorithm
thus correctly returns $\mathsf{MI}(X,Y)$ or certifies that
$\mathsf{hd}(X,Y)>k$.

Otherwise, the algorithm of Theorem 6.19 certifies
$\mathsf{hd}(\mathcal{T}(X),\mathcal{T}(Y))>k_{\ref{thm:skH}}$, and the whole
decoding procedure certifies $\mathsf{hd}(X,Y)>k$. This is correct because of
$\mathsf{hd}(\mathcal{T}(X),\mathcal{T}(Y))\leq\mathsf{hd}(X,Y)\lceil{\log(2n)}\rceil$.
To see this, observe that
$[p_{i}\mathinner{.\,.\allowbreak}q_{i})\cap\mathsf{MP}(X,Y)=\emptyset$
implies
$X[p_{i}\mathinner{.\,.\allowbreak}q_{i})=Y[p_{i}\mathinner{.\,.\allowbreak}q_{i})$
and $\mathcal{T}(X)[i]=\mathcal{T}(Y)[i]$. However, every leaf of
$\mathcal{T}$ has at most $\lceil{\log(2n)}\rceil$ ancestors (including
itself). Consequently, for every $j\in\mathsf{MP}(X,Y)$, there are at most
$\lceil{\log(2n)}\rceil$ nodes $v_{i}$ such that
$j\in[p_{i}\mathinner{.\,.\allowbreak}q_{i})$. ∎

###  6.4 Edit Distance Sketches

We are now ready to show the main result of this section.

See 3.17

###### Proof.

Let $c_{\ref{prp:alg}}$ be the constant of Proposition 3.16 for
$\delta_{\ref{prp:alg}}=\frac{\delta}{3}$, and let $c_{\ref{lem:bcgk}}$ be the
constant of Lemma 6.12. We shall use $\mathsf{CE}_{k^{\prime}}(W)$ with
$k^{\prime}=(c_{\ref{prp:alg}}+5)k$ and $W=\mathsf{W}(n,r,S)$, where $r$ is a
random seed of $\mathcal{O}(\log^{2}n)$ bits. Observe that the alphabet of
$\mathsf{CE}_{k^{\prime}}(W)$ can be interpreted as
$[0\mathinner{.\,.\allowbreak}n^{\mathcal{O}(k)})\times[0\mathinner{.\,.\allowbreak}n]$
because the $|\mathsf{LZ}(\overline{C^{2}_{k^{\prime}}(S,s)})|=\mathcal{O}(k)$
for each $s\in[1\mathinner{.\,.\allowbreak}|S|]$. We shall use Theorems 6.19
and 6.20 with $n_{\ref{thm:skH}}=n_{\ref{prp:mpi}}=3n$,
$\delta_{\ref{thm:skH}}=\delta_{\ref{prp:mpi}}=\tfrac{\delta}{3}$,
$k_{\ref{thm:skH}}=k_{\ref{prp:mpi}}=\min(n_{\ref{thm:skH}},\lfloor
c_{\ref{lem:bcgk}}(1+c_{\ref{prp:alg}})k\log(3n)\rfloor)$, and
$\sigma_{\ref{thm:skH}}=\sigma_{\ref{prp:mpi}}=n^{\mathcal{O}(k)}.$

The sketch $\mathsf{sk}^{E}_{k}(S)$ of a string $S\in\Sigma^{\leq n}$ consists
of $|S|$ as well as the sketches
$\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}(\mathsf{CE}_{k^{\prime}}(W))$ and
$\mathsf{sk}^{P}_{k_{\ref{prp:mpi}}}(\mathsf{CE}_{k^{\prime}}(W))$. This
construction uses

$\mathcal{O}(\log^{2}n+\log(n_{\ref{thm:skH}}\log\sigma_{\ref{thm:skH}})+\log(n_{\ref{prp:mpi}}\log\sigma_{\ref{prp:mpi}}))=\mathcal{O}(\log^{2}n+\log(nk\log
n))=\mathcal{O}(\log^{2}n)$

random bits and produces sketches of bit-size

$\mathcal{O}(k_{\ref{thm:skH}}\log(n_{\ref{thm:skH}}\sigma_{\ref{thm:skH}})+k_{\ref{prp:mpi}}\log^{2}n_{\ref{prp:mpi}})=\mathcal{O}(k\log
n\log(n^{\mathcal{O}(k)})+k\log^{3}n)=\mathcal{O}(k^{2}\log^{3}n).$

The encoding algorithm uses Lemma 6.16 to transform the input stream
representing $S$ to an auxiliary stream representing
$\mathsf{CE}_{k^{\prime}}(W)$, which we forward to the encoders constructing
$\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}(\mathsf{CE}_{k^{\prime}}(S))$ and
$\mathsf{sk}^{P}_{k_{\ref{prp:mpi}}}(\mathsf{CE}_{k^{\prime}}(W))$. Thus, it
takes
$\tilde{\mathcal{O}}(nk^{\prime}+n_{\ref{thm:skH}}\log\sigma_{\ref{thm:skH}}+n_{\ref{prp:mpi}})=\tilde{\mathcal{O}}(nk)$
time and uses
$\tilde{\mathcal{O}}(k^{\prime}+k_{\ref{thm:skH}}\log\sigma_{\ref{thm:skH}}+k_{\ref{prp:mpi}})=\tilde{\mathcal{O}}(k^{2})$
space.

##### Decoding Algorithm

Let $\mathcal{A}_{\mathsf{W}}$ be the zip alignment of walks
$W_{X}=(x_{t})_{t=1}^{3n+1}=\mathsf{W}(n,r,X)$ and
$W_{Y}=(y_{t})_{t=1}^{3n+1}=\mathsf{W}(n,r,Y)$ over strings
$X,Y\in\Sigma^{\leq n}$.

Given sketches $\mathsf{sk}^{E}_{k}(X),\mathsf{sk}^{E}_{k}(Y)$, we run the
decoders for
$\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}(\mathsf{CE}_{k^{\prime}}(W_{X})),\mathsf{sk}^{H}_{k_{\ref{thm:skH}}}(\mathsf{CE}_{k^{\prime}}(W_{Y}))$
and
$\mathsf{sk}^{P}_{k_{\ref{prp:mpi}}}(\mathsf{CE}_{k^{\prime}}(W_{X})),\mathsf{sk}^{P}_{k_{\ref{prp:mpi}}}(\mathsf{CE}_{k^{\prime}}(W_{Y}))$.
We certify $\mathsf{ed}(X,Y)>k$ if either procedure certifies
$\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{Y}))>k_{\ref{thm:skH}}=k_{\ref{prp:mpi}}$.
Otherwise, the decoder interprets the outputs as
$\mathsf{MI}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{Y}))$
and
$\mathsf{PMI}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{Y}))$,
respectively. In this case, we construct $\mathsf{E}^{M}(X,Y)$ for
$M=\\{(x,y)\in\mathcal{M}_{X,Y}(\mathcal{A}_{\mathsf{W}}):x\in P_{X}\text{ or
}y\in P_{Y}\\}$, where $P_{X}$ and $P_{Y}$ are defined in the statement of
Lemma 6.12. Finally, we compute $\mathsf{GR}_{k}(X,Y)$ using Proposition 5.12
or $\min(\mathsf{ed}(X,Y),k+1)$ using Corollary 5.5.

######  Claim 6.22.

Given
$\mathsf{MI}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{Y}))$
and
$\mathsf{PMI}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{Y}))$,
the encoding $\mathsf{E}^{M}(X,Y)$ can be constructed in
$\tilde{\mathcal{O}}(k^{3})$ time using $\tilde{\mathcal{O}}(k^{2})$ space.
Moreover, $|\mathsf{LZ}(X^{M}Y^{M})|=\tilde{\mathcal{O}}(k^{2})$.

###### Proof.

We proceed in two phases. In the first phase, we construct the compressed
representation $\mathsf{D}(X^{\prime})$ of a string
$X^{\prime}\in(\Sigma\cup\\{\\#\\})^{|X|}$ such that $X^{\prime}[x]=X[x]$ if
$x\in P_{X}$ and $X^{\prime}[x]=\\#$ otherwise. We initialize
$X^{\prime}:=\\#^{|X|}$ (via $\mathsf{LZ}(\\#^{|X|})$ using Proposition
4.2(h)). Next, we iterate over positions
$t\in[1\mathinner{.\,.\allowbreak}3n]$ such that
$\bot\neq\mathsf{CE}_{k^{\prime}}(W_{X})[t]\neq\mathsf{CE}_{k^{\prime}}(W_{Y})[t]$.
We retrieve $x_{t}$ and
$\mathsf{LZ}\big{(}\overline{C^{2}_{k^{\prime}}(X,x_{t})}\big{)}$ from the
mismatch information, convert
$\mathsf{LZ}\big{(}\overline{C^{2}_{k^{\prime}}(X,x_{t})}\big{)}$ to
$\mathsf{D}(C^{2}_{k^{\prime}}(X,x_{t}))$ (Proposition 4.2(h)), and update
$\mathsf{D}(X^{\prime})$, setting
$X^{\prime}[x_{t}\mathinner{.\,.\allowbreak}x_{t}+|C^{2}_{k^{\prime}}(X,x_{t})|):=C^{2}_{k^{\prime}}(X,x_{t})$
(Proposition 4.2(g)(i)). We also symmetrically construct the compressed
representation $\mathsf{D}(Y^{\prime})$ of a string
$Y^{\prime}\in(\Sigma\cup\\{\\#\\})^{|Y|}$ such that $Y^{\prime}[y]=Y[y]$ if
$y\in P_{Y}$ and $Y^{\prime}[y]=\\#$ otherwise.

In the second phase, we convert $\mathsf{D}(X^{\prime})$ to
$\mathsf{D}(X^{M})$. Here, the goal is make sure that $X^{M}[x]=\\#$ not only
for $x\in P_{X}$, but also when $X[x]\simeq_{\mathcal{A}_{\mathsf{W}}}Y[y]$
for some $y\in P_{Y}$. For this, we iterate over dummy segments
$Y^{\prime}[y\mathinner{.\,.\allowbreak}y^{\prime})$. By Lemma 6.12,
$\mathcal{A}_{\mathsf{W}}$ matches $Y[y\mathinner{.\,.\allowbreak}y^{\prime})$
to a fragment of $X[x\mathinner{.\,.\allowbreak}x^{\prime})$. Hence, we shall
identify the shift $x-y$ and set
$X^{M}[x\mathinner{.\,.\allowbreak}x^{\prime}):=\\#^{x^{\prime}-x}$
(Proposition 4.2(h)(g)(i)). Let
$\mathsf{MP}_{\mathsf{CE}}:=\mathsf{MP}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{Y}))$.
Define $u,v\in[1\mathinner{.\,.\allowbreak}3n+1]$ so that $u=v=3n+1$ if
$\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}t])\neq
y^{\prime}$ for all $t\in\mathsf{MP}_{\mathsf{CE}}$; otherwise, $u$ is the
smallest index in $\mathsf{MP}_{\mathsf{CE}}$ with
$\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}u])=y^{\prime}$,
whereas $v$ is the smallest index $\mathsf{MP}_{\mathsf{CE}}$ with
$\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}v))=\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}u))$.
We claim that
$x-y=\pi(\mathsf{CE}_{k^{\prime}}(W_{X})[1\mathinner{.\,.\allowbreak}v))-\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}v))$.

If $y^{\prime}\leq|Y|$, then $y^{\prime}-1\notin P_{Y}$ and $y^{\prime}\in
P_{Y}$. Hence, $Y[y^{\prime}]$ is covered by $C^{2}_{k^{\prime}}(Y,y_{t})$ for
some $t\in\mathsf{MP}_{\mathsf{CE}}$ with
$\mathsf{CE}_{k^{\prime}}(W_{X})[t]\neq\bot$, whereas $Y[y^{\prime}-1]$ is not
covered by $C^{2}_{k^{\prime}}(Y,y_{t})$. Hence, there is
$t\in\mathsf{MP}_{\mathsf{CE}}$ with $y_{t}=y^{\prime}$, and therefore
$y_{u}=y^{\prime}$. Similarly, $y_{u}=y^{\prime}$ holds if $y^{\prime}=|Y|+1$.
Let $w\in[1\mathinner{.\,.\allowbreak}3n]$ be the smallest index such that
$\mathsf{CE}_{k^{\prime}}(W_{Y})[w]\neq\bot$ and $C^{2}_{k^{\prime}}(Y,y_{t})$
covers $Y[y^{\prime}-1]$ (such an index exists by Lemma 6.9). Due to
$y^{\prime}-1\in P_{Y}$, we have
$\mathsf{CE}_{k^{\prime}}(W_{X})[w]=\mathsf{CE}_{k^{\prime}}(W_{Y})[w]$, and
hence $x-y=x_{w}-y_{w}$. Definition of $w$ further yields
$\mathsf{CE}_{k^{\prime}}(W_{Y})[w+1\mathinner{.\,.\allowbreak}v)=\bot^{u-w-1}$,
and thus
$\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}v))=y_{w}$.
Moreover, since
$\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}t))=y_{w}$
for $t\in[w+1\mathinner{.\,.\allowbreak}v]$, we have
$\pi(\mathsf{CE}_{k^{\prime}}(W_{X})[1\mathinner{.\,.\allowbreak}v))=x_{w}$ by
definition of $v$. This completes the proof that
$x-y=\pi(\mathsf{CE}_{k^{\prime}}(W_{X})[1\mathinner{.\,.\allowbreak}v))-\pi(\mathsf{CE}_{k^{\prime}}(W_{Y})[1\mathinner{.\,.\allowbreak}v))$.

To derive $\mathsf{E}^{M}(X,Y)$, it suffices to convert
$\mathsf{D}(Y^{\prime})$ to $\mathsf{D}(Y^{M})$ (symmetrically), and to
construct $\mathsf{D}(X^{M}Y^{M})$ using Proposition 4.2(i). Since
$\overline{\mathsf{maxLZ}}(C^{2}_{k^{\prime}}(X,x_{t})),\overline{\mathsf{maxLZ}}(C^{2}_{k^{\prime}}(Y,y_{t}))=\mathcal{O}(k)$
holds for all $t\in[1\mathinner{.\,.\allowbreak}3n+1]$ and since
$|\mathsf{MP}_{\mathsf{CE}}|=\mathcal{O}(k\log n)$, the
$\overline{\mathsf{maxLZ}}(\cdot)$ measure of all intermediate strings is
$\tilde{\mathcal{O}}(k^{2})$. Consequently, the $\tilde{\mathcal{O}}(k)$
applications of Proposition 4.2 cost $\tilde{\mathcal{O}}(k^{3})$ time and use
$\tilde{\mathcal{O}}(k^{2})$ space. ∎

To complete the complexity analysis, observe that the decoding procedure of
Theorem 6.19 uses
$\mathcal{O}(k_{\ref{thm:skH}}\log(n_{\ref{thm:skH}}\sigma_{\ref{thm:skH}})\log^{2}(n_{\ref{thm:skH}}\log\sigma_{\ref{thm:skH}}))=\tilde{\mathcal{O}}(k^{2})$
time and
$\mathcal{O}(k_{\ref{thm:skH}}\log(n_{\ref{thm:skH}}\sigma_{\ref{thm:skH}}))=\tilde{\mathcal{O}}(k^{2})$
bits of space. The procedure of Proposition 6.20 uses
$\mathcal{O}(k_{\ref{prp:mpi}}\log^{2}n_{\ref{prp:mpi}})=\tilde{\mathcal{O}}(k)$
bits of space and costs
$\mathcal{O}(k_{\ref{prp:mpi}}\log^{4}n_{\ref{prp:mpi}})=\tilde{\mathcal{O}}(k)$
time. Finally, due to $|\mathsf{LZ}(X^{M}Y^{M})|=\tilde{\mathcal{O}}(k^{2})$
and $|\mathcal{B}_{k}(X,Y)|=\mathcal{O}(k^{5})$ (Lemma 3.11), the algorithm of
Proposition 5.12 uses $\tilde{\mathcal{O}}(k^{2})$ space and costs
$\tilde{\mathcal{O}}(k^{5})$ time (dominating the overall decoding
complexity). If we only aim to retrieve $\min(\mathsf{ed}(X,Y),k+1)$, the
algorithm of Corollary 5.5 takes $\tilde{\mathcal{O}}(k^{2})$ time and space
(in which case the overall decoding uses $\tilde{\mathcal{O}}(k^{2})$ space
and costs $\tilde{\mathcal{O}}(k^{3})$ time.

It remains to argue that the decoding algorithm is correct. With
$\delta_{\ref{prp:alg}}=\frac{\delta}{3}$ probability loss, we may assume that
$\mathcal{A}_{\mathsf{W}}\in\mathsf{GA}_{c_{\ref{prp:alg}}(\mathsf{ed}(X,Y))^{2}}(X,Y)$
and $0pt(\mathcal{A}_{\mathsf{W}})\leq c_{\ref{prp:alg}}\mathsf{ed}(X,Y)$.
With $\delta_{\ref{thm:skH}}+\delta_{\ref{prp:mpi}}=\frac{2\delta}{3}$ further
probability loss, we may assume that the decoders of Theorems 6.19 and 6.20
are successful. If $\mathsf{ed}(X,Y)>k$, then the correctness follows from
Propositions 5.12 and 5.5 because
$M\subseteq\mathcal{M}_{X,Y}(\mathcal{A}_{\mathsf{W}})$ is a non-crossing
matching. Otherwise, Proposition 3.16 guarantees
$\mathsf{cost}(\mathcal{A}_{\mathsf{W}})\leq c_{\ref{prp:alg}}k^{2}$ and
$0pt(\mathcal{A}_{\mathsf{W}})\leq c_{\ref{prp:alg}}k$ so, in particular,
$k^{\prime}\geq 0pt(\mathcal{A}_{\mathsf{W}})+5k$. By Lemma 6.12, we thus have
$\mathsf{hd}(\mathsf{CE}_{k^{\prime}}(W_{X}),\mathsf{CE}_{k^{\prime}}(W_{X}))\leq
c_{\ref{lem:bcgk}}(1+c_{\ref{prp:alg}})k\log(3n)$. Hence, the decoders of
Theorems 6.19 and 6.20 report the mismatch information. Lemma 6.10 further
implies that $\Delta_{X}(\mathcal{A},\mathcal{A}_{\mathsf{W}})\subseteq P_{X}$
and $\Delta_{Y}(\mathcal{A},\mathcal{A}_{\mathsf{W}})\subseteq P_{Y}$ for all
$\mathcal{A}\in\mathsf{GA}_{k}(X,Y)$. In particular,
$\mathcal{M}_{X,Y}(\mathcal{A})\subseteq M$, and therefore
$\mathcal{M}_{k}(X,Y)\subseteq M$. Consequently, the algorithms of
Propositions 5.12 and 5.5 correctly compute $\mathsf{GR}_{k}(X,Y)$ and
$\min(\mathsf{ed}(X,Y),k+1)$, respectively. ∎

Next, we boost the success probability and strengthen the sketches so that we
can retrieve $\mathsf{qGR}_{k}(X,Y)$ instead of $\mathsf{GR}_{k}(X,Y)$.

######  Corollary 6.23.

There is a sketch $\mathsf{sk}^{\mathsf{q}}_{k}$ (parametrized by
$\delta\in(0,\frac{1}{2})$, 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\log(1/\delta))$ random bits) such that:

  1. (a)

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

  2. (b)

There exists a decoding algorithm that, given
$\mathsf{sk}^{\mathsf{q}}_{k}(X),\mathsf{sk}^{\mathsf{q}}_{k}(Y)$ for
$X,Y\in\Sigma^{\leq n}$, with probability at least $1-\delta$ computes
$\mathsf{qGR}_{k}(X,Y)$. The algorithm takes
$\tilde{\mathcal{O}}(k^{5}\log(1/\delta))$ time and uses
$\tilde{\mathcal{O}}(k^{2}\log(1/\delta))$ space.

###### Proof.

We shall use $\mu=\mathcal{O}(\log(1/\delta))$ sketches
$\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}$ of 3.17 with
$\delta_{\ref{thm:ske}}=\frac{1}{3}$, $n_{\ref{thm:ske}}=n+1$,
$k_{\ref{thm:ske}}=k+1$, and independent seeds. For each of the $\mu$ sketches
$\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}$, the sketch
$\mathsf{sk}^{\mathsf{q}}_{k}(S)$ contains
$\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}(\$_{1}S)$,
$\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}(\$_{2}S)$, where
$\$_{1},\$_{2}\notin\Sigma$ are two distinct symbols. This construction uses
$\mathcal{O}(\mu\log^{2}n_{\ref{thm:ske}})=\mathcal{O}(\log^{2}n\log(1/\delta))$
random bits and produces sketches of $\mathcal{O}(\mu
k^{2}_{\ref{thm:ske}}\log^{3}n_{\ref{thm:ske}})=\mathcal{O}(k^{2}\log^{3}n\log(1/\delta))$
bits.

The encoding algorithm calls $2\mu$ instances of the encoding algorithm of
3.17. Hence, it uses $\tilde{\mathcal{O}}(\mu
k^{2}_{\ref{thm:ske}})=\mathcal{O}(k^{2}\log(1/\delta))$ space and costs
$\tilde{\mathcal{O}}(\mu
n_{\ref{thm:ske}}k_{\ref{thm:ske}})=\tilde{\mathcal{O}}(nk\log(1/\delta))$
time.

The decoding algorithm, given
$\mathsf{sk}^{\mathsf{q}}_{k}(X),\mathsf{sk}^{\mathsf{q}}_{k}(Y)$ for
$X,Y\in\Sigma^{\leq n}$, runs the decoder of 3.17 for
$\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}(\$_{1}X),\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}(\$_{1}Y)$
for each of the $\mu$ sketches $\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}$. This
yields $\mu$ candidates for
$\mathsf{GR}_{k_{\ref{thm:ske}}}(\$_{1}X,\$_{2}Y)$, which we convert to
candidates for $\mathsf{qGR}_{k}(X,Y)$ using Corollary 5.17. Finally, we
determine the majority answer among the $\mu$ candidates. The equality test
uses Proposition 4.2(i)(c) to compare two candidates for
$\mathsf{D}(X^{M}Y^{M})$.

Recall that the decoding procedures of 3.17 use $\tilde{\mathcal{O}}(\mu
k^{5}_{\ref{thm:ske}})=\tilde{\mathcal{O}}(k^{5}\log(1/\delta))$ time and
$\tilde{\mathcal{O}}(\mu
k^{2}_{\ref{thm:ske}})=\tilde{\mathcal{O}}(k^{2}\log(1/\delta))$ space. The
applications of Corollary 5.17 and the equality tests take
$\tilde{\mathcal{O}}(\mu
k^{2}_{\ref{thm:ske}})=\tilde{\mathcal{O}}(k^{2}\log(1/\delta))$ time and
space. The entire decoding algorithm uses
$\tilde{\mathcal{O}}(k^{2}\log(1/\delta))$ space and $\tilde{\mathcal{O}}(\mu
k^{5}_{\ref{thm:ske}})=\tilde{\mathcal{O}}(k^{5}\log(1/\delta))$ time.

As for correctness, since the $\mu$ sketches
$\mathsf{sk}^{E}_{k_{\ref{thm:ske}}}$ are independent, by the Chernoff bound,
the majority answer is wrong with probability at most
$\exp(-\mathcal{O}(\mu))$. Setting $\mu=\mathcal{O}(\log(1/\delta))$ (with a
sufficiently large constant factor) guarantees a success probability of
$1-\delta$. ∎

##  7 Pattern Matching with $k$ Edits

In this section, we present solutions for pattern matching with $k$ edits in
the semi-streaming and streaming settings.

###  7.1 Periodicity under Edit Distance

We start by recalling combinatorial properties of strings periodic under the
edit distance.

See 3.2

######  Claim 7.1.

Suppose that a string $X$ is a prefix of a string $Y$, where $|X|<|Y|\leq
2|X|$. If $X$ is $k$-periodic with $k$-period $Q$, $|Q|\leq|X|/128k$, then
either $Y$ is not $k$-periodic, or $Y$ is $k$-periodic with $k$-period $Q$.

###### Proof.

Suppose by contradiction that $Y$ is $k$-periodic with $k$-period
$Q^{\prime}\neq Q$. Let $q=|Q|$ and $q^{\prime}=|Q^{\prime}|$. Assume first
$q\leq q^{\prime}$. Fix an alignment of the smallest cost between $Y$ and a
prefix of $(Q^{\prime})^{\infty}$. It induces an alignment
$\mathcal{A}^{\prime}$ of cost at most $2k$ between $X$ and a prefix of
$(Q^{\prime})^{\infty}$ and hence generates a partition $X=X_{1}X_{2}\ldots
X_{z}$, where each $X_{i}$, $1\leq i\leq z-1$, is aligned with $Q^{\prime}$
and $X_{z}$ is aligned with a prefix of $Q^{\prime}$. From $|Q|\leq|X|/128k$
we obtain $|X|\geq 128k$ and therefore

$z\geq(|X|-2k)/q^{\prime}\geq\frac{128-2}{128}|X|/(|Y|/128k)\gg 20k$

Consider fragments $X_{1}X_{2}X_{3}X_{4}$, $X_{5}X_{6}X_{7}X_{8}$, and so on.
The total number of such fragments is at least $(20k-3)/4>4k$, and at least
$2k+1$ of them are not edited under $\mathcal{A}^{\prime}$. Fix an optimal
alignment $\mathcal{A}$ between $X$ and a prefix $Q^{\infty}$. The cost of
$\mathcal{A}$ is bounded from above by $2k$, and therefore there is at least
one fragment $X_{4i+1}X_{4i+2}X_{4i+3}X_{4i+4}$ that is not edited. Consider
one such fragment $F$. On the one hand,
$F=Q^{\prime}Q^{\prime}Q^{\prime}Q^{\prime}$. On the other hand,
$F=\mathsf{suff}(Q)Q^{j}\mathsf{pref}(Q)$, where $\mathsf{suff}(Q)$ and
$\mathsf{pref}(Q)$ are some suffix and some prefix of $Q$, respectively.

Suppose first that $q^{\prime}$ is a multiple of $q$. In this case,
$Q^{\prime}=\left(Q[\ell+1\mathinner{.\,.\allowbreak}q]Q[1\mathinner{.\,.\allowbreak}\ell]\right)^{r}$,
where $\ell=q-|\mathsf{suff}(Q)|$ and an integer $r$, which contradicts the
fact that $Q^{\prime}$ is primitive. Otherwise, consider the copy of $Q$ that
contains $F[q^{\prime}]$. Consider also a substring $QQQ$ of $F$ formed by the
copy of $Q$ that contains $F[2q^{\prime}]$, and the preceding and succeeding
copies of $Q$. We then obtain that there is an occurrence of $Q$ in $QQQ$ that
is not aligned with any copy of $Q$ (otherwise, $q^{\prime}$ is a multiple of
$q$), and therefore $Q$ is not primitive, a contradiction.

The case $q>q^{\prime}$ can be treated analogously. ∎

Note that 7.1 implies in particular that a string can have at most one
$k$-period.

###  7.2 Semi-streaming Algorithm

We first present a deterministic algorithm for pattern matching with $k$ edits
in the semi-streaming setting.

####  7.2.1 Preprocessing Stage

Consider a set $\Pi$ of $\mathcal{O}(\log m)$ prefixes $P_{i}$ of $P$
initialised to contain $P$ itself as well as the prefixes of length $2^{\ell}$
for all $0\leq\ell\leq\lfloor{\log|P|}\rfloor$. Order the prefixes by lengths,
and consider two consecutive prefixes $P^{\prime},P^{\prime\prime}$. If
$P^{\prime}$ is $k$-periodic with $k$-period $Q^{\prime}$ while
$P^{\prime\prime}$ is not $k$-periodic, we add two more prefixes to $\Pi$.
Namely, if $\ell$ be the maximum integer such that
$P[1\mathinner{.\,.\allowbreak}\ell]$ is $k$-periodic with $k$-period
$Q^{\prime}$, add to $\Pi$ the prefixes $P[1\mathinner{.\,.\allowbreak}\ell]$
and $P[1\mathinner{.\,.\allowbreak}\ell+1]$. Note that
$P[1\mathinner{.\,.\allowbreak}\ell+1]$ is not $k$-periodic by 7.1.

Let $\Pi=\\{P_{1},P_{2},\ldots,P_{z}\\}$ be the resulting set of prefixes. We
assume that the patterns are ordered in the ascending order of their lengths.
During the preprocessing step, for each $i$ such that $P_{i}$ is $k$-periodic,
we compute its $k$-period $Q_{i}$. We use notation $\ell_{i}=P_{i}$ and
$q_{i}=|Q_{i}|$ (if defined). Importantly, we do not have to store $Q_{i}$
explicitly, we can simply memorize its endpoints in $P_{i}$ which takes
$\mathcal{O}(\log m)$ extra space in total. We also store, for each of the
$\mathcal{O}(k)$ rotations $D$ of $Q_{i}$ that can be a difference of a chain
of $k$-edit occurrences of $P_{i}$ (Corollary 3.5), the encodings
$\mathsf{qGR}_{32k}(D,D)$ and
$\mathsf{qGR}_{30k}(P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])$,
where $\Delta_{i}=\ell_{i}-\ell_{i-1}+k$.

####  7.2.2 Main Stage

The main stage of the algorithm starts after we have preprocessed the pattern.
During the main stage, we receive the text as a stream, one character of a
time. We exploit the following result:

######  Fact 7.2 (cf. [59]).

Given a read-only string $X$ of length $m$ and a streaming string $Y$. There
is a dynamic programming algorithm that correctly identifies all prefixes
$Y^{\prime}$ of $Y$ within edit distance at most $k\leq m$ from $X$, as well
as $\mathsf{ed}(Y^{\prime},X)$ itself. The algorithm takes $\mathcal{O}(km)$
time and $\mathcal{O}(k)$ space besides the space required to store $X$.

##### Chains of $k$-edit occurrences.

During the main stage of the algorithm, we store the following information.
Let $r$ be the newly arrived position of the text $T$. For each $2\leq i\leq
z$, consider all $k$-edit occurrences of $P_{i-1}$ in
$T[r-\ell_{i}-k+1\mathinner{.\,.\allowbreak}r]$. We call such occurrences
_active_. We denote the set of right endpoints of the active occurrences by
$\mathsf{aOCC}_{k}^{E}(P_{i-1},T)$. By Corollaries 3.3 and 3.5,
$\mathsf{aOCC}_{k}^{E}(P_{i-1},T)$ forms $\mathcal{O}(k^{3})$ chains. For each
chain $\mathcal{C}$, we store the following information:

  1. 1.

The leftmost position $lp$ and the size $|\mathcal{C}|$ of $\mathcal{C}$;

  2. 2.

An integer $\mathsf{ed}(\mathcal{C})$ equal to the smallest edit distance from
$P_{i-1}$ to a suffix of $T[1\mathinner{.\,.\allowbreak}r]$ for every endpoint
$r\in\mathcal{C}$;

  3. 3.

If $|\mathcal{C}|\geq 2$, we store the shift $\Delta$ of the difference
$D=Q_{i-1}[1+\Delta\mathinner{.\,.\allowbreak}q_{i-1}]Q_{i-1}[1\mathinner{.\,.\allowbreak}q_{i-1}]$
of $\mathcal{C}$.

If $p^{\ast}$ is the first position added to $\mathcal{C}$ (it can be
different from $lp$ as we will update chains to contain only active
occurrences), then at the position $(p^{\ast}+1)$ we start running the dynamic
programming algorithm for $T[p^{\ast}+1\mathinner{.\,.\allowbreak}]$ and
$P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}]$ (Fact 7.2).

Furthermore, consider the moment when we detect the second position in
$\mathcal{C}$ (if it exists) and hence the difference $D$ of the chain.
Starting from this moment, for every newly added position $p\in\mathcal{C}$,
at the position $(p+1)$ we start computing the greedy encoding
$\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+\Delta_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])$.
We continue running the algorithm until either the computation is over or a
new position in the chain is detected. In the end, we compute the encoding for
the rightmost position in the chain.

##### Detecting new $k$-edit occurrences of $P_{i}$.

We now explain how to detect new $k$-edit occurrences of the prefixes $P_{i}$.
Let $r$ be the latest arrived position of $T$. If $i=1$, then since $k\geq 1$,
$r\in\mathsf{aOCC}_{k}^{E}(P_{1},T)$. Below we consider three possible cases
for $i\geq 2$: $P_{i-1}$ is $k$-periodic, $P_{i}$ is not $k$-periodic;
$P_{i-1}$ is not $k$-periodic; $P_{i-1}$ and $P_{i}$ are $k$-periodic.

###### Case 1: $P_{i-1}$ is $k$-periodic, $P_{i}$ is not $k$-periodic.

By construction, in this case $\ell_{i-1}+1=\ell_{i}$. The position
$r\in\mathsf{aOCC}_{k}^{E}(P_{i},T)$ iff one of the following conditions is
satisfied:

  1. 1.

The smallest edit distance from $P_{i-1}$ to a suffix of
$T[1\mathinner{.\,.\allowbreak}r]$ is at most $k-1$ (this corresponds to the
case when the last character of $P_{i}$ is deleted in an optimal alignment of
a suffix of $T[1\mathinner{.\,.\allowbreak}r]$ and $P_{i}$);

  2. 2.

The smallest edit distance from $P_{i-1}$ to a suffix of
$T[1\mathinner{.\,.\allowbreak}r-1]$ is at most $k-1$ and $P_{i}[\ell_{i}]\neq
T[r]$ (this corresponds to the case when the last character of $P_{i}$ is
substituted for $T[r]$ in an optimal alignment of a suffix of
$T[1\mathinner{.\,.\allowbreak}r]$ and $P_{i}$);

  3. 3.

The smallest edit distance from $P_{i-1}$ to a suffix of
$T[1\mathinner{.\,.\allowbreak}r-1]$ is at most $k$ and $P_{i}[\ell_{i}]=T[r]$
(this corresponds to the case when the last character of $P_{i}$ is matched
with $T[r]$ in an optimal alignment of a suffix of
$T[1\mathinner{.\,.\allowbreak}r]$ and $P_{i}$);

  4. 4.

The smallest edit distance from $P_{i}$ to a suffix of
$T[1\mathinner{.\,.\allowbreak}r-1]$ is at most $k-1$ (this corresponds to the
case when $T[r]$ is deleted in an optimal alignment of a suffix of
$T[1\mathinner{.\,.\allowbreak}r]$ and $P_{i}$).

We can decide which of the conditions is satisfied, and therefore whether
$r\in\mathsf{aOCC}_{k}^{E}(P_{i},T)$ in $\mathcal{O}(k^{3})$ time using
$\mathsf{aOCC}_{k}^{E}(P_{i-1},T)$ and $\mathsf{aOCC}_{k}^{E}(P_{i},T)$.
Moreover, we can compute the smallest edit distance from $P_{i}$ to a suffix
of $T[1\mathinner{.\,.\allowbreak}r]$ if it is bounded by $k$.

For the next two cases, we will use the following simple observation that
follows from Fact 2.3:

######  Observation 7.3.

Let $\mathsf{ed}_{i-1}(r^{\prime})$ be the smallest edit distance from
$P_{i-1}$ to a suffix of $T[1\mathinner{.\,.\allowbreak}r^{\prime}]$, and
define

$d=\min_{\begin{subarray}{c}r^{\prime}\in\mathsf{aOCC}_{k}^{E}(P_{i-1},T)\\\
r^{\prime}\in[r+1-\Delta_{i},r+1-\Delta_{i}+2k]\end{subarray}}\\{\mathsf{ed}_{i-1}(r^{\prime})+\mathsf{ed}(P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}],T[r^{\prime}+1\mathinner{.\,.\allowbreak}r])\\}$
(2)

The smallest edit distance from $P_{i}$ to $T[1\mathinner{.\,.\allowbreak}r]$
is equal to $d$ if $d\leq k$ and is larger than $k$ otherwise.

It follows that to decide whether $r\in\mathsf{aOCC}_{k}^{E}(P_{i},T)$, it
suffices to compute the value $\min\\{d,k+1\\}$, where $d$ is as defined
above.

###### Case 2: $P_{i-1}$ is not $k$-periodic.

In this case, $\mathsf{aOCC}_{k}^{E}(P_{i-1},T)$ is stored as
$\mathcal{O}(k^{3})$ chains of size one. Therefore, we can find the positions
$r^{\prime}$ from Eq. 2 in $\mathcal{O}(k^{3})$ time. Moreover, for each
position $r^{\prime}$, we run the dynamic programming algorithm for
$T[r^{\prime}+1\mathinner{.\,.\allowbreak}]$ and
$P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}]$, which outputs the edit
distance between $T[r^{\prime}+1\mathinner{.\,.\allowbreak}r]$ and
$P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}]$ if it is at most $k$. As
we also know the smallest edit distance between $P_{i-1}$ and a suffix of
$T[1\mathinner{.\,.\allowbreak}r^{\prime}]$, we can compute $d$ in
$\mathcal{O}(k^{3})$ time.

######  Case 3: $P_{i-1}$ and $P_{i}$ are $k$-periodic.

We can identify all positions $r^{\prime}$ from Eq. 2 in $\mathcal{O}(k^{3})$
time. (It suffices to check each of the $\mathcal{O}(k^{3})$ chains that we
store for $P_{i-1}$). We must now test each of these positions. Consider a
position $r^{\prime}$ and let $\mathcal{C}$ be the chain containing it. It
suffices to compute the edit distance between
$P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}]$ and
$T[r^{\prime}+1\mathinner{.\,.\allowbreak}r]$ as we already know the smallest
edit distance from $P_{i-1}$ to a suffix of
$T[1\mathinner{.\,.\allowbreak}r^{\prime}]$. If $|\mathcal{C}|=1$, the
distance has been computed by the dynamic programming algorithm. Otherwise, we
use quasi-greedy encodings. On a high level, our goal is to compute the edit
distance between $\pi=P[\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}]$ and
$\tau=T[r^{\prime}+1\mathinner{.\,.\allowbreak}r]$ via a string
$\mu=D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}]$, where $D$ is the
difference of $\mathcal{C}$ and $\Delta_{i}=\ell_{i}-\ell_{i-1}+k$.

######  Lemma 7.4.

There is $\mathsf{ed}(\pi,\mu)\leq 26k$.

###### Proof.

As $P_{i-1}$ and $P_{i}$ are $k$-periodic, by 7.1 we obtain that
$P_{i}=P[1\mathinner{.\,.\allowbreak}\ell_{i}]$ is $k$-periodic with
$k$-period $Q_{i}=Q_{i-1}$, that is, there is a prefix of $Q_{i}^{\infty}$
such that the edit distance between it and $P_{i}$ is at most $2k$. By Fact
2.3, there is a substring $Q_{i}^{\infty}[r\mathinner{.\,.\allowbreak}t]$ such
that $|r-\ell_{i-1}|\leq 2k$ and $|t-\ell_{i}|\leq 2k$ and
$\mathsf{ed}(Q_{i}^{\infty}[r\mathinner{.\,.\allowbreak}t],\pi)\leq 2k$. By
the triangle inequality, we obtain that
$\mathsf{ed}(Q_{i}^{\infty}[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}],\pi)\leq
6k$. Let $a=\ell_{i-1}-7k\pmod{q_{i}}$ and $b=\ell_{i-1}+7k\pmod{q_{i}}$. By
Corollary 3.5, $D$ is a rotation of $Q_{i-1}=Q_{i}$ with shift $\Delta$, where
$\Delta\in[a-3k,b+3k]$ if $a\leq b$ and $\Delta\in[0,b+3k]\cup[a-3k,q_{i})$ if
$a>b$. It follows that
$D^{\infty}=Q_{i}^{\infty}[s\mathinner{.\,.\allowbreak}]$, where
$|s-\ell_{i-1}|\leq 10k$. As
$\mu=D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}]=Q_{i}^{\infty}[s\mathinner{.\,.\allowbreak}s+\Delta_{i}-1]$,
by the triangle inequality we obtain
$\mathsf{ed}(\mu,Q_{i}^{\infty}[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}])\leq
20k$. Applying the triangle inequality one more time, we obtain the claim. ∎

Let $\mathcal{G}_{P}=\mathsf{qGR}_{30k}(\pi,\mu)$ and
$\mathcal{G}_{T}=\mathsf{qGR}_{30k}(\mu,\tau)$. By Corollary 5.27, knowing
$\mathcal{G}_{P}$ and $\mathcal{G}_{T}$ is sufficient to compute the edit
distance between $\pi$ and $\tau$. Note that we do not know $\mathcal{G}_{T}$
yet, we must compute it using the available information. Let $p$ be the
rightmost position in $\mathcal{C}$.

  1. 1.

Recall that at the position $(p+1)$ we launched an algorithm that is computing
$\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+\Delta_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])$
with a delay of $k$ characters (Corollary 5.22). We have $p+\Delta_{i}\geq
r^{\prime}+\Delta_{i}\geq r$. Therefore, upon reaching $r$, we can use the
memory of the algorithm to compute
$\mathcal{G}_{T,1}=\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}r],D^{\infty}[1\mathinner{.\,.\allowbreak}r-p])$
in $\tilde{\mathcal{O}}(k^{5})$ time and $\tilde{\mathcal{O}}(k^{2})$ space
(Lemma 5.21).

  2. 2.

By the definition of chains,
$T[r^{\prime}+1\mathinner{.\,.\allowbreak}p]=D^{j}$ for some integer $j$. By
Lemma 5.21, we can use $\mathsf{qGR}_{32k}(D,D)$ computed during the
preprocessing step to compute
$\mathcal{G}_{T,2}=\mathsf{qGR}_{32k}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}p],D^{j})$
in $\tilde{\mathcal{O}}(k^{5})$ time and $\tilde{\mathcal{O}}(k^{2})$ space.
By applying Lemma 5.21 again, we can compute
$\mathsf{qGR}_{32k}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}p],D^{j}D^{\infty}[1\mathinner{.\,.\allowbreak}r-p])$
in $\tilde{\mathcal{O}}(k^{5})$ time and $\tilde{\mathcal{O}}(k^{2})$ space.

  3. 3.

Finally, we compute via Corollary 5.22 the encoding
$\mathsf{qGR}_{30k}(\varepsilon,D^{\infty}[r-p+1\mathinner{.\,.\allowbreak}\Delta_{i}])$,
where $\varepsilon$ is the empty string and $\Delta_{i}-(r-p)\leq 2k$. We then
apply 5.20 to compute
$\mathsf{qGR}_{30k+(\Delta_{i}-(r-p))}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}p],D^{j}D^{\infty}[1\mathinner{.\,.\allowbreak}r-p])$
and further Lemma 5.21 to compute
$\mathsf{qGR}_{30k}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}p],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])=\mathcal{G}_{T}$.

##### Updating the chains.

When we detect a new $k$-edit occurrence of $P_{i}$, we must decide if it
should be added to some existing chain or if we must create a new chain for
this occurrence.

To this end, for each $1\leq i\leq z$, we consider $\mathcal{O}(k)$ of its
rotations of $Q_{i}$ that can be the difference of a chain of $k$-edit
occurrences of $P_{i}$ in $T$ (Corollary 3.5). For each rotation $R$, we run a
constant-space and linear-time deterministic pattern matching algorithm [54].
The algorithm processes the text $T$ as a stream and if there is an occurrence
$T[\ell\mathinner{.\,.\allowbreak}r]$ of the rotation reports it while reading
$T[r]$. The algorithm uses $\mathcal{O}(1)$ space and $\mathcal{O}(1)$
amortised time per character of $T$.

Suppose that we detect a new right endpoint $r$ of a $k$-edit occurrence
$T[\ell\mathinner{.\,.\allowbreak}r]$ of $P_{i}$. We must decide whether $r$
belongs to an existing chain of $k$-edit occurrences of $P_{i}$ or starts a
new one. In order to do this, we first find the chain $\mathcal{C}$ that
contains $r-q_{i}+1$ if it exists by checking each chain in turn. We then
check that the smallest edit distance from a suffix of
$T[1\mathinner{.\,.\allowbreak}r]$ to $P_{i}$ equals to
$\mathsf{ed}(\mathcal{C})$ and that $T[r-q_{i}+1\mathinner{.\,.\allowbreak}r]$
is equal to the difference of the chain. (Recall that we run the exact pattern
matching algorithm for each rotation of $Q_{i}$ that can be the difference of
a chain so that both checks can be performed in $\mathcal{O}(1)$ time).

If these conditions are not satisfied, we create a new chain that contains $r$
only. Otherwise, we add $r$ to $\mathcal{C}$ (i.e., increment the size of
$\mathcal{C}$). To finalize the update of the chains, we must delete all
$k$-edit occurrences that become inactive: for each $i$ and for each chain of
$k$-edit occurrences of $P_{i}$, we “delete” the first $k$-edit occurrence if
it starts before $r-\ell_{i}-k+1$. To “delete” a $k$-edit occurrence, we
simply update the endpoints of the first occurrence in the chain and the total
number of occurrences in the chain.

####  7.2.3 Analysis

We summarize the results of this section:

######  Theorem 7.5.

Assume a read-only pattern $P$ of length $m$ and a streaming text $T$ of
length $n$. There is a deterministic algorithm that finds the set
$\mathsf{OCC}_{k}(P,T)$ using $\tilde{\mathcal{O}}(k^{5})$ space and
$\tilde{\mathcal{O}}(k^{6})$ amortised time per character of the text $T$.

###### Proof.

Let us first upper bound the space complexity of the algorithm. For each
$i=1,\ldots,z=\mathcal{O}(\log m)$, we store the set
$\mathsf{aOCC}_{k}(P_{i},T)$ as $\mathcal{O}(k^{3})$ chains. For each chain,
we launch the dynamic programming algorithm (Fact 7.2), which takes
$\tilde{\mathcal{O}}(k^{2})$ space and Corollary 5.22 that takes
$\tilde{\mathcal{O}}(k^{2})$ space. The pattern matching algorithms for the
rotations of $Q_{i}$ take $\tilde{\mathcal{O}}(k)$ space in total. Finally,
testing if a position of the text is the rightmost position of a $k$-edit
occurrence of $P_{i}$ requires $\tilde{\mathcal{O}}(k^{2})$ space.

We now show the time bound. Updating the chains takes $\tilde{\mathcal{O}}(1)$
time. At any time, we run $\tilde{\mathcal{O}}(k^{3})$ instances of Corollary
5.22 that takes $\mathcal{O}(k^{3})$ amortised time per character. To test
each position $r$, we spend $\tilde{\mathcal{O}}(k\cdot k^{3})$ time. ∎

###  7.3 Streaming Algorithm

We now modify the algorithm for the semi-streaming model to develop a fully
streaming algorithm. W.l.o.g., assume $k\leq m$ and take $\delta=1/n^{c}$ for
$c$ large enough.

####  7.3.1 Preprocessing

We define the prefixes $P_{i}$ and their periods $Q_{i}$ exactly in the same
way as in Section 7.2. Recall that $\ell_{i}=|P_{i}|$ and $q_{i}=|Q_{i}|$. For
every $i>1$, we store the following information, where all sketches
$\mathsf{sk}^{\mathsf{q}}$ (6.23) are parametrized by probability $\delta$,
maximal length $\Delta_{i}$, the alphabet of $P$ and $T$, and a seed of
$\mathcal{O}(\log^{2}n\log(1/\delta))$ random bits:

  1. 1.

$P[\ell_{i}]$ and the sketch
$\mathsf{sk}^{\mathsf{q}}_{k}(P[\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}])$;

  2. 2.

For each of rotation $D$ of $Q_{i}$ that can be a difference of a chain of
$k$-edit occurrences of $P_{i}$, the encoding
$\mathsf{qGR}_{30k}(P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])$,
where $\Delta_{i}=\ell_{i}-\ell_{i-1}+k$;

  3. 3.

For each of rotation $D$ of $Q_{i}$ that can be a difference of a chain of
$k$-edit occurrences of $P_{i}$, the sketches
$\mathsf{sk}^{\mathsf{q}}_{32k}(D)$ and
$\mathsf{sk}^{\mathsf{q}}_{32k}(D[1\mathinner{.\,.\allowbreak}\Delta_{i}\pmod{q_{i}}])$.

####  7.3.2 Main Stage

As in Section 7.2, for each $i$, we store $\mathsf{aOCC}_{k}^{E}(P_{i-1},T)$
in $\mathcal{O}(k^{3})$ chains. For each chain $\mathcal{C}$, we store the
leftmost position $lp$ in it, its size $|\mathcal{C}|$, and the smallest edit
distance, $\mathsf{ed}(\mathcal{C})$, from a suffix of
$T[1\mathinner{.\,.\allowbreak}lp]$ to $P_{i-1}$. If $|\mathcal{C}|\geq 2$, we
also store its difference (defined by the shift of the rotation of $Q_{i-1}$).

If $p^{\ast}$ is the first position added to $\mathcal{C}$, then at the
position $(p^{\ast}+1)$, we start running the streaming algorithm of 6.23(a)
for computing the sketch
$\mathsf{sk}^{\mathsf{q}}_{k}(T[p^{a}st+1\mathinner{.\,.\allowbreak}p^{a}st+\Delta_{i}])$.

Furthermore, consider the moment when we detect the second position in
$\mathcal{C}$ (if it exists) and hence the difference $D$ of the chain.
Starting from this moment, for every newly added position $p\in\mathcal{C}$,
at the position $(p+1)$ we start computing the quasi-greedy encoding
$\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+\Delta_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])$
as follows: Assume that we have computed
$\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+\ell\cdot
q_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\ell\cdot q_{i}])$. Suppose
first that $(\ell+1)\cdot q_{i}\leq\Delta_{i}$. While reading $T[p+\ell\cdot
q_{i}+1\mathinner{.\,.\allowbreak}p+(\ell+1)\cdot q_{i}]$, we compute
$\mathsf{sk}^{\mathsf{q}}_{32k}(T[p+\ell\cdot
q_{i}+1\mathinner{.\,.\allowbreak}p+(\ell+1)\cdot q_{i}])$ again via the
algorithm of 6.23(a). We then use this sketch and
$\mathsf{sk}^{\mathsf{q}}_{32k+1}(D)$ to compute
$\mathsf{qGR}_{32k}(T[p+\ell\cdot
q_{i}+1\mathinner{.\,.\allowbreak}p+(\ell+1)\cdot q_{i}],D)$ (6.23(b)) and
then $\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+(\ell+1)\cdot
q_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}(\ell+1)\cdot q_{i}])$ (Lemma
5.21). If $(\ell+1)\cdot q_{i}>\Delta_{i}$, we use the sketches
$\mathsf{sk}^{\mathsf{q}}_{32k}(T[p+\ell\cdot
q_{i}\mathinner{.\,.\allowbreak}p+\Delta_{i}])$ and
$\mathsf{sk}^{\mathsf{q}}_{32k}(D[1\mathinner{.\,.\allowbreak}\Delta_{i}\pmod{q_{i}}])$,
the rest is analogous. We continue running the algorithm until either the
computation is completed or a new $k$-edit occurrence in the chain has been
detected. In other words, in the end we compute the encoding for the rightmost
position in the chain.

##### Detecting new $k$-edit occurrences of $P_{i}$.

We now explain how we modify the algorithm for detecting new $k$-edit
occurrences of the prefixes $P_{i}$. The algorithm for Case 1 does not change.
Instead of the dynamic programming algorithm in Case 2, we use
$\mathsf{sk}^{\mathsf{q}}_{k}$ and use 6.23(b) and then Corollary 5.27 to
compute the edit distance. It remains to explain how we modify the algorithm
for Case 3.

We exploit Eq. 2 again. We can find all positions $r^{\prime}$ in
$\mathcal{O}(k^{3})$ time. To test a position $r^{\prime}$, it suffices to
compute the edit distance between
$P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}]$ and
$T[r^{\prime}+1\mathinner{.\,.\allowbreak}r]$. Let $\mathcal{C}$ be the chain
with difference $D$ that contains $r^{\prime}$. If $|\mathcal{C}|=1$, we use
the edit distance sketch, and otherwise the quasi-greedy encodings. By Lemma
7.4,
$\mathsf{ed}(P[\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])\leq
26k$ and hence by Corollary 5.27, the edit distance between
$P[\ell_{i-1}+1\mathinner{.\,.\allowbreak}\ell_{i}]$ and
$T[r^{\prime}+1\mathinner{.\,.\allowbreak}r]$ can be computed from the
encodings $\mathcal{G}_{P}=\mathsf{qGR}_{30k}(\pi,\mu)$ and
$\mathcal{G}_{T}=\mathsf{qGR}_{30k}(\mu,\tau)$ for
$\pi=P[\ell_{i-1}\mathinner{.\,.\allowbreak}\ell_{i}]$,
$\mu=D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}]$, and
$\tau=T[r^{\prime}+1\mathinner{.\,.\allowbreak}r]$. $\mathcal{G}_{P}$ was
computed during the preprocessing step and we store it explicitly. Hence, we
only need to explain how to compute $\mathcal{G}_{T}$. Let $p$ be the
rightmost position in the chain $\mathcal{C}$.

  1. 1.

Recall that $T[r^{\prime}+1\mathinner{.\,.\allowbreak}p]=D^{j}$ for
$j=(p-r^{\prime})/q_{i}$. We first compute $\mathsf{qGR}_{32k}(D,D)$ from
$\mathsf{sk}^{\mathsf{q}}_{32k}(D,D)$ via 6.23(b), and then
$\mathcal{G}_{T,1}=\mathsf{qGR}_{32k}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}p],D^{j})=\mathsf{qGR}_{32k}(D^{j},D^{j})$
in $\tilde{\mathcal{O}}(k^{5})$ time and $\tilde{\mathcal{O}}(k^{2})$ space as
in Section 7.2.

  2. 2.

At the position $(p+1)$ we launched the streaming algorithm computing
$\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+\Delta_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\Delta_{i}])$
with a delay of $q_{i}$ characters. We have $p+\Delta_{i}\geq
r^{\prime}+\Delta_{i}\geq r$. Therefore, at a position $p+\ell\cdot q_{i}$,
where $\ell=\lfloor(r-p+1)/q_{i}\rfloor$, the algorithm computes
$\mathcal{G}_{T,2}=\mathsf{qGR}_{32k}(T[p+1\mathinner{.\,.\allowbreak}p+\ell\cdot
q_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}\ell\cdot q_{i}])$. The
algorithm then continues to compute the sketch
$\mathsf{sk}^{\mathsf{q}}_{32k}(T[p+\ell\cdot
q_{i}+1\mathinner{.\,.\allowbreak}r])$. We use this sketch and the sketch
$\mathsf{sk}^{\mathsf{q}}_{32k}(D[1\mathinner{.\,.\allowbreak}\Delta_{i}\pmod{q_{i}}])$
to compute $\mathcal{G}_{T,3}=\mathsf{qGR}_{30k}(T[p+\ell\cdot
q_{i}+1\mathinner{.\,.\allowbreak}r],D[1\mathinner{.\,.\allowbreak}\Delta_{i}\pmod{q_{i}}])$
via 6.23(b) and 5.20.

  3. 3.

We finally concatenate $\mathcal{G}_{T,1}$ and $\mathcal{G}_{T,2}$ to obtain
$\mathsf{qGR}_{32k}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}r^{\prime}+(\ell+j)\cdot
q_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}(\ell+j)\cdot q_{i}])$, and then
$\mathsf{qGR}_{32k}(T[r^{\prime}+1\mathinner{.\,.\allowbreak}r^{\prime}+(\ell+j)\cdot
q_{i}],D^{\infty}[1\mathinner{.\,.\allowbreak}(\ell+j)\cdot q_{i}])$ and
$\mathcal{G}_{T,3}$ to obtain $\mathcal{G}_{T}$ via Lemma 5.21 (note that the
difference of lengths of strings in $\mathcal{G}_{T,3}$ is bounded by $2k$).

##### Updating the chains.

When we detect a new $k$-edit occurrence of $P_{i}$, we must decide if it
should be added to some existing chain or if we must create a new chain for
this occurrence. We use the algorithm of Section 7.2, but replace the
constant-space pattern matching algorithm with the streaming pattern matching
algorithm [52] that for a rotation of $Q_{i}$ takes $\tilde{\mathcal{O}}(1)$
space and $\tilde{\mathcal{O}}(1)$ time per character and retrieves all its
occurrences correctly with probability at least $1-\delta$.

####  7.3.3 Analysis

We summarize the results of this section:

######  Theorem 7.6.

Given a pattern $P$ of length $m$ and a text $T$ of length $n$. There is a
streaming algorithm that finds the set $\mathsf{OCC}_{k}^{E}(P,T)$ using
$\tilde{\mathcal{O}}(k^{5})$ space and $\tilde{\mathcal{O}}(k^{8})$ amortised
time per character of the text $T$. The algorithm computes
$\mathsf{OCC}_{k}^{E}(P,T)$ correctly with high probability.

###### Proof.

By Corollary 3.5, for a fixed $i$ only $\mathcal{O}(k)$ rotations of $Q_{i}$
can be a difference of a chain of occurrences of $P_{i}$. The sketch
$\mathsf{sk}^{\mathsf{q}}_{30k+1}(\cdot)$ takes $\tilde{\mathcal{O}}(k^{2})$
space (6.23(a)) and $\mathsf{qGR}_{30k}(\cdot,\cdot)$
$\tilde{\mathcal{O}}(k^{2})$ space as well (Corollary 5.17). Therefore, the
information computed during the preprocessing stage occupies
$\tilde{\mathcal{O}}(k^{3})$ space. During the main stage, we store
$\tilde{\mathcal{O}}(k^{3})$ chains. For each chain, we run the algorithm of
6.23(a) that takes $\tilde{\mathcal{O}}(k^{2})$ space. The algorithm than
computes the quasi-greedy encoding (6.23(b)) takes
$\tilde{\mathcal{O}}(k^{2})$ space as well. In total, the information we store
for the chains occupies $\tilde{\mathcal{O}}(k^{5})$ space. When checking for
new occurrences, we apply Lemmas 5.21 and 5.27, which require an overhead of
$\tilde{\mathcal{O}}(k^{2})$ space. Finally, the streaming pattern matching
algorithms for the rotations of $Q_{i}$ that can be differences of occurrences
of $P_{i}$ take $\tilde{\mathcal{O}}(k)$ space in total. The space bound
follows.

At any time, we run $\tilde{\mathcal{O}}(k^{3})$ instances of the algorithm of
6.23(a) that takes $\tilde{\mathcal{O}}(k)$ amortised time per character. In
addition, for every character we run $\tilde{\mathcal{O}}(k^{3})$ instances of
the algorithms of Lemmas 5.21 and 5.27 taking $\tilde{\mathcal{O}}(k^{8})$
time in total. The pattern matching algorithms for the rotations of $Q_{i}$
take $\tilde{\mathcal{O}}(k)$ time per character.

Note that the only probabilistic procedures in the algorithm are streaming
pattern matching [52] and that of 6.23(b) that computes quasi-greedy
encodings. These procedures are called $\mathrm{poly}(n,k)=\mathrm{poly}(n)$
times. By choosing the constant $c$ in $\delta=1/n^{c}$ large enough, we can
guarantee that the algorithm is correct with high probability by the union
bound. ∎

## References

  * [1] Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams.  Simulating branching programs with edit distance and friends: Or: A polylog shaved is a lower bound made.  In STOC 2016, pages 375––388, 2016.
  * [2] Karl R. Abrahamson.  Generalized string matching.  SIAM J. Comput., 16(6):1039–1051, 1987.  doi:10.1137/0216067.
  * [3] Amihood Amir, Moshe Lewenstein, and Ely Porat.  Faster algorithms for string matching with $k$ mismatches.  Journal of Algorithms, 50(2):257–275, 2004.  URL: https://doi.org/10.1016/S0196-6774(03)00097-X, doi:10.1016/S0196-6774(03)00097-X.
  * [4] Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma.  Streaming algorithms for language recognition problems.  Theor. Comput. Sci., 494:13–23, 2013.
  * [5] Arturs Backurs and Piotr Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  In STOC 2015, pages 51––58, 2015.  doi:10.1145/2746539.2746612.
  * [6] Djamal Belazzougui and Qin Zhang.  Edit distance: Sketching, streaming, and document exchange.  In FOCS 2016, pages 51–60, 2016.  doi:10.1109/FOCS.2016.15.
  * [7] Dany Breslauer and Zvi Galil.  Real-time streaming string-matching.  ACM Trans. Algorithms, 10(4):22:1–22:12, 2014.  doi:10.1145/2635814.
  * [8] Karl Bringmann and Marvin Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In FOCS 2015, pages 79–97, 2015.  doi:10.1109/FOCS.2015.15.
  * [9] Diptarka Chakraborty, Debarati Das, and Michal Koucký.  Approximate online pattern matching in sublinear time.  In FSTTCS 2019, volume 150 of LIPIcs, pages 10:1–10:15, 2019\.  doi:10.4230/LIPIcs.FSTTCS.2019.10.
  * [10] Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký.  Streaming algorithms for embedding and computing edit distance in the low distance regime.  In STOC 2016, pages 712–725, 2016.  doi:10.1145/2897518.2897577.
  * [11] Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat.  Approximating text-to-pattern Hamming distances.  In STOC 2020, pages 643–656, 2020.  URL: https://doi.org/10.1145/3357713.3384266, doi:10.1145/3357713.3384266.
  * [12] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz.  Faster approximate pattern matching: A unified approach.  In FOCS 2020, pages 978–989, 2020.  doi:10.1109/FOCS46700.2020.00095.
  * [13] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya.  Dictionary matching in a stream.  In ESA 2015, volume 9294 of LNCS, pages 361–372, 2015.  doi:10.1007/978-3-662-48350-3\\_31.
  * [14] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya.  The _k_ -mismatch problem revisited.  In SODA 2016, pages 2039–2052, 2016.  doi:10.1137/1.9781611974331.ch142.
  * [15] Raphaël Clifford, Markus Jalsenius, and Benjamin Sach.  Cell-probe bounds for online edit distance and other pattern matching problems.  In SODA 2015, pages 552–561, 2015.  doi:10.1137/1.9781611973730.37.
  * [16] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat.  The streaming k-mismatch problem, 2019.  doi:10.1137/1.9781611975482.68.
  * [17] Richard Cole and Ramesh Hariharan.  Approximate string matching: A simpler faster algorithm.  SIAM J. Comput., 31(6):1761–1782, 2002.  doi:10.1137/S0097539700370527.
  * [18] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou.  Streaming periodicity with mismatches.  In APPROX 2017, pages 42:1–42:21, 2017.
  * [19] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou.  Periodicity in data streams with wildcards.  In CSR 2018, pages 90–105, 2018.  doi:10.1007/978-3-319-90530-3_9.
  * [20] Funda Ergün, Hossein Jowhari, and Mert Sağlam.  Periodicity in streams.  In APPROX 2010, pages 545–559, 2010.  doi:10.1007/978-3-642-15369-3\\_41.
  * [21] N. François, F. Magniez, M. de Rougemont, and O. Serre.  Streaming property testing of visibly pushdown languages.  In ESA 2016, volume 57 of LIPIcs, pages 43:1–43:17, 2016\.
  * [22] Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras.  Automata theory on sliding windows.  In STACS 2018, volume 96 of LIPIcs, pages 31:1–31:14, 2018\.  doi:10.4230/LIPIcs.STACS.2018.31.
  * [23] Moses Ganardi, Danny Hucke, and Markus Lohrey.  Querying regular languages over sliding windows.  In FSTTCS 2016, volume 65 of LIPIcs, pages 18:1–18:14, 2016\.  doi:10.4230/LIPIcs.FSTTCS.2016.18.
  * [24] Moses Ganardi, Danny Hucke, and Markus Lohrey.  Randomized sliding window algorithms for regular languages.  In ICALP 2018, volume 107 of LIPIcs, pages 127:1–127:13, 2018\.  doi:10.4230/LIPIcs.ICALP.2018.127.
  * [25] Moses Ganardi, Danny Hucke, and Markus Lohrey.  Sliding window algorithms for regular languages.  In LATA 2018, volume 10792, pages 26–35, 2018.  doi:10.1007/978-3-319-77313-1\\_2.
  * [26] Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya.  Sliding window property testing for regular languages.  In ISAAC 2019, volume 149 of LIPIcs, pages 6:1–6:13, 2019\.  doi:10.4230/LIPIcs.ISAAC.2019.6.
  * [27] Moses Ganardi, Artur Jeż, and Markus Lohrey.  Sliding windows over context-free languages.  In MFCS 2018, volume 117 of LIPIcs, pages 15:1–15:15, 2018\.  doi:10.4230/LIPIcs.MFCS.2018.15.
  * [28] Paweł Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemyslaw Uznański.  Tight tradeoffs for real-time approximation of longest palindromes in streams.  Algorithmica, 81(9):3630–3654, 2019.  doi:10.1007/s00453-019-00591-8.
  * [29] Paweł Gawrychowski, Jakub Radoszewski, and Tatiana Starikovskaya.  Quasi-periodicity in streams.  In CPM, volume 128 of LIPIcs, pages 22:1–22:14, 2019.  doi:10.4230/LIPIcs.CPM.2019.22.
  * [30] Pawel Gawrychowski and Tatiana Starikovskaya.  Streaming dictionary matching with mismatches.  In CPM 2019, volume 128 of LIPIcs, pages 21:1–21:15, 2019\.  doi:10.4230/LIPIcs.CPM.2019.21.
  * [31] Paweł Gawrychowski and Przemysław Uznański.  Towards unified approximate pattern matching for Hamming and L_1 distance.  In ICALP 2018, volume 107 of LIPIcs, pages 62:1–62:13, 2018\.  doi:10.4230/LIPIcs.ICALP.2018.62.
  * [32] Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat.  The streaming k-mismatch problem: Tradeoffs between space and total time.  In CPM 2020, volume 161 of LIPIcs, pages 15:1–15:15, 2020\.  doi:10.4230/LIPIcs.CPM.2020.15.
  * [33] Shay Golan, Tsvi Kopelowitz, and Ely Porat.  Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams.  In ICALP 2018, volume 107 of LIPIcs, pages 65:1–65:16, 2018\.  doi:10.4230/LIPIcs.ICALP.2018.65.
  * [34] Shay Golan and Ely Porat.  Real-time streaming multi-pattern search for constant alphabet.  In ESA 2017, volume 107 of LIPIcs, pages 41:1–41:15, 2017\.  doi:10.4230/LIPIcs.ESA.2017.41.
  * [35] Tomohiro I.  Longest common extensions with recompression.  In CPM 2017, volume 78 of LIPIcs, pages 18:1–18:15, 2017\.
  * [36] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of $k$-SAT.  Journal of Computer and System Sciences, 62(2):367–375, 2001.  doi:10.1006/jcss.2000.1727.
  * [37] Ce Jin, Jelani Nelson, and Kewen Wu.  An improved sketching bound for edit distance, 2021.  doi:10.4230/LIPIcs.STACS.2021.45.
  * [38] Richard M. Karp and Michael O. Rabin.  Efficient randomized pattern-matching algorithms.  IBM J. of R&D, 31(2):249–260, 1987.
  * [39] Dominik Kempa and Tomasz Kociumaka.  Resolution of the Burrows-Wheeler transform conjecture, 2020.  doi:10.1109/FOCS46700.2020.00097.
  * [40] S. Kosaraju.  Efficient string matching.  1987\.
  * [41] Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt.  Incremental string comparison.  SIAM J. Comput., 27(2):557–582, April 1998.
  * [42] Gad M. Landau and Uzi Vishkin.  Efficient string matching with $k$ mismatches.  Theoretical Computer Science, 43:239–249, 1986.  doi:10.1016/0304-3975(86)90178-7.
  * [43] Gad M. Landau and Uzi Vishkin.  Fast parallel and serial approximate string matching.  J. Algorithms, 10(2):157–169, 1989.  doi:10.1016/0196-6774(89)90010-2.
  * [44] David Levin and Yuval Peres.  Markov Chains and Mixing Times.  American Mathematical Society, 2017.  doi:10.1090/mbk/107.
  * [45] Frédéric Magniez, Claire Mathieu, and Ashwin Nayak.  Recognizing well-parenthesized expressions in the streaming model.  SIAM J. Comput., 43(6):1880–1905, 2014.  doi:10.1137/130926122.
  * [46] William J. Masek and Michael S. Paterson.  A faster algorithm computing string edit distances.  Journal of Computer and System Sciences, 20(1):18–31, 1980.  doi:https://doi.org/10.1016/0022-0000(80)90002-1.
  * [47] O. Merkurev and A. M. Shur.  Searching runs in streams.  In SPIRE 2019, volume 11811 of LNCS, pages 203–220, 2019\.
  * [48] Oleg Merkurev and Arseny M. Shur.  Searching long repeats in streams.  In CPM 2019, volume 128 of LIPIcs, pages 31:1–31:14, 2019\.
  * [49] Gonzalo Navarro.  A guided tour to approximate string matching.  ACM Comput. Surv., 33(1):31–88, March 2001.  doi:10.1145/375360.375365.
  * [50] Noam Nisan.  Pseudorandom generators for space-bounded computation.  Comb., 12(4):449–461, 1992.  doi:10.1007/BF01305237.
  * [51] Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Dynamic index and LZ factorization in compressed space.  Discrete Applied Mathematics, 274:116–129, 2020.  Stringology Algorithms.  doi:https://doi.org/10.1016/j.dam.2019.01.014.
  * [52] Benny Porat and Ely Porat.  Exact and approximate pattern matching in the streaming model.  In FOCS 2009, pages 315–323, 2009.  doi:10.1109/FOCS.2009.11.
  * [53] Jakub Radoszewski and Tatiana Starikovskaya.  Streaming _k_ -mismatch with error correcting and applications.  Journal of Information and Computation, 271:104513, 2020.  doi:10.1016/j.ic.2019.104513.
  * [54] Wojciech Rytter.  On maximal suffixes and constant-space linear-time versions of KMP algorithm.  Theoretical Computer Science, 299(1):763 – 774, 2003.  doi:https://doi.org/10.1016/S0304-3975(02)00590-X.
  * [55] Süleyman Cenk Sahinalp and Uzi Vishkin.  Efficient approximate and dynamic matching of patterns using a labeling paradigm (extended abstract).  In FOCS 1996, pages 320–328, 1996.  doi:10.1109/SFCS.1996.548491.
  * [56] Peter H. Sellers.  The theory and computation of evolutionary distances: Pattern recognition.  Journal of Algorithms, 1(4):359 – 373, 1980.  doi:https://doi.org/10.1016/0196-6774(80)90016-4.