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

Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya

► To cite this version:

Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya. Small space and streaming pattern matching with *k* edits. 2021. hal-03257386

HAL Id: hal-03257386

https://hal.science/hal-03257386

Preprint submitted on 10 Jun 2021

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Small space and streaming pattern matching with *k* edits

Tomasz Kociumaka*¹, Ely Porat², and Tatiana Starikovskaya†³

¹University of California, Berkeley, USA
kociumaka@berkeley.edu

²Bar-Ilan University, Israel
porately@cs.biu.ac.il

³DI/ENS, PSL Research University, France
tat.starikovskaya@gmail.com

Abstract

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

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

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

# 1 Introduction

In the pattern matching problem, given two strings, a *pattern* *P* of length *m* and a *text* *T* of
length *n*, one must find all substrings of the text equal to the pattern. This is a fundamental
problem of string processing with a myriad of applications in such fields as computational
biology, information retrieval, and signal processing, to mention just a few. However, in many

<footnote>*Partly supported by NSF 1652303, 1909046, and HDR TRIPODS 1934846 grants, and an Alfred P. Sloan Fellowship.</footnote>

<footnote>†Partly supported by the grant ANR-20-CE48-0001 from the French National Research Agency (ANR).</footnote>
applications, retrieving substrings that are exactly equal to the pattern is not enough, and one must search for substrings merely *similar* to the pattern. This task, which is often referred to as *approximate pattern matching problem*, can be formalised in the following way: for each position *i* in the text, compute the smallest distance *d*ᵢ between *P* and any substring of *T* that ends at position *i*. In string processing, the two most popular distances are the Hamming distance and the edit distance. Recall that the Hamming distance between two equal-length strings is the number of mismatching pairs of characters of the strings. The edit distance of two strings, not necessarily of equal lengths, is the smallest number of edits (character insertions, deletions, and substitutions) needed to transform one string into the other. Due to its practical importance, the approximate pattern matching problem has been extensively studied in the literature, originally in the classic setting with input strings explicitly stored in memory.

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

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

Similarly to the Hamming distance, one can define the threshold variant of approximate pattern matching, which we refer to as approximate pattern matching with *k* edits. The first algorithm for this variant of the problem was developed by Landau and Vishkin [43]; this by-now classical algorithm solves the problem in $O(nk)$ time. The current best result was achieved by a series of work [55, 17] with the running time (for some range of parameters) $O(n + k^4n/m)$. Very recently, Charalampopoulos et al. [12] studied the problem for both

<footnote n="1">¹Hereafter, $\tilde{O}(\cdot)$ hides a factor of $\text{poly}(\log n)$.</footnote>
distances in the grammar-compressed setting. Their result, in particular, implies an $O(k^4)$-space and $O(nk^4)$-time algorithm for the read-only model, where random access to characters in $P$ and $T$ is allowed and one accounts only for the “extra” space, the space required beyond the space needed to store the pattern and the text.

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

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

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

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

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

## 1.1 Our results

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

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

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

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

# 2 Preliminaries

We assume an integer alphabet $\Sigma = \{1, 2, \dots, \sigma\}$ with $\sigma$ characters. A string $Y$ is a sequence of characters numbered from 1 to $n = |Y|$. By $Y[i]$ we denote the $i$-th symbol of $Y$. For a string $Y$ of length $n$, we denote its reverse $Y[n]Y[n-1]\dots Y[1]$ by $\bar{Y}$. We define $Y[i..j]$ to be equal to $Y[i]...Y[j]$ which we call a fragment of $Y$ if $i \le j$ and to the empty string $\varepsilon$ otherwise. We also use notations $Y[i..j]$ and $Y(i..j]$ which naturally stand for $Y[i]...Y[j-1]$ and $Y[i+1]...Y[j]$, respectively. We call a fragment $Y[1]...Y[j]$ a prefix of $Y$ and use a simplified notation $Y[\dots i]$, and a fragment $Y[i]...Y[n]$ a suffix of $Y$ denoted by $Y[i..]$. We say that $X$ is a substring of $Y$ if $X = Y[i..j]$ for some $1 \le i \le j \le |Y|$. The fragment $Y[i..j]$ is called an occurrence of $X$.

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

We say that a fragment $X[i..i + \ell)$ is a previous factor if $X[i..i + \ell) = X[i'..i' + \ell)$ holds for some $i' \in [1..i)$. The LZ77 factorization of $X$ is a factorization $X = F_1 \cdots F_z$ into non-empty phrases such that the $j$th phrase $F_j$ is the longest previous factor starting at position $1 + |F_1 \cdots F_{j-1}|$; if no previous factor starts there, then $F_j$ consists of a single character. In the underlying LZ77 representation, every phrase $F_j = T[j..j + \ell)$ that is a previous fragment is encoded as $(i', \ell)$, where $i' \in [1..i)$ satisfies $X[i..i + \ell) = X[i'..i' + \ell)$. The remaining length-1 phrases are represented by the underlying character. We use $\text{LZ}(X)$ to denote the underlying LZ77 representation and $|\text{LZ}(X)|$ to denote its size (the number of phrases).

## 2.1 Edit Distance Alignments

The edit distance $\text{ed}(X, Y)$ between two strings $X$ and $Y$ is defined as the smallest number of character insertions, deletions, and substitutions required to transform $X$ to $Y$. The Hamming distance $\text{hd}(X, Y)$ allows substitutions only (and we assume $\text{hd}(X, Y) = \infty$ if $|X| \neq |Y|$).
**Definition 2.1.** A sequence $(x_t, y_t)_{t=1}^m$ is an alignment of $X, Y \in \Sigma^*$ if $(x_1, y_1) = (1, 1)$, $(x_m, y_m) = (|X| + 1, |Y| + 1)$, and $(x_{t+1}, y_{t+1}) \in \{(x_t + 1, y_t + 1), (x_t + 1, y_t), (x_t, y_t + 1)\}$ for $t \in [1..m]^3$

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

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

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

* If $(x_{t+1}, y_{t+1}) = (x_t + 1, y_t + 1)$, we say that $\mathcal{A}$ aligns $X[x_t]$ and $Y[y_t]$, denoted $X[x_t] \sim_{\mathcal{A}} Y[y_t]$. If additionally $X[x_t] = Y[y_t]$, we say that $\mathcal{A}$ matches $X[x_t]$ and $Y[y_t]$, denoted $X[x_t] \simeq_{\mathcal{A}} Y[y_t]$. Otherwise, we say that $\mathcal{A}$ substitutes $X[x_t]$ for $Y[y_t]$.

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

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

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

**Example 2.2.** Consider strings $X = \text{abbaabcb}$ and $Y = \text{acabaabab}$ and a cost-4 alignment

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

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

<figure><img src="image_2.png" /></figure>

Given an alignment $\mathcal{A} = (x_t, y_t)_{t=1}^m$ of $X$ and $Y$, for every $\ell, r \in [1..m]$ with $\ell \le r$, we say that $\mathcal{A}$ aligns $X[x_\ell..x_r)$ and $Y[y_\ell..y_r)$, denoted $X[x_\ell..x_r) \sim_{\mathcal{A}} Y[y_\ell..y_r)$. If there is no breakpoint $(x_t, y_t)$ with $t \in [\ell..r)$, we further say that $\mathcal{A}$ matches $X[x_\ell..x_r)$ and $Y[y_\ell..y_r)$, denoted $X[x_\ell..x_r) \simeq_{\mathcal{A}} Y[y_\ell..y_r)$.

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

**Fact 2.3.** If an alignment $\mathcal{A}$ satisfies $X[x..x') \sim_{\mathcal{A}} Y[y..y')$, then $|x - x'|, |y - y'| \le \text{width}(\mathcal{A})$ and $|(x' - x) - (y' - y)| \le \text{ed}(X[x..x'), Y[y..y')) \le \text{cost}(\mathcal{A}_{[x..x'),[y..y')}) \le \text{cost}(\mathcal{A})$.

# 3 Technical Overview

In this section, we provide an overview of our conceptual and technical contribution. Let us start with a formal statement of the pattern matching with $k$ edits problem. We say that

<footnote n="3">³This definition is rather complex, but it is equivalent to the standard definition given in the textbooks. We chose this particular formulation as it allowed us to introduce notions essential for this work in a rigorous way.</footnote>
$T[\ell..r]$ is a $k$-edit occurrence of $P$ if $\text{ed}(P, T[\ell..r]) \le k$, and we denote the set of the right endpoints of the $k$-edit occurrences of $P$ in $T$ by $\text{OCC}_k^E(P, T)$.

**Problem 3.1** (Pattern matching with $k$ edits). Given a pattern $P$ of length $m$ over an alphabet $\Sigma$, a text $T$ of length $n$ over $\Sigma$, and an integer $k$, compute $\text{OCC}_k^E(P, T)$.

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

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

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

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

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

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

**Definition 3.2 (k-periodic string).** A string $X$ is $k$-periodic if there exists a primitive string $Q$ with $|Q| \le |X|/128k$ such that the edit distance between $X$ and a prefix of $Q^\infty$ is at most $2k$. We call $Q$ a $k$-period of $X$.

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

**Corollary 3.3 (of [12, Theorem 5.1]).** Let $X \in \Sigma^m$, $k \in [1..m]$, and $Y \in \Sigma^n$ with $n \le 2m$. If $X$ is not $k$-periodic, then $|\text{OCC}_k^E(X, Y)| = \mathcal{O}(k^2)$.

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

The difficulty lies in $k$-periodic strings whose occurrences form chains.
**Definition 3.4 (Chain of occurrences).** Consider strings X, Y ∈ Σ* and an integer k ∈ Z≥0.
An increasing sequence of positions p₁, ..., p_c forms a chain of k-edit occurrences of X in Y if:

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

2. there is an integer $k' \in [0 \dots k]$ such that $p_j \in \mathbf{OCC}_k^E(X, Y) \setminus \mathbf{OCC}_{k'-1}^E(X, Y)$ for $j \in [1 \dots c]$.

**Corollary 3.5** (of [12, Theorem 5.2, Claim 5.16, Claim 5.17]). Let $X \in \Sigma^m$, $k \in [1 \dots m]$, and $Y \in \Sigma^n$ with $n \le 2m$. If $X$ is $k$-periodic with period $Q$, then $\mathbf{OCC}_k^E(X, Y)$ can be decomposed into $\mathcal{O}(k^3)$ chains whose differences are of the form $\text{rot}^s(Q)$ with $|m-s| \le 10k$.

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

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

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

**3.2 Greedy Alignments and Encodings**

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

**Capped edit distance:** given $\mathbf{qGR}(X, Y)$, compute $\mathbf{ed}(X, Y)$ or certify that $\mathbf{ed}(X, Y)$ is large;

**Product:** given $\mathbf{qGR}(X, Y)$ and $\mathbf{qGR}(Y, Z)$, retrieve $\mathbf{qGR}(X, Z)$;

**Concatenation:** given $\mathbf{qGR}(X_1, Y_1)$ and $\mathbf{qGR}(X_2, Y_2)$, retrieve $\mathbf{qGR}(X_1 X_2, Y_1 Y_2)$.

Our encoding is parameterized with a threshold $k \in \mathbb{Z}_+$ such that $\mathbf{ed}(\cdot, \cdot) > k$ is considered large, and the goal is to achieve $\tilde{\mathcal{O}}(k^{O(1)})$ encoding size. In fact, whenever $\mathbf{ed}(X, Y) > k$, we shall simply assume that $\mathbf{qGR}_k(X, Y)$ is undefined (formally, $\mathbf{qGR}_k(X, Y) = \perp$). Consequently, products and concatenations will require sufficiently large thresholds in the input encodings so that if either of them is undefined, the output encoding is also undefined.
In order to support concatenations alone, we could use so-called semi-local edit distances. For now, suppose that we only need to encode pairs of equal-length strings.<fnref n="4" /> Through a sequence of concatenations, we may only extend $q\mathbf{GR}_k(X, Y)$ to $q\mathbf{GR}_k(X', Y')$ so that $X = X'[\ell..r)$ and $Y = Y'[\ell..r)$. For any alignment $\mathcal{A}'$ of $X', Y'$ with $\text{cost}(\mathcal{A}') \le k$, consider the induced alignment $\mathcal{A} := \mathcal{A}'_{[\ell..r),[\ell..r)}$. Note that $\mathcal{A}$ mimics the behavior of $\mathcal{A}'$ except that it deletes some characters at the extremes of $X$ and $Y$ (which $\mathcal{A}'$ aligns outside $Y$ and $X$, respectively). By Fact 2.3, we have $\text{cost}(\mathcal{A}) \le k$ and, in particular, $\mathcal{A}$ deletes at most $k$ characters at the extremes of $X$ and $Y$. If, after performing these deletions, we replace $\mathcal{A}$ with an optimal alignment between the remaining fragments of $X$ and $Y$, this modification may only decrease $\text{cost}(\mathcal{A})$ and $\text{cost}(\mathcal{A}')$. Consequently, it suffices to store the $O(k)$ characters at the extremes of $X, Y$ and the $O(k^4)$ edit distances<fnref n="5" /> between long fragments of $X$ and $Y$. In a sense, this encoding represents $O(k^4)$ alignments between $X, Y$ that are sufficient to derive an optimal alignment of any extension.

The main challenge is to handle products, for which we develop a greedy encoding $\mathbf{GR}_k(X, Y)$ that compactly represents the following family $\mathbf{GA}_k(X, Y)$ of greedy alignments of $X, Y$.

**Definition 3.6 (Greedy alignment).** We say that an alignment $\mathcal{A}$ of two strings $X, Y \in \Sigma^*$ is greedy if $X[x] \neq Y[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([1..|X|] \times [1..|Y|])$. Given $k \ge 0$, we denote by $\mathbf{GA}_k(X, Y)$ the set of all greedy alignments $\mathcal{A}$ of $X, Y$ satisfying $\text{cost}(\mathcal{A}) \le k$.

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

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

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

**Definition 3.8.** Let $M$ be a non-crossing matching of strings $X, Y \in \Sigma^*$. We define $X^M, Y^M$ to be the strings obtained from $X, Y$ by replacing $X[x]$ and $Y[y]$ with $\# \notin \Sigma$ for every $(x, y) \in M$. We refer to $\#$ as a dummy symbol and to maximal blocks of $\#$'s as dummy segments.

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

**Lemma 3.9.** Consider strings $X, Y \in \Sigma^*$, an integer $k \ge \text{ed}(X, Y)$, and a set $M \subseteq M_k(X, Y)$. Then, $\text{ed}(X, Y) = \text{ed}(\text{num}(X^M), \text{num}(Y^M))$ and $M_k(X, Y) = M_k(\text{num}(X^M), \text{num}(Y^M))$.

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

**Lemma 3.10.** Let $M = M_k(X, Y)$ for strings $X, Y \in \Sigma^*$ and a positive integer $k \ge \text{ed}(X, Y)$. Then, $|\text{LZ}(X^M)|, |\text{LZ}(Y^M)| = O(k^2)$, and $X^M, Y^M$ contain $O(k)$ dummy segments.

<footnote n="4">⁴Pairs of strings of any lengths can be supported in the same way provided that concatenations require larger input thresholds (compared to the output threshold) to accommodate length differences.</footnote>

<footnote n="5">⁵In fact, $O(k^2)$ edit distances suffice and they can be encoded in $O(k)$ space using techniques of Tiskin [58].</footnote>
Consequently, for $k \ge \text{ed}(X, Y)$, we could define the greedy encoding $\text{GR}_k(X, Y)$ so that it consists of $\text{LZ}(X^M)$ and $\text{LZ}(Y^M)$. Instead, we use a more powerful compressed representation (developed in Section 4) that supports more efficient queries concerning $X^M$ and $Y^M$.

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

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

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

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

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

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

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

## 3.3 Edit Distance Sketches

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

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

**Definition 3.14 (Complete walk).** For a string $S \in \Sigma^*$, we say that $(s_t)_{t=1}^{m+1}$ is an m-step complete walk over $S$ if $s_1 = 1$, $s_{m+1} = |S| + 1$, and $s_{t+1} \in \{s_t, s_t + 1\}$ for $t \in [1..m]$.
For any two strings $X, Y \in \Sigma^*$, the two walks underlying CGK($X$) and CGK($Y$) can be interpreted as an edit distance alignment using the following abstract definition:

**Definition 3.15 (Zip alignment).** The zip alignment of $m$-step complete walks $(x_t)_{t=1}^{m+1}$ and $(y_t)_{t=1}^{m+1}$ over $X, Y \in \Sigma^*$ is obtained by removing repeated entries in $(x_t, y_t)_{t=1}^{m+1}$.

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

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

$$ \Pr_r [\mathcal{A}_W \in \mathrm{GA}_{c \cdot \mathrm{ed}(X,Y)^2}(X,Y) \text{ and width}(\mathcal{A}_W) \le c \cdot \mathrm{ed}(X,Y)] \ge 1 - \delta. $$

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

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

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

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

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

With each forward context $X[x_t..x'_t)$ retrieved, we also need to determine the value $x_t$ (so that we know which fragment of $X$ we can learn from $\mathrm{CE}(X)[t]$). To avoid knock-on effects, we actually store differences $x_t - x_u$ with respect to the previous index satisfying $\mathrm{CE}(X)[u] \ne \perp$. This completes the intuitive description of the context encoding $\mathrm{CE}$ studied in Section 6.2.

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

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

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

(b) There exists an $\tilde{O}(k^2)$-space decoding algorithm that, given $\mathrm{sk}_k^E(X), \mathrm{sk}_k^E(Y)$ for $X, Y \in \Sigma^{\le n}$, with probability at least $1-\delta$ outputs $\mathrm{GR}_k(X, Y)$ and $\min(\mathrm{ed}(X, Y), k+1)$. Retrieving $\mathrm{GR}_k(X, Y)$ costs $\tilde{O}(k^5)$ time, whereas computing $\min(\mathrm{ed}(X, Y), k+1)$ costs $\tilde{O}(k^3)$ time.
# 4 Compressed String Representation

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

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

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

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

(a) retrieve $n = |X|$, in $O(1)$ time;

(b) given $i \in [1..n]$, retrieve $X[i]$, in $O(\log n)$ time;

(c) given $i, j \in [1..n]$, compute $LCE(X[i..n], X[j..n])$, in $O(\log n)$ time;

(d) given $i, j \in [1..n]$, compute $LCE(\bar{X}[i..n], \bar{X}[j..n])$, in $O(\log n)$ time;

(e) compute $LZ(X)$, in $O(z \log^4 n)$ time;

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

(g) given $i, j \in [1..n]$ with $i \le j$, compute $D(X[i..j])$, in $O(z \log^4 n)$ time.

Moreover, $D(X)$ can be constructed:

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

(i) in $O(z \log^4 n)$ time given $D(X[1..i])$ and $D(X[i..n])$ for some $i \in [1..n]$.

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

A straight-line grammar is a tuple $G = (S, \Sigma, \text{rhs}, S)$, where $S$ is a finite set of symbols, $\Sigma \subseteq S$ is a set of terminal symbols, $\text{rhs} : (S \setminus \Sigma) \to S^*$ is the production (or right-hand side) function, and $S \in S$ is the start symbol. We further require existence of an order $\prec$ on $S$ such that $B \prec A$ if $B$ occurs in $\text{rhs}(A)$.

The expansion function $\exp : S \to \Sigma^+$ is defined recursively:

$$ \exp(A) = \begin{cases} A & \text{if } A \in \Sigma, \\ \exp(B_1) \cdots \exp(B_k) & \text{if } \text{rhs}(A) = B_1 \cdots B_k, \end{cases} $$

We say that $G$ is a grammar-compressed representation of $\exp(S)$.

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

Each node $\nu$ of $T(A)$ is associated with an occurrence $\exp(\nu)$ of $\exp(s(\nu))$ in $\exp(A)$. For the root $\rho$, we define $\exp(\rho) = \exp(A)[1..|\exp(A)|]$ to be the whole $\exp(A)$. Moreover, if $\exp(\nu) = \exp(A)[\ell..r)$, $\text{rhs}(s(\nu)) = B_1 \cdots B_k$, and $\nu_1, \dots, \nu_k$ are the children of $\nu$, then $\exp(\nu_i) = \exp(A)[r_{i-1}..r_i)$, where $r_i = \sum_{j=1}^i |\exp(B_j)|$ for $0 \le i \le k$. This way, the fragments $\exp(\nu_i)$ form a partition of $\exp(\nu)$, and $\exp(\nu_i)$ is indeed an occurrence $\exp(s(\nu_i))$ in $\exp(A)$.

A straight-line program (SLP) is a straight-line grammar $G = (S, \Sigma, \text{rhs}, S)$ such that $|\text{rhs}(A)| = 2$ holds for each nonterminal $A \in S \setminus \Sigma$. In a run-length straight-line program (RLSLP), productions of the form $\text{rhs}(A) = B^k$, with $B \in S$ and $k \in \mathbb{Z}_{\ge 2}$, are also allowed.
An RLSLP $\mathcal{G}$ of size $g$ (with $g$ symbols) representing a string of length $n$ can be stored in $\mathcal{O}(g)$ space ($\mathcal{O}(g \log(n+g))$ bits) with each non-terminal $A \in \mathcal{S} \setminus \Sigma$ storing $\text{rhs}(A)$ (represented by $(B, k)$ if $\text{rhs}(A) = B^k$) and $|\exp(A)|$. This representation allows for efficiently traversing the parse tree $\mathcal{T}_{\mathcal{G}}$: given a node $\nu$ represented as a pair $(s(\nu), \exp(\nu))$, it is possible to retrieve in constant time an analogous representation of any child of $\nu$.

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

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

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

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

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

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

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

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

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

(b) Here, an intermediate goal is to construct a sequence $(A_1, m_1), \dots, (A_t, m_t)$ with $A_p \in \mathcal{S}$ and $m_p \in \mathbb{Z}_{\ge 1}$ such that $\exp(A_1)^{m_1} \cdots \exp(A_t)^{m_t} = X[i \dots j]$ and $t = \mathcal{O}(g)$. We only visit nodes $\nu$ such that $\exp(\nu)$ intersects $X[i \dots j]$.

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

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

The number of visited nodes is proportional to the height of $\mathcal{G}$ and thus this traversal takes $\mathcal{O}(g)$ time. In the post-processing, for each pair $(A_p, m_p)$, we create a new symbol $B_p$ with $\text{rhs}(B_p) = A_p^{m_p}$ (if $m_p \ge 2$) or set $B_p$ as an alias of $A_p$ (if $m_p = 1$). Next, we set $C_1$ to be an alias of $B_1$ and, for $p \in [2..t]$, create a new symbol $C_p$ with $\text{rhs}(C_p) = C_{p-1}B_{p-1}$. Finally, we return the extended RLSLP with $C_t$ as the new starting symbol. $\square$

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

**Access:** Given $i \in [1..n]$, retrieve $S[i]$;

**LCE queries:** Given $i, j \in [1..n]$, compute $\text{LCE}(S[i..n], S[j..n])$.

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

To implement (h), we first use [39, Theorem 6.1] and build a size-$\mathcal{O}(f \log n)$ SLP representing $X$ or $\bar{X}$. By reversing the right-hand sides of all the productions, we obtain an analogous SLP representing $\bar{X}$ or $X$, respectively. Finally, we pass these SLPs to the construction algorithm of Theorem 4.4. Overall, the running time is $\mathcal{O}(f \log^2 n)$.
In (i), given $D(X[1..i])$ and $D(X[i..n])$, we convert the underlying RLSLPs to LZ-like representations (Fact 4.3), concatenate them into an $O(g^* \log n)$-phrase LZ-like representation of $X$, and apply (h). Overall, this takes $O(g^* \log^3 n) = O(z \log^4 n)$ time.

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

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

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

# 5 Greedy Alignments and Encodings

**Definition 3.6 (Greedy alignment).** We say that an alignment $\mathcal{A}$ of two strings $X, Y \in \Sigma^*$ is greedy if $X[x] \neq Y[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([1..|X|] \times [1..|Y|])$. Given $k \ge 0$, we denote by $\text{GA}_k(X, Y)$ the set of all greedy alignments $\mathcal{A}$ of $X, Y$ satisfying $\text{cost}(\mathcal{A}) \le k$.

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

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

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

* If $y_j < y_{j+1}$, we define an alignment $\mathcal{A}' = (x'_t, y'_t)_{t=1}^m$ obtained from $\mathcal{A}$ by incrementing $x_t$ for $t \in (i..j]$. Moreover, $\mathcal{B}(\mathcal{A}) \setminus \mathcal{B}(\mathcal{A}') \subseteq \{(x_t, y_t) : t \in [i..j)\}$ and $\mathcal{B}(\mathcal{A}') \setminus \mathcal{B}(\mathcal{A}) = \{(x'_t, y'_t) : t \in (i..j]\}$, so $\text{cost}(\mathcal{A}') \le \text{cost}(\mathcal{A})$. Furthermore, $\sum_{t=1}^m (x'_t + y'_t) = j - i + \sum_{t=1}^m (x_t + y_t)$, contradicting the choice of $\mathcal{A}$ as an optimal alignment maximizing $\sum_{t=1}^m (x_t + y_t)$. □

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

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

of common matches of all alignments $\mathcal{A} \in \text{GA}_k(X, Y)$; note that it forms a non-crossing matching of $X, Y$.

**Definition 3.8.** Let $M$ be a non-crossing matching of strings $X, Y \in \Sigma^*$. We define $X^M, Y^M$ to be the strings obtained from $X, Y$ by replacing $X[x]$ and $Y[y]$ with $\# \notin \Sigma$ for every $(x, y) \in M$. We refer to $\#$ as a dummy symbol and to maximal blocks of $\#$'s as dummy segments.

Additionally, for a string $Z \in (\Sigma \cup \#)^*$, we define $\text{num}(Z)$ as a string obtained from $Z$ by replacing the $i$th leftmost occurrence of $\#$ in it with a unique dummy symbol $\#_i \notin \Sigma$.
**Fact 5.1.** Let $X, Y \in \Sigma^*$. For each non-crossing matching $M$ of $X, Y$, we have $\text{ed}(X, Y) \le \text{ed}(\text{num}(X^M), \text{num}(Y^M))$.

*Proof.* For every $(x, y) \in [1..|X|] \times [1..|Y|]$, if $\text{num}(X^M)[x] = \text{num}(Y^M)[y]$, then $X[x] = Y[y]$. Thus, $\text{cost}_{X,Y}(\mathcal{A}) \le \text{cost}_{\text{num}(X^M),\text{num}(Y^M)}(\mathcal{A})$ holds for all alignments $\mathcal{A}$ of $X, Y$. $\square$

**Lemma 3.9.** Consider strings $X, Y \in \Sigma^*$, an integer $k \ge \text{ed}(X, Y)$, and a set $M \subseteq \mathcal{M}_k(X, Y)$. Then, $\text{ed}(X, Y) = \text{ed}(\text{num}(X^M), \text{num}(Y^M))$ and $\mathcal{M}_k(X, Y) = \mathcal{M}_k(\text{num}(X^M), \text{num}(Y^M))$.

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

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

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

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

Overall, we conclude that $\text{GA}_k(X, Y) = \text{GA}_k(X', Y')$ and that every alignment $\mathcal{A}$ in this family satisfies both $\mathcal{M}_{X,Y}(\mathcal{A}) = \mathcal{M}_{X',Y'}(\mathcal{A})$ and $\text{cost}_{X,Y}(\mathcal{A}) = \text{cost}_{X',Y'}(\mathcal{A})$. Consequently, $\mathcal{M}_k(X, Y) = \mathcal{M}_k(X', Y')$ and, due to Fact 3.7, $\text{ed}(X, Y) = \text{ed}(X', Y')$. $\square$

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

1. $\text{rank}_\#(S, i):$ Given $i \in [1..n+1]$, return $|\{i' \in [1..i) : S[i'] = \#\}|$.

2. $\text{select}_\#(S, j):$ Given $j \in [1..\text{rank}_\#(S, n)]$, return the jth smallest element of $\{i \in [1..n] : S[i] = \#\}$.
**Proof.** For each dummy segment $S[\ell..r)$, the data structure stores a tuple $(\ell, r, \text{rank}_{\#}(S, \ell))$. These tuples are stored in a sorted array (note that the order is the same for all coordinates). To compute $\text{rank}_{\#}(S, i)$, we binary search for the rightmost segment $S[\ell^*..r^*)$ such that $\ell^* \le i$. If there is no such segment, we return $\text{rank}_{\#}(S, i) = 0$. Otherwise, $\text{rank}_{\#}(S, i) = \text{rank}_{\#}(S, \ell^*) + \min(i, r^*) - \ell^*$.

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

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

$$ E^M(X, Y) := (\mathcal{D}(X^M Y^M), \text{RS}_{\#}(X^M), \text{RS}_{\#}(Y^M)). $$

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

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

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

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

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

## 5.1 Greedy Encoding and Its Size

**Definition 5.6.** For strings $X, Y \in \Sigma^*$ and an integer $k$, we define the greedy encoding

$$ \text{GR}_k(X, Y) = \begin{cases} E^{\mathcal{M}_k(X, Y)}(X, Y) & \text{if } k \ge \text{ed}(X, Y), \\ \perp & \text{otherwise.} \end{cases} $$

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

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

As $\text{ed}(X, Y) \le k$, by Fact 3.7 $\text{GA}_k(X, Y) \ne \emptyset$, and therefore there is an alignment $A \in \text{GA}_k(X, Y)$ of cost at most $k$ between $X$ and $Y$. We consider yet another graphical representation of an alignment. Namely, we represent $A$ as a set of at most $k$ horizontal segments, where a horizontal segment $I = [i..j; \Delta]$ from $(i, \Delta)$ to $(j, \Delta)$ means that $X[i..j] \simeq_A Y[i + \Delta..j + \Delta]$ (see Fig. 1). This representation induces a partitioning of $X = f_1 \cdots f_z$, where $z = \mathcal{O}(k)$, and each factor $f_\ell$ is either a single character deleted under $A$ or a fragment $X[i..j]$ corresponding to a horizontal segment $I = [i..j; \Delta]$.
<figure><img src="image_3.png" /></figure>

Alignment $\mathcal{A}$.

<figure><img src="image_4.png" /></figure>

Alignment $\mathcal{A}''$.

<figure><img src="image_5.png" /><figcaption>Figure 1: Graphical representations of two greedy alignments $\mathcal{A}, \mathcal{A}'' \in \text{GA}_5(X, Y)$, where $X = \text{abababcabcbc}$ and $Y = \text{abbabcabcbc}$. The alignment $\mathcal{A}$ (red) has cost 1 (we delete $X[3]$), and the alignment $\mathcal{A}''$ cost 5 (we delete $X[5], X[10], X[11], Y[3], Y[6]$). The alignments imply that $X[6..9] = Y[7..10] = X[8..11]$.</figcaption></figure>

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

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

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

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

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

The claim follows.

<figure><img src="image_6.png" /></figure>

**Corollary 5.7.** For every $X, Y \in \Sigma^{\le n}$ and $k \in \mathbb{Z}_+$, the encoding $\text{GR}_k(X, Y)$ takes $\mathcal{O}(k^2 \log^2 n)$ space.

*Proof.* Follows immediately from Propositions 4.2 and 5.2 and Lemma 3.10. $\square$

<figure><img src="image_7.png" /></figure>

**5.2 Construction of greedy encodings**

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

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

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

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

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

**Claim 5.8.** *There are alignments $\mathcal{A}, \mathcal{A}' \in \text{GA}_k(X, Y)$ such that $X[a \dots a + 9k^2) \cong_{\mathcal{A}} Y[i \dots i + 9k^2) \cong_{\mathcal{A}'} X[b \dots b + 9k^2)$ holds for some positions $a \neq b$.*

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

Next, consider $k+1$ disjoint parts of $Y[s+k \dots t-k)$, each of length $9k^2 \le (21k^3-1-2k)/(k+1)$. By Fact 2.3, $\mathcal{A}$ aligns the entire $Y[s+k \dots t-k)$ without mismatches to a fragment of $X[s \dots t)$.

<footnote n="6">⁶The authors would like to thank Panagiotis Charalampopoulos for an early write-up of the proof of this lemma, which was originally meant to be included into [12].</footnote>
Moreover, $\mathcal{A}'$ aligns at least one part without mismatches. Denote this part $Y[i..i+9k^2)$, and fix positions $a, b$ so that $X[a..a+9k^2) \simeq_{\mathcal{A}} Y[i..i+9k^2) \simeq_{\mathcal{A}'} X[b..b+9k^2)$. Note that $a \in [s..t)$ and thus $X[a..t) \simeq_{\mathcal{A}} Y[i..t')$. Now, if $a = b$, then we would have $X[a] \simeq_{\mathcal{A}'} Y[i]$ and the greedy nature of $\mathcal{A}'$ would guarantee $X[a..t) \simeq_{\mathcal{A}'} Y[i..t')$, contradicting $X[t-1] \not\simeq_{\mathcal{A}'} Y[t'-1]$. Consequently, $a \neq b$. $\square$

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

**Claim 5.9.** For every $\mathcal{A}'' \in \text{GA}_k(X, Y)$, we have $X[i+3k^2..i+8k^2) \simeq_{\mathcal{A}''} Y[v..v+5k^2)$ for some $v \in [i+2k^2..i+4k^2]$.

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

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

Algorithm 1 is the key procedure for computing greedy encodings.

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

*Proof.* To show correctness of Algorithm 1, consider an (imaginary set) of alignments $\mathcal{G}$ generated by the algorithm. First, associate with each point in $[1..|X|] \times [1..|Y|]$ an empty set of alignments. Let $(x, y)$ be the latest point extracted from $Q$ and $\mathcal{G}[(x, y)]$ the set of alignments associated with it. In line 7 (if the algorithm executes it), we create a new set of alignments containing all alignments in $\mathcal{G}[(x, y)]$ extended by $(x+1, y)$ (deletion of $X[x]$), $(x+1, y)$, $(x+2, y+1)$, ..., $(x+\ell, y+\ell-1)$, where $\ell = \text{LCE}(X[x+1..], Y[y..])$ (matching of $X[x+1..x+\ell]$ and $Y[y..y+\ell-1]$). We union the resulting set of alignments with $\mathcal{G}[x+\ell, y+\ell-1]$ and push $(x+\ell, y+\ell-1)$ to $Q$. In lines 9 and 11 we process $\mathcal{G}[(x, y)]$ analogously. Finally, we define $\mathcal{G} = \mathcal{G}[|X|, |Y|]$. We claim that $\mathcal{G} = \text{GA}_k(X, Y)$. First note that all alignments in $\mathcal{G}$ are greedy by construction: an alignment can only delete $X[x]$, $Y[y]$, or substitute $X[x]$ for $Y[y]$ if $X[x] \neq Y[y]$. In other words, for every breakpoint $(x, y)$ we have $X[x] \neq Y[y]$. Additionally, the cost of every alignment in $\mathcal{G}$ is at most $k$ as at each call of GreedyMatch credit decreases by one. Hence, $\mathcal{G} = \text{GA}_k(X, Y)$.
1 Greedy($k$)
2 $Q = \emptyset$;
3 GreedyMatch($Q, 1, 1, k$);
4 while $Q$ is not empty do
5 ($x, y$), credit = $Q$.extract-min();
6 if $x \le |X|$ then
7 GreedyMatch($Q, x + 1, y, credit - 1$); // delete $X[x]$
8 if $y \le |Y|$ then
9 GreedyMatch($Q, x, y + 1, credit - 1$); // delete $Y[y]$
10 if $x \le |X|$ and $y \le |Y|$ then
11 GreedyMatch($Q, x + 1, y + 1, credit - 1$); // substitute $X[x]$ for $Y[y]$
12 GreedyMatch($Q, x, y, credit$):
13 if $\text{ed}(X[x..], Y[y..]) \le credit$ then
14 $\ell = \text{LCE}(X[x..], Y[y..])$; // match $X[x]$ and $Y[y]$, ..., $X[x + \ell - 1]$ and $Y[y + \ell - 1]$
15 $x = x + \ell; y = y + \ell$;
16 Push($Q, (x, y), credit$);
17 if $|Q| = 1$ then output $[x - \ell, x - 1]$;
18 Push($Q, (x, y), credit$)
19 if $(x, y) \notin Q$ then $Q[(x, y)] = credit$;
20 else $Q[(x, y)] = \max\{Q[(x, y)], credit\}$; // points are ordered lexicographically.

<caption>**Algorithm 1:** The algorithm receives as an input strings $X, Y$, and integer $k$. Lexicographic order on points is defined in the following way: $(x_1, y_1) < (x_2, y_2)$ if either $x_1 < x_2$ or $x_1 = x_2$ and $y_1 < y_2$.</caption>

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

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

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

3. If $Q$ contains points $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ such that $x_1 - y_1 = x_2 - y_2$, then $p_1 = p_2$.

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

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

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

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

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

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

1. $\mathcal{B}(\mathcal{G})$ does not contain any points with the $x$-coordinate in $[x..x']$ or the $y$-coordinate in $[y..y']$;

2. $\mathcal{B}(\mathcal{G})$ contains $q = (x' + 1, y' + 1)$;

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

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

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

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

**Claim 5.11.** Given two strings $U, V$, and a data structure of size $s$ that can answer the LCE queries on the suffixes of $\overline{U}, \overline{V}$ in $t$ time. We can build in $O(k^2t)$ time a data structure that occupies $O(k^2)$ space and can retrieve $\min(k + 1, \text{ed}(U[u..], V[v..]))$ in $O(\log n)$ time.
**Proof.** The data structure is based on the Landau–Myers–Schmidt algorithm [41]. Consider a table $D$ of size $|U| \times |V|$ such that $D[i, j] = \text{ed}(U[|U| - i + 1..], V[|V| - j + 1..]) = \text{ed}(\bar{U}[1..i], \bar{V}[1..j])$. By Fact 2.3, if $D[i, i + \delta] \le h$, then $-h \le \delta \le h$. Let $L^h(\delta) = \max\{i : D[i, i + \delta] \le h\}$. The data structure consists of $2k + 1$ sorted arrays containing $L^0(\delta), L^1(\delta), \dots, L^k(\delta)$, $-k \le \delta \le k$. The arrays occupy $\mathcal{O}(k^2)$ space and allow to retrieve $\text{ed}(U[u..], V[v..])$ in $\tilde{\mathcal{O}}(1)$ time by simple binary search. The data structure can be computed via the following recurrence, where $\text{SLIDE}_\delta(u) = u + \text{LCE}(\bar{U}[u..], \bar{V}[u + \delta..])$.

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

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

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

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

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

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

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

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

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

## 5.3 Concatenations and Quasi-greedy Alignments

**Definition 5.14 (Quasi-greedy alignment).** We say that an alignment $\mathcal{A}$ of two strings $X, Y \in \Sigma^*$ is quasi-greedy if it satisfies at least one of the following symmetric conditions:

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

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

Given $k \ge 0$, we denote by $\mathbf{qGA}_k(X, Y)$ the set of all quasi-greedy alignments $\mathcal{A}$ of $X, Y$ with $\mathrm{cost}(\mathcal{A}) \le k$.

**Lemma 5.15.** Consider an alignment $\mathcal{A} \in \mathbf{qGA}_k(X_pX_s, Y_pY_s)$, where $X_p, X_s, Y_p, Y_s \in \Sigma^*$ and $k \in \mathbb{Z}_{\ge 0}$. Then, $\mathcal{A}_{[1..|X_p|+1], [1..|Y_p|+1]} \in \mathbf{qGA}_{k+||X_s|-|Y_s||}(X_p, Y_p)$ and $\mathcal{A}_{[|X_p|+1..],[|Y_p|+1..]} \in \mathbf{qGA}_{k+||X_p|-|Y_p||}(X_s, Y_s)$.

*Proof.* For brevity, let $X = X_pX_s, Y = Y_pY_s$; $n_p = |X_p|, n_s = |X_s|, n = |X|, m_p = |Y_p|, m_s = |Y_s|, m = |Y|$.

Let $\mathcal{A} = (x_t, y_t)_{t=1}^q$ and let $(x_{i_p}, y_{i_p})$ be the leftmost pair $(x, y) \in \mathcal{A}$ such that $x > n_p$ or $y > m_p$. By symmetry, we assume without loss of generality that $x_{i_p} = n_p + 1$; see Fig. 2. Observe that $\mathcal{A}_p := \mathcal{A}_{[1..n_p+1], [1..m_p+1]}$ is the union of $(x_t, y_t)_{t=1}^{i_p-1}$ and $(n_p + 1, y)_{y=y_{i_p}}^{m_p+1}$. Furthermore, $\mathcal{B}(\mathcal{A}_p) = \{(x_t, y_t) \in \mathcal{B}(\mathcal{A}) : t \in [1..p]\} \cup \{(n_p + 1, y) : y \in [y_p..m_p+1]\}$. Let $k_p$ be the size of the former component. Then, $k \ge \mathrm{cost}(\mathcal{A}) \ge k_p + \mathrm{ed}(X_s, Y_p[y_{i_p}..]Y_s) \ge k_p + |Y_p[y_{i_p}..]| + m_s - n_s$, so that $\mathrm{cost}(\mathcal{A}_p) = k_p + |Y_p[y_{i_p}..]| \le k + n_s - m_s \le k - \frac{|X_s| - |Y_s|}{2}$. It remains to prove that $\mathcal{A}_p$ is a quasi-greedy alignment. By Definition 3.6 applied to $\mathcal{A}$, we have two possibilities:

* There exists $\delta \in [1..n+1]$ such that $(\delta, 1) \in \mathcal{A}$ and $X[x] \ne Y[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([\delta..n] \times [1..m])$. If $\delta \le n_p+1$, then we also have that $(\delta, 1) \in \mathcal{A}_p$ and $X_p[x] \ne Y_p[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}_p) \cap ([\delta..n_p] \times [1..m_p])$. Otherwise, $(x_{i_p}, y_{i_p}) = (n_p+1, 1) \in \mathcal{A}_p$, so $\mathcal{A}_p$ is trivially quasi-greedy.

* There exists $\delta \in [1..m+1]$ such that $(1, \delta) \in \mathcal{A}$ and $X[x] \ne Y[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([1..n] \times [\delta..m])$. If $\delta \le y_{i_p}$, then we also have that $(1, \delta) \in \mathcal{A}_p$ and $X_p[x] \ne Y_p[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}_p) \cap ([1..n_p] \times [\delta..m_p])$. Otherwise, $n_p = 0$ because $(1, \delta)$ cannot cross $(n_p+1, y_p)$. Hence, $\mathcal{A}_p$ is trivially quasi-greedy.

Now, let $(x_{i_s}, y_{i_s})$ be the leftmost pair $(x, y) \in \mathcal{A}$ such that $x > n_p$ and $y > m_p$. By symmetry, we assume without loss of generality that $y_{i_s} = m_p + 1$; see Fig. 2. Observe that $\mathcal{A}_s := \mathcal{A}_{[n_p+1.., [m_p+1..]}$ is the union of $(x, 1)_{x=1}^{x_{i_s}-n_p-1}$ and $(x_t - n_p, y_t - m_p)_{t=i_s}^q$. Furthermore, $\mathcal{B}(\mathcal{A}_s) = \{(x_t - n_s, y_t - m_s) \in \mathcal{B}(\mathcal{A}) : t \in [i_s..q]\} \cup \{(x, 1) : x \in [1..x_{i_s}-n_p]\}$. Let $k_s$ be the size of the former component. Then, $k \ge \mathrm{cost}(\mathcal{A}) \ge k_s - 1 + \mathrm{ed}(X_pX_s[1..x_{i_s}-n_p], Y_p) \ge k_s - 1 + x_{i_s} - m_p$, so that $\mathrm{cost}(\mathcal{A}_s) = k_s - 1 + x_{i_s} - n_p \le k + m_p - n_p \le k - \frac{|X_p| - |Y_p|}{2}$. It remains to prove that $\mathcal{A}_s$ is a quasi-greedy alignment. By Definition 3.6 applied to $\mathcal{A}$, we have two possibilities:

* There exists $\delta \in [1..n+1]$ such that $(\delta, 1) \in \mathcal{A}$ and $X[x] \ne Y[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([\delta..n] \times [1..m])$. If $\delta \le x_{i_s}$, then $(x_{i_s} - n_p, 1) \in \mathcal{A}_s$ and $X_s[x] \ne Y_s[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}_s) \cap ([x_{i_s} - n_p..n_s] \times [1..m_s])$. Otherwise, $(\delta - n_p, 1) \in \mathcal{A}_s$ and $X_s[x] \ne Y_s[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}_s) \cap ([\delta - n_p..n_s] \times [1..m_s])$.

* There exists $\delta \in [1..m+1]$ such that $(1, \delta) \in \mathcal{A}$ and $X[x] \ne Y[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([1..n] \times [\delta..m])$. If $\delta \le m_p+1$, then $(x_{i_s} - n_p, 1) \in \mathcal{A}_s$ and $X_s[x] \ne Y_s[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}) \cap ([x_{i_s} - n_p..n_s] \times [1..m_s])$. Otherwise, $x_{i_s} = 1$ and $n_p = 0$.
because $(1, \delta)$ cannot cross $(x_{i_s}, m_p + 1)$. Hence, $(1, \delta - m_p) \in \mathcal{A}$ and $X_s[x] \neq Y_s[y]$ holds for every $(x, y) \in \mathcal{B}(\mathcal{A}_s) \cap ([1..n_s] \times [\delta - m_p..m_s])$. $\square$

<figure><img src="image_8.png" /><figcaption>Figure 2: Alignment $\mathcal{A} \in \mathbf{qGA}_k(X_pX_s, Y_pY_s)$.</figcaption></figure>

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

$$ \mathbf{qM}_k(X, Y) = \bigcap_{\mathcal{A} \in \mathbf{qGA}_k(X, Y)} \mathcal{M}_{X,Y}(\mathcal{A}) $$

of common matches of all alignments $\mathcal{A} \in \mathbf{qGA}_k(X, Y)$.

**Definition 5.16.** For strings $X, Y \in \Sigma^*$ and an integer $k$, we define the quasi-greedy encoding

$$ \mathbf{qGR}_k(X, Y) = \begin{cases} \mathbb{E}^{\mathcal{M}_k(X,Y)}(X, Y) & \text{if } \mathrm{ed}(X, Y) \le k, \\ \perp & \text{otherwise.} \end{cases} $$

**Corollary 5.17.** Consider strings $X, Y \in \Sigma^{\le n}$. Define $X' = \$1X$ and $Y' = \$2Y$, where $\$1 \neq \$2$ are special symbols not in $\Sigma$. Let $M' = \mathcal{M}_{k+1}(X', Y')$ and $M = \mathbf{qM}_k(X, Y)$. The following properties hold:

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

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

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

*Proof.* Let us first show that $\mathcal{A}' \mapsto \mathcal{A}'_{[2..], [2..]}$ bijectively maps $\mathbf{GA}_{k+1}(X', Y')$ to $\mathbf{qGA}_k(X, Y)$.

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

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

Let $M' = \mathcal{M}_{k+1}(X', Y')$ and $M = \mathbf{qM}_k(X, Y)$. From above, we obtain $M' = \{(x+1, y+1) : (x, y) \in M\}$. Therefore, $(X')^{M'}[2..] = X^M$ and $(Y')^{M'}[2..] = Y^M$.
It follows that we can obtain the dummy segments for $X^M$ by subtracting one from the endpoints of each dummy segment of $(X')^{M'}$, and analogously for $Y^M$. The reverse claim is obtained analogously, by adding one to the endpoints. As the number of the dummy segments in $X^M$ and $(X')^{M'}$ is $\mathcal{O}(k)$ by Lemma 3.10, (a) follows.

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

(c) follows immediately from (b). $\square$

From Corollaries 5.13 and 5.17 it immediately follows that:

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

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

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

**Observation 5.20.** Let $k' \leq k$. Given $\mathbf{qGR}_k(X, Y)$, the encoding $\mathbf{qGR}_{k'}(X, Y)$ can be computed in $\tilde{\mathcal{O}}(k^5)$ time and $\tilde{\mathcal{O}}(k^2)$ space.

*Proof.* For $k' \leq k$, we have $\mathbf{qM}_k(X, Y) \subseteq \mathbf{qM}_{k'}(X, Y)$ by definition. The claim follows from Corollary 5.19. $\square$

We now show that the quasi-greedy encodings are *concatenatable*.

**Lemma 5.21.** Consider strings $X_p, Y_p, X_s, Y_s \in \Sigma^{\leq n}$ and $k \in \mathbb{Z}_+$. Assume $\max\{|X_p| - |Y_p|, |X_s| - |Y_s|\} = \mathcal{O}(k)$. Given $\mathbf{qGR}_{k+||X_s|-|Y_s||}(X_p, Y_p)$ and $\mathbf{qGR}_{k+||X_p|-|Y_p||}(X_s, Y_s)$, one can compute $\mathbf{qGR}_k(X_p X_s, Y_p Y_s)$ in $\tilde{\mathcal{O}}(k^5)$ time and $\tilde{\mathcal{O}}(k^2)$ space.

*Proof.* For brevity, let $M_p = \mathbf{qM}_{k+||X_s|-|Y_s||}(X_p, Y_p)$ and $M_s = \mathbf{qM}_{k+||X_p|-|Y_p||}(X_s, Y_s)$. Let also $X = X_p X_s, Y = Y_p Y_s$.

By Lemma 5.15, if $\mathrm{ed}(X, Y) \leq k$, then $M := M_p \cup \{(x + |X_p|, y + |Y_p|) : (x, y) \in M_s\} \subseteq \mathbf{qM}_k(X, Y)$. Hence, we shall construct $\mathbf{E}^M(X, Y)$ and then apply Corollary 5.19.

For this, we extract $\mathbf{D}(X_p^{M_p}), \mathbf{D}(X_s^{M_s}), \mathbf{D}(Y_p^{M_p}), \mathbf{D}(Y_s^{M_s})$ using Proposition 4.2(g), and then concatenate them to $\mathbf{D}(X^M Y^M) = \mathbf{D}(X_p^{M_p} X_s^{M_s} Y_p^{M_p} Y_s^{M_s})$ using Proposition 4.2(i). Overall, this takes $\mathcal{O}(k^2 \log^4 n)$ time. Then, we use Proposition 5.2 to build $\mathrm{RS}_{\#}(X^M)$ and $\mathrm{RS}_{\#}(Y^M)$ in $\tilde{\mathcal{O}}(k)$ time.

Finally, we note that using Corollary 5.19 costs $\tilde{\mathcal{O}}(k^5)$ time and $\tilde{\mathcal{O}}(k^2)$ space (here we use the fact that $|X_p| - |Y_p| = \mathcal{O}(k)$). $\square$
Finally, as a corollary we derive an algorithm that can compute the quasi-greedy encoding of arbitrarily long strings.

**Corollary 5.22.** *Assuming constant-time random access to a string $X \in \Sigma^\ell$ and streaming access to a string $Y \in \Sigma^\ell$, where $\ell \le n$, there is an algorithm that constructs $\mathbf{qGR}_k(X, Y)$ with a delay of at most $k^2$ characters in $\tilde{O}(k^3)$ amortised time per character and $\tilde{O}(k^2)$ space. The delay means that at the moment when the y-th character of Y arrives, the algorithm knows $\mathbf{qGR}_k(X[\dots y'], Y[\dots y'])$, where $|y - y'| \le k^2$.*

*Proof.* If $\ell \le k^2$, construct $\mathbf{qGR}_k(X, Y)$ via Claim 5.18 in $\tilde{O}(k^3)$ (total) time and $\tilde{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 \dots p)$ and $|X_p| = |Y_z| = \ell \bmod k^2$. Suppose that we have computed $\mathbf{qGR}_k(X_1 \cdots X_{i-1}, Y_1 \cdots Y_{i-1})$ for $i \in [1 \dots p)$. Compute $\mathbf{qGR}_k(X_1 \cdots X_i, Y_1 \cdots Y_i)$ in the following manner: first, compute $\mathbf{qGR}_k(X_i, Y_i)$ in $O(k^5)$ time and $O(k^2)$ space via Claim 5.18, and then compute $\mathbf{qGR}_k(X_1 \cdots X_i, Y_1 \cdots Y_i)$ in $\tilde{O}(k^5)$ time and $\tilde{O}(k^2)$ space via Lemma 5.21. $\square$

## 5.4 Products of Greedy Alignments

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

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

*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 $\text{cost}(\mathcal{A}^{X,Y}) = \text{ed}(X, Y)$ and $\text{cost}(\mathcal{A}^{Y,Z}) = \text{ed}(Y, Z) \le \text{ed}(X, Y) + \text{ed}(X, Z) \le \text{ed}(X, Y) + \text{cost}(\mathcal{A}^{X,Z})$. Moreover, it is 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. $\mathbf{X}[1] = \mathbf{Z}[1] = \mathbf{Y}[1]$.

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

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

In this case, we have $\text{ed}(X, Y) > \min(\text{ed}(X[2..], Y[2..]), \text{ed}(X[2..], Y), \text{ed}(X, Y[2..]))$.

(a) If $\text{ed}(X, Y) > \text{ed}(X[2..], Y[2..])$, we recurse on $X' = X[2..], Y' = Y[2..], Z' = Z[2..]$, and $\mathcal{A}^{X',Z'} = \mathcal{A}_{[2..],[2..]}^{X,Z}$, which is greedy due to $X[1] \cong_{\mathcal{A}^{X,Z}} Z[1]$. This yields greedy alignments $\mathcal{A}^{X',Y'}$, $\mathcal{A}^{Y',Z'}$ of cost at most $d' = 2\text{cost}(\mathcal{A}^{X,Z}) + \text{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$.

(b) If $\text{ed}(X, Y) > \text{ed}(X[2..], Y)$, we recurse on $X' = X[2..], Y' = Y, Z' = Z[2..]$, and $\mathcal{A}^{X',Z'} = \mathcal{A}_{[2..],[2..]}^{X,Z}$, which is greedy due to $X[1] \cong_{\mathcal{A}^{X,Z}} Z[1]$. This yields greedy alignments $\mathcal{A}^{X',Y'}$, $\mathcal{A}^{Y',Z'}$ of cost at most $d' = 2\text{cost}(\mathcal{A}^{X,Z}) + \text{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$.
(c) If $\mathrm{ed}(X, Y) > \mathrm{ed}(X, Y[2..])$, we recurse on $X' = X, Y' = Y[2..], Z' = Z$, and $\mathcal{A}^{X',Z'} = \mathcal{A}^{X,Z}$. This yields greedy alignments $\mathcal{A}^{X',Y'}, \mathcal{A}^{Y',Z'}$ of cost at most $d' = 2\mathrm{cost}(\mathcal{A}^{X,Z}) + \mathrm{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. $\mathbf{X}[1] \neq \mathbf{Z}[1] = \mathbf{Y}[1]$.

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

(b) If $\mathcal{A}^{X,Z}$ deletes $Z[1]$, we recurse on $X' = X, Y' = Y[2..], Z' = Z[2..]$, and $\mathcal{A}^{X',Z'} = \mathcal{A}_{[1.,[2.,]..}^{X,Z}$. This yields greedy alignments $\mathcal{A}^{X',Y'}, \mathcal{A}^{Y',Z'}$ of cost $\le d' = 2\mathrm{cost}(\mathcal{A}^{X,Z}) - 2+\mathrm{ed}(X', Y') \le 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$.

(c) If $X[1] \sim_{\mathcal{A}^{X,Z}} Z[1]$, we recurse on $X' = X[2..], Y' = Y[2..], Z' = Z[2..]$, and $\mathcal{A}^{X',Z'} = \mathcal{A}_{[2.,[2.,]..}^{X,Z}$. This yields greedy alignments $\mathcal{A}^{X',Y'}, \mathcal{A}^{Y',Z'}$ of cost $\le d' = 2\mathrm{cost}(\mathcal{A}^{X,Z}) - 2 + \mathrm{ed}(X', Y') \le 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. $\mathbf{X}[1] \neq \mathbf{Z}[1] \neq \mathbf{Y}[1]$. (Note that this case allows both $X[1] = Y[1]$ and $X[1] \neq Y[1]$.)

(a) If $\mathcal{A}^{X,Z}$ deletes $X[1]$, we recurse on $X' = X[2..], Y' = Y[2..], Z' = Z$, and $\mathcal{A}^{X',Z'} = \mathcal{A}_{[2.,[1.,]..}^{X,Z}$. This yields greedy alignments $\mathcal{A}^{X',Y'}, \mathcal{A}^{Y',Z'}$ of cost at most $d' = 2\mathrm{cost}(\mathcal{A}^{X,Z}) - 2 + \mathrm{ed}(X', Y') \le 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$.

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

(c) If $X[1] \sim_{\mathcal{A}^{X,Z}} Z[1]$, we recurse on $X' = X[2..], Y' = Y[2..], Z' = Z[2..]$, and $\mathcal{A}^{X',Z'} = \mathcal{A}_{[2.,[2.,]..}^{X,Z}$. This yields greedy alignments $\mathcal{A}^{X',Y'}, \mathcal{A}^{Y',Z'}$ of cost $\le d' = 2\mathrm{cost}(\mathcal{A}^{X,Z}) - 2 + \mathrm{ed}(X', Y') \le 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',Y'}$ 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',Z'}$ 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',Z'}$ is a product of $\mathcal{A}^{X',Y'}$ and $\mathcal{A}^{Y',Z'}$. $\square$

Assume that we are given three strings $X, Y, Z$. Let $d = \mathrm{ed}(X, Y) + 2k$, and define $\mathcal{G}_X = \mathrm{GR}_d(X, Y)$ and $\mathcal{G}_Z = \mathrm{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$ such that $(x, y) \in \mathcal{M}_d(X, Y)$ and $(y, z) \in \mathcal{M}_d(Y, Z)\}$.

**Lemma 5.23.** If $\mathrm{ed}(X, Z) \le 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 \mathrm{GA}_k(X, Z)$. Then, there exists $(x', z') \in \mathcal{A}$ such that either $x' \le x$ and $z' > z$, or $x' > x$ and $z' \le 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 \mathrm{GA}_d(X, Y)$ and $\mathcal{A}^{Y,Z} \in \mathrm{GA}_d(Y, Z)$. According to Definition 3.12, this means that there exists $y'$ such that $(x', y') \in \mathcal{A}^{X,Y}$ and $(y', z') \in \mathcal{A}^{Y,Z}$. If $y' \le y$, then $(y, z), (y', z') \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' > y$, then $(x, y)$, $(x', y') \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_A Z[z]$ for every $\mathcal{A} \in \mathcal{GA}_k(X, Z)$. Due to $X[x] = Y[y] = Z[z]$, we also have $X[x] \simeq_A Z[z]$ for every $\mathcal{A} \in \mathcal{GA}_k(X, Z)$, i.e., $(x, y) \in \mathcal{M}_k(X, Z)$ holds as claimed. $\square$

**Lemma 5.24.** If $\text{ed}(X, Y) = \mathcal{O}(k)$ and $\mathcal{G}_X, \mathcal{G}_Z \neq \emptyset$, $\text{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..|X|]$ such that $(x, z) \notin M$ for every $z \in [1..|Z|]$. If $X^{M_d(X,Y)}[x] \neq \#$, then $X^M[x] = X[x] = X^{M_d(X,Y)}[x]$. Otherwise, $(x, y) \in M_d(X, Y)$ for some $y \in [1..|Y|]$. By Lemma 5.23, we have $(y, z) \notin M_d(Y, Z)$ for every $z \in [1..|Z|]$. Hence, $Y^{M_d(Y,Z)}[y] \neq \#$, and we have $X[x] = Y[y] = Y^{M_d(Y,Z)}[y]$. In words, non-dummy characters of $X^M$ can be retrieved from non-dummy characters of $X^{M_d(X,Y)}$ and non-dummy characters of $Y^{M_d(Y,Z)}$.

Thus, for each dummy segment $[\ell \dots r)$ in $X^{M_d(X,Y)}$ and its counterpart $[\ell' \dots r')$ in $Y^{M_d(X,Y)}$, we need to set $X^M[\ell \dots r) := Y^{M_d(Y,Z)}[\ell' \dots r')$. 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 $\text{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 $\text{RS}_\#(X^M)$ and $\text{RS}_\#(Z^M)$ in $\mathcal{O}(k)$ time. $\square$

**Corollary 5.25.** Given $\mathcal{G}_X$ and $\mathcal{G}_Z$. If $\text{ed}(X, Y) = \mathcal{O}(k)$, then we can compute $\min(k + 1, \text{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 $\perp$, then $\text{ed}(X, Z) > k$ by Lemma 3.13. Otherwise, construct $\text{E}^M(X, Z)$ using Lemma 5.24. Finally, we pass $k$ and $\text{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 $\text{ed}(X, Z) > k$. If $\text{ed}(X, Z) \le k$, then Lemma 5.23 implies $M \subseteq \mathcal{M}_k(X, Z)$, and thus $d = \text{ed}(X, Z)$ holds as claimed.

The overall runtime and space complexity are dominated by the procedure of Lemma 5.24. $\square$

*Remark 5.26.* Using Proposition 5.12 instead of Corollary 5.5, we could construct $\text{GR}_k(X, Z)$.

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

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

# 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^{\le n}$ is bounded in terms of the edit distance $\text{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 $\perp \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^{\le n}$, the CGK walk $W_{\text{CGK}}(S) = (s_t)_{t=1}^{3n+1}$ and the CGK embedding $\text{CGK}(S) \in (\Sigma \cup \{\perp\})^{3n}$ are defined by the following algorithm:

**Algorithm 2:** The CGK algorithm
***
**Input:** An integer $n \in \mathbb{Z}_+$, a string $S \in \Sigma^{\le n}$.
**Randomness:** A sequence $R \in \mathcal{H}^{3n}$ of 2-independent hash functions $\Sigma \to \{0, 1\}$.
**Output:** The CGK walk $W_{\text{CGK}}(S) = (s_t)_{t=1}^{3n+1}$ and the CGK embedding $\text{CGK}(S)$.
1 $s_1 := 1$;
2 for $t := 1$ to $3n$ do
3 if $s_t \le |S|$ then
4 $\text{CGK}(S)[t] := S[s_t]$;
5 $s_{t+1} := s_t + R_t(S[s_t])$;
6 else
7 $\text{CGK}(S)[t] := \perp$;
8 $s_{t+1} := s_t$;

<caption>**Algorithm 2:** The CGK algorithm</caption>

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^{\le n}$ satisfies $\text{Pr}_R[W_{\text{CGK}}(S)$ is complete$] \ge 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^{\le n}$ and every constant $c > 0$, the embeddings $\text{CGK}(X)$, $\text{CGK}(Y)$ satisfy $\text{Pr}_{R \in \mathcal{H}^{3n}}[\text{hd}(\text{CGK}(X), \text{CGK}(Y)) > c \cdot \text{ed}(X, Y)^2] < \frac{12}{\sqrt{c}}$.

If $W_{\text{CGK}}(X)$ and $W_{\text{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_{\text{CGK}}(X)$ and $W_{\text{CGK}}(Y)$ are complete for some $X, Y \in \Sigma^{\le n}$ and $R \in \mathcal{H}^{3n}$, then the CGK alignment of $X, Y$ belongs to $\text{GA}_{\text{hd}(\text{CGK}(X),\text{CGK}(Y))}(X, Y)$.

*Proof.* Let $\mathcal{A}$ be the CGK alignment of $X, Y$, i.e., the zip alignment of $W_{\text{CGK}}(X) = (x_t)_{t=1}^{3n+1}$ and $W_{\text{CGK}}(Y) = (y_t)_{t=1}^{3n+1}$. Consider $(x_t, y_t) \in \mathcal{B}(\mathcal{A})$, with $t \in [1 \dots 3n + 1]$ chosen so that $t = 3n + 1$ or $(x_{t+1}, y_{t+1}) \ne (x_t, y_t)$. If $t = 3n + 1$, then $(x_t, y_t) = (|X|+1, |Y|+1)$ by the assumption that $W_{\text{CGK}}(X)$ and $W_{\text{CGK}}(Y)$ are complete. If $(x_{t+1}, y_{t+1}) = (x_t+1, y_t+1)$, then we have $\text{CGK}(X)[t] = X[x_t] \ne Y[y_t] = \text{CGK}(Y)[t]$. The remaining possibility $x_{t+1} - x_t \ne y_{t+1} - y_t$ holds only in the following three cases: if $x_t = |X|+1$ and $y_t \le |Y|$ (when $\text{CGK}(X)[t] = \perp \ne \text{CGK}(Y)[t] = Y[y_t]$), if $x_t \le |X|$ and $y_t = |Y|+1$ (when $X[x_t] = \text{CGK}(X)[t] \ne \perp = \text{CGK}(Y)[t]$), or if $x_t \le |X|$, $y_t \le |Y|$, and $R_t(X[x_t]) \ne R_t(Y[y_t])$ (when $\text{CGK}(X)[t] = X[x_t] \ne Y[y_t] = \text{CGK}(Y)[t]$). Overall, we have $X[x_t] \ne Y[y_t]$ whenever $(x_t, y_t) \in [1 \dots |X|] \times [1 \dots |Y|]$, and $\text{CGK}(X)[t] \ne \text{CGK}(Y)[t]$ whenever $t \in [1 \dots 3n]$. Consequently, $\mathcal{A} \in \text{GA}_{\text{hd}(\text{CGK}(X),\text{CGK}(Y))}(X, Y)$. $\square$

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

**Fact 6.5.** Let $(w_i)_{i \ge 0}$ be an unbiased lazy random walk (that is, $w_0 = 0$, and, for every $i \ge 1$, we have $\text{Pr}[w_{i+1} = w_i | w_0, \dots, w_i] = \frac{1}{2}$, $\text{Pr}[w_{i+1} = w_i + 1 | w_0, \dots, w_i] = \text{Pr}[w_{i+1} = w_i - 1 | w_0, \dots, w_i] = \frac{1}{4}$). Then, for every $m, \ell \in \mathbb{Z}_+$, we have $\text{Pr}[\max_{i=0}^m |w_i| \ge \ell] \le \frac{m}{\ell^2}$.
**Proof.** By the reflection principle [44, Excercise 2.10], we have $\Pr[\max_{i=0}^m |w_i| \ge \ell] \le 2 \Pr[|w_m| \ge \ell] = 2 \Pr[w_m^2 \ge \ell^2]$. By Markov's inequality,

$$2 \Pr[w_m^2 \ge \ell^2] \le \frac{2\mathbb{E}[w_m^2]}{\ell^2} = \frac{2\mathbb{E}[(w_1 - w_0)^2 + \dots + (w_m - w_{m-1})^2]}{\ell^2} = \frac{m}{\ell^2}. \quad \square$$

**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^{\le n}$, and their CGK alignment $\mathcal{A}$, the probability over $R \in \mathcal{H}^{3n}$ that $W_{\text{CGK}}(X), W_{\text{CGK}}(Y)$ are complete, $\mathcal{A} \in \text{GA}_{c \cdot \text{ed}}(X, Y)^2(X, Y)$, and width($\mathcal{A}$) $\le c \cdot \text{ed}(X, Y)$ is at least $1 - \delta$.

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

To bound width($\mathcal{A}$), let us analyze the CGK walks $W_{\text{CGK}}(X) = (x_t)_{t=1}^{3n+1}$ and $W_{\text{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| \ge ck]$, where $k = \text{ed}(X, Y)$.

Let $A = \{1\} \cup \{t+1 : t \in [1..T]\}$ and $X[x_t] \ne Y[y_t]$. Observe that $x_t - y_t = x_{t-1} - y_{t-1}$ holds for $t \in [1..T] \setminus A$, so we may focus on bounding $\Pr[\max_{t \in A} |x_t - y_t| \ge ck]$. Let $A = \{t_0, \dots, t_a\}$ with $t_0 < \dots < t_a$, and let $d_i = x_{t_i} - y_{t_i}$ for $i \in [0..a]$. Observe that $(d_i)_{i=0}^a$ is an $a$-step unbiased lazy random walk and that $a \le \text{hd}(\text{CGK}(X), \text{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}^{|ck|^2} |d_i| \ge ck] \le \frac{ck^2}{c^2k^2} = \frac{1}{c} \le \frac{\delta}{4}$. Therefore,

$$\Pr \left[ \max_{i=0}^{a} |d_i| \ge ck \right] \le \Pr \left[ \text{hd}(\text{CGK}(X), \text{CGK}(Y)) > ck^2 \right] + \Pr \left[ \max_{i=0}^{|ck|^2} |d_i| \ge ck \right].$$

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

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].

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

$$\Pr_r [\mathcal{A}_W \in \text{GA}_{c \cdot \text{ed}}(X, Y)^2(X, Y) \text{ and width}(\mathcal{A}_W) \le c \cdot \text{ed}(X, Y)] \ge 1 - \delta.$$

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

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

If $n < \max(\frac{10}{\delta}, n_{6.6})$, we set $W(n, r, S) = (\min(t, |S| + 1))_{t=1}^{3n+1}$ for all $S \in \Sigma^{\le n}$ so that $W(n, r, S)$ is trivially a $3n$-step complete walk over $S$. Now, consider strings $X, Y \in \Sigma^{\le n}$ and the zip alignment $\mathcal{A}_W$ of $W(n, r, X)$ and $W(n, r, Y)$. Observe that $\mathcal{A}_W \in \text{GA}_0(X, Y)$ if $X = Y$ and $\mathcal{A}_W \in \text{GA}_n(X, Y)$ otherwise. Moreover, width($\mathcal{A}_W$) = $||X|-|Y|| \le \text{ed}(X, Y)$. Consequently,
the claimed conditions are (deterministically) satisfied for $c \ge n_{6.6}$. The construction algorithm uses $O(\log n)$ bits and $O(n)$ time.

If $n \ge \max(\frac{10}{\delta}, n_{6.6})$, we first develop an algorithm $W'$ 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 $[\log \sigma]$-bit integer $h_t$ so that $R_t(a)$ counts (modulo 2) the set bits in a xor $h_t$.

We set $W'(n, R, S) = (\max(t-3n+|S|, s_t))_{t=1}^{3n+1}$ based on the CGK walk $W_{\text{CGK}}(S) = (s_t)_{t=1}^{3n+1}$ for all $S \in \Sigma^{\le n}$. Observe that this modification guarantees that $W'(n, R, S)$ is a complete walk over $S$ and that $W'(n, R, S) = W_{\text{CGK}}(S)$ if $W_{\text{CGK}}(S)$ is already complete. Consequently, by Corollary 6.6, the claimed conditions are satisfied with probability at least $1 - \delta_{6.6} = 1 - \frac{\delta}{2}$ for $c \ge c_{6.6}$. The construction algorithm uses $O(\log n)$ bits, costs $O(n)$ time, reads the random bits $(h_t)_{t=1}^{3n+1}$ from left to right, and outputs the elements of $W'(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 $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^{\le 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}'$ of $W'(n, R, X) = (x_t)_{t=1}^{3n+1}$ and $W'(n, R, Y) = (y_t)_{t=1}^{3n+1}$ are testable in $O(\log n)$ bits and $O(n)$ time:

* whether $\mathcal{A}'$ is greedy;

* whether $\text{cost}(\mathcal{A}') \le k$ for a given integer $k \in [0..n]$;

* whether $\text{width}(\mathcal{A}') \le w$ for a given integer $w \in [0..n]$.

All these testers simply construct triples $(t, x_t, y_t)$ for subsequent $t \in [1..3n+1]$.

In this setting, Nisan's pseudorandom generator [50], given a sequence $r$ of $O(\log^2 n)$ random bits, constructs a sequence $\text{PRG}(r)$ of pseudorandom bits in $O(1)$ amortized time per bit, using $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 $\text{PRG}(r)$ differ by at most $\frac{1}{n^2}$ [10, Theorem 5]. Consequently, setting $W(n, r, S) = W'(n, \text{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} \ge 1 - \delta$. The streaming construction algorithm takes $O(\log^2 n)$ bits and $O(n \log n)$ time, dominated by the generation of $\text{PRG}(r)$. $\square$

## 6.2 Context encoding

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

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

(a) $\overline{\text{maxLZ}}(S[\ell..r]) \le k$ if and only if $\text{LZ}(\overline{S[\ell..r]}) \le k$;

(b) $\overline{\text{maxLZ}}(S[\ell+1..r]) \le k$;

(c) $\overline{\text{maxLZ}}(S[\ell..r]) \le k+1$.

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

**Definition 6.8 (Double Context).** Consider a string $S \in \Sigma^*$ and an integer $k \in \mathbb{Z}_+$. For a position $p \in [1..|S|]$, we define the context $C_k(S, p)$ as the longest prefix $S[p..q)$ of $S[p..|S|]$ such that $\overline{\text{maxLZ}}(S[p..q)) \le k$ and the double context $C_k^2(S, p)$ as the longest prefix $S[p..q)$ of $S[p..|S|]$ such that $\overline{\text{maxLZ}}(S[p..r)) \le k$ and $\overline{\text{maxLZ}}(S[r..q)) \le k$ for some $r \in [p..q]$.

For integers $t < v$, let $\mu(t, v)$ denote the integer $w \in [t..v)$ divisible by the largest power of 2. We say that a position $S[s]$ is covered by a fragment $S[\ell..r)$ if $\ell \le s < r$.
**Input:** An integer $k \in \mathbb{Z}_{\ge 0}$, a string $S \in \Sigma^*$, and a complete walk $(s_t)_{t=1}^{m+1}$ over $S$.

**Output:** The string $\mathrm{CE}_k(W)[1..m]$.

1. $\mathrm{CE}_k(W) := \bot^m$, where $\bot = (\mathrm{LZ}(\varepsilon), 0)$;

2. $s_0 := 0; \mu_0 := 0; u := 0$;

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

4. if $s_t \le |S|$ then

5. $\mu_t := \mu(t, \min\{v \in [1..m+1] : s_v = s_t + |C_k(S, s_t)|\})$;

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

7. $\mathrm{CE}_k(W)[t] := (\mathrm{LZ}(\overline{C_k^2(S, s_t)}), s_t - s_u)$;

8. $u := t$;

9. return $\mathrm{CE}_k(W)$;

<caption>**Algorithm 3:** Function CE</caption>

**Lemma 6.9.** Consider $\mathrm{CE}_k(W)$ constructed for an integer $k \in \mathbb{Z}_{\ge 0}$ and an $m$-complete walk $W = (s_t)_{t=1}^{m+1}$ over $S \in \Sigma^*$. Each position $s \in [1..|S|]$ satisfies

$$1 \le |\{t \in [1..m] : \mathrm{CE}_k(W)[t] \ne \bot \text{ and } C_k(S, s_t) \text{ covers } S[s]\}| \le \\ \le |\{t \in [1..m] : \mathrm{CE}_k(W)[t] \ne \bot \text{ and } C_k^2(S, s_t) \text{ covers } S[s]\}| \le \mathcal{O}(\log m)$$

*Proof.* Let us first bound the covering number from below. Consider an index $t \in [1..m]$ such that $s = s_t$, and let $t' \in [1..m]$ be the smallest index such that $\mu_{t'} = \mu_t$. Note that $s_{\mu_{t'}} < s_{t'} + |C_k(S, s_{t'})|$ and $s_{\mu_t} \ge s_t$ by definition of $\mu$ and monotonicity of the walk $W$. Due to $\mu_{t'} = \mu_t$, this implies $s_{t'} \le s_t < s_{t'} + |C_k(S, s_{t'})|$, i.e., that $S[s_t]$ is covered by $C_k(S, s_{t'})$. Due to $\mu_{t'-1} \ne \mu_t$, this guarantees $\mathrm{CE}_k(S)[t'] \ne \bot$.

As for the upper bound, note that the indexes $t \in [1..m]$ with $\mathrm{CE}_k(S)[t] \ne \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'$ in the same group. Since $\mu_t < \mu_{t'}$ are divisible by the same largest power of two, there is a number $\nu \in (\mu_t..\mu_{t'})$ divisible by a strictly larger power of two. By definition of $\mu_t$, we have $s_\nu \ge s_t + |C_k(S, s_t)|$ and, by definition of $\mu_{t'}$, we have $s_\nu < s_{t'}$. Consequently, $s_{t'} > s_t + |C_k(S, s_t)|$, i.e., the contexts $C_k(S, s_t)$ and $C_k(S, s_{t'})$ are disjoint. By monotonicity of $\max\mathrm{LZ}$, this also means that $s_t + |C_k^2(S, s_t)| \le s_{t'} + |C_k(S, s_{t'})|$. In particular, each position $s \in [1..|S|]$ is covered by at most one context $C_k(S, s_t)$ and at most two double contexts $C_k^2(S, s_t)$ for $t \in [1..m]$ belonging to a single group. $\square$

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..|X|]$. Moreover, for two alignments $\mathcal{A}, \mathcal{A}'$ between $X, Y \in \Sigma^*$, we define $\Delta_X(\mathcal{A}, \mathcal{A}')$ to contain $x \in [1..|X|]$ unless $(x, y) \in \mathcal{M}(\mathcal{A}) \cap \mathcal{M}(\mathcal{A}')$ for some $y \in [1..|Y|]$.

**Lemma 6.10.** Let $b \in \mathbb{Z}_+$ and $\mathcal{A}, \mathcal{A}'$ be greedy alignments of strings $X$ and $Y$. The positions in $\Delta_X(\mathcal{A}, \mathcal{A}')$ can be covered by at most $\mathrm{cost}(\mathcal{A}) + \frac{1}{b}\mathrm{cost}(\mathcal{A}')$ contexts $C_{\mathrm{width}(\mathcal{A})+\mathrm{width}(\mathcal{A}')+2b}(X, \cdot)$.

Moreover, if $b > \mathrm{cost}(\mathcal{A}')$, then the positions in $\Delta_X(\mathcal{A}, \mathcal{A}')$ can be covered by contexts $C_{\mathrm{width}(\mathcal{A})+\mathrm{width}(\mathcal{A}')+2b}(X, x)$ with $x \in \mathcal{B}_X(\mathcal{A})$.

*Proof.* Let $w = \mathrm{width}(\mathcal{A})$ and $w' = \mathrm{width}(\mathcal{A}')$. 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}'$ match the common prefix, so $\Delta_X(\mathcal{A}, \mathcal{A}')$ only contains positions following the prefix. Moreover, we assume that $X \ne \varepsilon$; otherwise $\Delta_X(\mathcal{A}, \mathcal{A}') = \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, \dots, x_m\}$, where $1 = x_1 < \dots < 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 \dots x_{i+1})$. The alignment $\mathcal{A}'$ further yields a decomposition $Y = Y_1 \cdots Y_m$ into $m$ (possibly empty) substrings $Y_i := Y[y_i \dots y_{i+1})$ so that $X_i \sim_{\mathcal{A}'} Y_i$ and $|x_i - y_i| \le w'$ for $i \in [1 \dots m]$. Moreover, the cost of $\mathcal{A}'$ can be expressed as $\mathrm{cost}(\mathcal{A}') = \sum_{i=1}^m c'_i$, where $c'_i$ denotes the cost of $\mathcal{A}'$ restricted to $X_i$ and $Y_i$.

**Claim 6.11.** For every $i \in [1 \dots m]$, the set $\Delta_X(\mathcal{A}, \mathcal{A}') \cap [x_i \dots x_{i+1})$ can be covered by at most $\lceil \frac{1}{b}(c'_i + 1) \rceil$ contexts $C_{w+w'+2b}(X, \cdot)$ including $C_{w+w'+2b}(X, x_i)$.

*Proof.* Let $q_i = \max(\Delta_X(\mathcal{A}, \mathcal{A}') \cap [x_i \dots x_{i+1}))$. We may assume that $q_i \ge x_i + w + w'$; otherwise, the claim holds trivially. We shall prove that $X[x_i + 1 \dots q_i - (w + w')]$ can be decomposed into at most $2c'_i + 1$ phrases, each of which is a single character or has another occurrence at most $w + w'$ positions to the right. Accounting for $X[x_i]$, this yields a decomposition of $X[x_i \dots q_i - (w + w')]$ into at most $2c'_i + 2$ such phrases. The $\max\underline{LZ}$ measure of the concatenation of every $2b$ subsequent phrases and $w + w'$ following single characters does not exceed $w + w' + 2b$. Hence, $X[x_i \dots q_i]$ can be covered by $\lceil \frac{1}{b}(c'_i + 1) \rceil$ contexts $C_{w+w'+2b}(X, \cdot)$ including $C_{w+w'+2b}(X, x_i)$.

Thus, it remains to construct the decomposition of $X[x_i + 1 \dots q_i - (w + w')]$ into phrases. By definition of $\mathcal{B}_X(\mathcal{A})$, we have $X[x_i + 1 \dots x_{i+1}) \cong_{\mathcal{A}} Y[x_i + 1 + d \dots x_{i+1} + d)$ for some shift $d \in [-w \dots w]$. We consider two cases.

In the first case, we assume that $(x_i + 1, \bar{y}) \in \mathcal{A}'$ holds for some $\bar{y} \ge x_i + 1 + d$. The greedy nature of $\mathcal{A}'$ then guarantees that if $(x, y) \in \mathcal{A}'$ with $x \in [x_i + 1 \dots q_i)$, then $y > x + d$. We decompose $X[x_i + 1 \dots q_i - (w + w')]$ (which is contained in $X_i$) into maximal phrases $X[x \dots x']$ satisfying $X[x \dots x'] \cong_{\mathcal{A}'} Y[x + d' \dots x' + d']$ for some $d' \in (d \dots w']$ and remaining single characters (deleted or substituted by $\mathcal{A}'$). Observe that this yields at most $1 + c'_i$ phrases and at most $c'_i$ single characters. Moreover, we have $X[x \dots x'] \cong_{\mathcal{A}'} Y[x + d' \dots x' + d'] \cong_{\mathcal{A}} X[x + (d'-d) \dots x' + (d'-d)]$ due to $x_i+1 \le x \le x + (d'-d)$ and $x' + (d'-d) \le x' + (w'+w) \le q_i$. Hence, each phrase $X[x \dots x']$ has another occurrence located $d' - d \in [1 \dots w + w']$ positions to the right.

In the second case, we assume that $(x_i + 1, \bar{y}) \in \mathcal{A}'$ holds for some $\bar{y} \le x_i + 1 + d$. The greedy nature of $\mathcal{A}'$ then guarantees that if $(x, y) \in \mathcal{A}'$ with $x \in [x_i + 1 \dots q_i)$, then $y < x + d$. We decompose $Y[x_i + 1 + d \dots q_i - (w + w') + d]$ (which is contained in $Y_i$) into maximal phrases $Y[y \dots y']$ satisfying $Y[y \dots y'] \cong_{\mathcal{A}'} X[y - d' \dots y' - d']$ for some $d' \in [-w \dots d)$ and remaining single characters (deleted or substituted by $\mathcal{A}'$). Observe that this yields at most $1 + c'_i$ phrases and at most $c'_i$ single characters. Moreover, we have $Y[y \dots y'] \cong_{\mathcal{A}'} X[y - d' \dots y' - d'] \cong_{\mathcal{A}} Y[y + (d - d') \dots y + (d-d')]$ due to $x_i+1 \le x_i+1+d-d' \le y-d'$ and $y'-d' \le q_i - (w+w') + d-d' \le q_i$. Hence, each phrase $Y[y \dots y']$ has another occurrence located $d-d' \in [1 \dots w+w']$ characters to the right. Since $Y[x_i + 1 + d \dots q_i + d] = X[x_i + 1 \dots q_i]$, this decomposition of $Y[x_i + 1 + d \dots q_i - (w + w') + d]$ gives an analogous decomposition of $X[x_i + 1 \dots q_i - (w + w')]. \square$

The set $\Delta_X(\mathcal{A}, \mathcal{A}')$ can be covered by $\sum_{i=1}^m \lceil \frac{1}{b}(c'_i + 1) \rceil \le m + \frac{\mathrm{cost}(\mathcal{A}')}{b} \le \mathrm{cost}(\mathcal{A}) + \frac{\mathrm{cost}(\mathcal{A}')}{b}$ contexts $C_{w+w'+2b}(X, \cdot)$. If $b \ge \mathrm{cost}(\mathcal{A}') + 1$, then the contexts starting at positions in $\mathcal{B}_X(\mathcal{A})$ are sufficient. $\square$

**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' \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 \dots |X|]$ such that $X[x]$ is covered by $C_{k'}^2(X, x_t)$ for some $t \in [1 \dots m]$ with $\perp \ne \mathrm{CE}_{k'}(W_X)[t] \ne \mathrm{CE}_{k'}(W_Y)[t]$. Moreover, for every positive integer $k \ge \mathrm{ed}(X, Y)$ such that $k' \ge \mathrm{width}(\mathcal{A}_W) + 5k$:

* every $\mathcal{A} \in \mathrm{GA}_k(X, Y)$ satisfies $\Delta_X(\mathcal{A}, \mathcal{A}_W) \subseteq P_X$,
• hd($\mathrm{CE}_{k'}(X)$, $\mathrm{CE}_{k'}(Y)$) $\le c(k + \frac{1}{k}\mathrm{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..m]$ such that $\mathrm{CE}_{k'}(W_X)[t] \ne \perp$ and $C_{k'}^2(X, x_t)$ covers $X[x]$. To conclude that $x \in P_X$, it remains to prove $\mathrm{CE}_{k'}(W_X)[t] \ne \mathrm{CE}_{k'}(W_Y)[t]$. For a proof by contradiction, suppose that $\mathrm{CE}_{k'}(W_X)[t] = \mathrm{CE}_{k'}(W_Y)[t]$. This implies $C_{k'}^2(X, x_t) = C_{k'}^2(Y, y_t)$. Since $\mathcal{A}_W$ is greedy, we derive $X[x_t..x_t + |C_{k'}^2(X, x_t)|] \cong_{\mathcal{A}_W} Y[y_t..y_t + |C_{k'}^2(Y, y_t)|]$, which contradicts $x \in \mathcal{B}_X(\mathcal{A}_W)$.

In the remainder of the proof, we assume that $k \ge \mathrm{ed}(X, Y)$ and $k' \ge \mathrm{width}(\mathcal{A}_W) + 5k$. Next, consider a greedy alignment $\mathcal{A}$ with $\mathrm{cost}(\mathcal{A}) \le k$ and a position $x \in \Delta_X(\mathcal{A}, \mathcal{A}_W)$. Due to $k' \ge \mathrm{width}(\mathcal{A}_W) + \mathrm{width}(\mathcal{A}) + 4k$, Lemma 6.10 shows that there exists a position $r \in \mathcal{B}_X(\mathcal{A}_W)$ such that $C_{k'}(X, r)$ covers $X[x]$ and, by Lemma 6.9, there exists a position $t \in [1..m]$ such that $\mathrm{CE}_{k'}(X)[t] \ne \perp$ and $C_{k'}(X, x_t)$ covers $X[r-1]$. Since $\max\mathcal{L}\mathcal{Z}(X[x_t..r]), \max\mathcal{L}\mathcal{Z}(X[r..x]) \le k'$, we conclude that both $r$ and $x$ are covered by $C_{k'}^2(X, x_t)$. We shall prove that $\mathrm{CE}_{k'}(X)[t] \ne \mathrm{CE}_{k'}(Y)[t]$. For a proof by contradiction, suppose that $\mathrm{CE}_{k'}(W_X)[t] = \mathrm{CE}_{k'}(W_Y)[t]$, which implies $C_{k'}^2(X, x_t) = C_{k'}^2(Y, y_t)$. Let us fix the smallest $t' \in [t..m+1]$ such that $(x_{t'}, y_{t'}) \in \mathcal{B}(\mathcal{A}_W)$. Observe that $X[x_t..x_{t'}] \cong_{\mathcal{A}_W} Y[y_t..y_{t'}]$ and, by the greedy nature of $\mathcal{A}_W$, $X[x_t..x_{t'}] = Y[y_t..y_{t'}]$ is the longest common prefix of $X[x_t..]$ and $Y[y_t..]$. At the same time, due to $x_t < r \in \mathcal{B}_X(\mathcal{A}_W)$, we have $x_{t'} \le r$, so $X[x_t..x_{t'}]$ is a prefix of $C_{k'}^2(X, x_t)$. However, $X[x_t..x_{t'}]$ is not a prefix $Y[y_t..]$, so $C_{k'}^2(X, x_t)$ is not a prefix of $Y[y_t..]$ and $C_{k'}^2(X, x_t) \ne C_{k'}^2(Y, y_t)$. The contradiction completes the proof.

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

**Claim 6.13.** If $t \in M$ satisfies $\mathrm{CE}_{k'}(X)[t] \ne \perp$, then

$$[x_{t-1}..x_t + |C_{k'}^2(X, x_t)|] \cap (\mathcal{B}_X(\mathcal{A}_W) \cup \{|X| + 1\}) \ne \emptyset.$$

**Proof.** For a proof by contradiction, suppose that $[x_{t-1}..x_t + |C_{k'}^2(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..]$ and $Y[y_t..]$. 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_{k'}^2(X, x_t)| \ge |C_{k'}(X, x_t)|$, and therefore $X[x_t..x_t + |C_{k'}^2(X, x_t)|] = Y[y_t..y_t + |C_{k'}^2(Y, y_t)|]$ and $X[x_t..x_t + |C_{k'}(X, x_t)|] = Y[y_t..y_t + |C_{k'}(Y, y_t)|]$. In particular, $C_{k'}^2(X, x_t) = C_{k'}^2(Y, y_t)$.

If $t=1$, then we note that $\mathrm{CE}_{k'}(X)[t] \ne \perp \ne \mathrm{CE}_{k'}(Y)[t]$, so $C_{k'}^2(X, x_t) = C_{k'}^2(Y, y_t)$ contradicts $t \in M$.

In the following, we assume that $t \ge 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}..x_{t-1} + |C_{k'}(X, x_{t-1})|] = Y[y_{t-1}..y_{t-1} + |C_{k'}(Y, y_{t-1})|]$ due to $X[x_{t-1}..x_t + |C_{k'}(X, x_t)|] = Y[y_{t-1}..y_t + |C_{k'}(Y, y_t)|]$ and by Observation 6.7. Consequently, $\min\{u \in [1..m] : x_u = x_{t-1} + |C_{k'}(X, x_{t-1})|\} = \min\{u \in [1..m] : y_u = y_{t-1} + |C_{k'}(Y, y_{t-1})|\}$ and, by a similar reasoning, $\min\{u \in [1..m] : x_u = x_t + |C_{k'}(X, x_t)|\} = \min\{u \in [1..m] : y_u = y_t + |C_{k'}(Y, y_t)|\}$. Hence, the assumption $\mathrm{CE}_{k'}(X)[t] \ne \perp$ implies $\mathrm{CE}_{k'}(Y)[t] \ne \perp$. Therefore, $C_{k'}^2(X, x_t) = C_{k'}^2(Y, y_t)$ contradicts $t \in M$. $\square$

**Claim 6.14.** There are $\mathcal{O}((k + \frac{1}{k}\mathrm{cost}(\mathcal{A}_W)) \log m)$ positions $t \in M$ such that $\mathrm{CE}_{k'}(X)[t] \ne \perp$.

**Proof.** Let $\mathcal{O}$ be an optimum greedy alignment between $X$ and $Y$. Due to $k' \ge \mathrm{width}(\mathcal{O}) + \mathrm{width}(\mathcal{A}_W) + 4k$, from Lemma 6.10 it follows that $\Delta_X(\mathcal{O}, \mathcal{A}_W)$ can be covered by $\mathcal{O}(\mathrm{cost}(\mathcal{O}) + \frac{1}{k}\mathrm{cost}(\mathcal{A}_W)) = \mathcal{O}(k + \frac{1}{k}\mathrm{cost}(\mathcal{A}_W))$ contexts $C_{k'}(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..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 $\mathrm{CE}_{k'}(X)[t] \ne \perp$, then $C_{k'}^2(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 $O(\log m)$ double contexts $C_{k'}^2(X, x_t)$ with $\mathrm{CE}_{k'}(X)[t] \neq \perp$.

By Claim 6.13, we have $[x_{t-1}..x_t + |C_{k'}^2(X, x_t)|] \cap (\mathcal{B}_X(\mathcal{A}_W) \cup \{|X|+1\}) \neq \emptyset$. If $\{|X|+1\} \in [x_{t-1}..x_t + |C_{k'}^2(X, x_t)|]$, then $|X|+1 = x_t + |C_{k'}^2(X, x_t)|$. Hence, $C_{k'}^2(X, x_t)$ covers the position $|X| \in R_X$. Thus, we may assume that $[x_{t-1}..x_t + |C_{k'}^2(X, x_t)|]$ contains a position in $\mathcal{B}_X(\mathcal{A}_W)$. Note that the fragment $X[q..r] \in \mathcal{C}$ covering that position in $\mathcal{B}_X(\mathcal{A}_W)$ satisfies $r \ge x_{t-1}$ and $q \le x_t + |C_{k'}^2(X, x_t)|$. In particular, $r+1 \ge x_t$ and $q-1 < x_t + |C_{k'}^2(X, x_t)|$. Now, if $C_{k'}^2(X, x_t)$ covers $q-1$ or $r+1$, then we are done. Otherwise, $q-1 < x_t$ and $r+1 \ge x_t + |C_{k'}^2(X, x_t)|$, so $q \le x_t$ and $r \ge x_t + |C_{k'}^2(X, x_t)|$, i.e., $C_{k'}^2(X, x_t)$ is contained in $X[q..r]$ and, since $\overline{\max LZ}$ is monotone, $\overline{\max LZ}(C_{k'}^2(X, x_t)) \le k'$. Consequently, $C_{k'}^2(X, x_t) = C_{k'}(X, x_t)$ is a suffix of $X$, so $C_{k'}^2(X, x_t)$ covers the position $|X| \in R_X$. $\square$

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

**Claim 6.15.** $\mathrm{hd}(\mathrm{CE}_{k'}(X), \mathrm{CE}_{k'}(Y)) \le 2|M|$.

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

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

Now, suppose that $t' \notin M$. Consequently, we have $\mathrm{CE}_{k'}(X)[t'] \neq \perp \neq \mathrm{CE}_{k'}(Y)[t']$. Due to $\mathrm{CE}_{k'}(X)[t'+1..t) = \perp^{t-t'-1}$, Lemma 6.9 implies that $C_{k'}(X, x_t')$ covers $X[x_t-1]$, that is, $\overline{\max LZ}(X[x_t'..x_t]) \le k'$, and hence $X[x_t'..x_t]$ is a prefix of $C_{k'}^2(X, x_t')$. Moreover, $C_{k'}^2(X, x_t') = C_{k'}^2(Y, y_t')$ implies $X[x_t'..x_t] \simeq_{\mathcal{A}_W} Y[y_t'..y_t' + x_t - x_t']$ by the greedy nature of $\mathcal{A}_W$. As $(x_t, y_t) \in \mathcal{A}_W$, we conclude that $y_t = y_t' + x_t - x_t'$. At the same time, since $\mathrm{CE}_{k'}(X)[t'+1..t) = \perp^{t-t'-1} = \mathrm{CE}_{k'}(Y)[t'+1..t)$, we have $\mathrm{CE}_{k'}(X)[t] = (\overline{LZ}(\overline{C_{k'}^2(X, x_t)}), x_t - x_t')$ and $\mathrm{CE}_{k'}(Y)[t] = (\overline{LZ}(\overline{C_{k'}^2(Y, y_t)}), y_t - y_t')$. Thus, $\mathrm{CE}_{k'}(X)[t] = \mathrm{CE}_{k'}(Y)[t]$, which contradicts $t \in M'$.

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

Overall, we conclude that $\mathrm{hd}(\mathrm{CE}_{k'}(X), \mathrm{CE}_{k'}(Y)) \le 2|M| = O((k + \frac{1}{k}\mathrm{cost}(\mathcal{A}_W))\log m)$. $\square$

**Lemma 6.16.** *Given integers $n \ge k \ge 1$, a seed $r$ of $O(\log^2 n)$ random bits, and streaming access to a string $S \in \Sigma^{\le n}$, the string $\mathrm{CE}_k(\mathcal{W}(S, n, r))$ can be computed in $\tilde{O}(k)$ space and $\tilde{O}(nk)$ time.*

*Proof.* Let us start with an auxiliary subroutine:

**Claim 6.17.** *There is a streaming algorithm that computes $\mathrm{D}(C_k(S, p))$ for subsequent positions $p \in [1..|S|]$. The algorithm uses $\tilde{\mathcal{O}}(k)$ space and $\tilde{\mathcal{O}}(nk)$ time. Moreover, if $C_k(S, p) = S[p..q)$, then $\mathrm{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..q)$ satisfying $\overline{\max LZ}(S[p..q)) \le k$ and the encoding $\mathrm{D}(S[p..q))$. Initially, $S[p..q) = S[1..1) = \varepsilon$.

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

By Observation 6.7(c), we store $D(X)$ only for strings $X$ satisfying $|\overline{\max L Z}(X)| \le k+1$, so the space usage and the per-iteration running time is $\tilde{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{O}(k)$ per character. $\square$

We maintain two instances of the algorithm of Claim 6.17 and two instances of the algorithm of Proposition 3.16. We feed the first instance of Claim 6.17 with the input stream $S$, obtaining $D(C_k(S, q))$ for subsequent positions $q \in [1..|S|]$. Upon retrieving $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..3n]$ such that $s_v = q$. We also forward $S[q]$ to the second instance of Claim 6.17, obtaining $D(C_k(S, p))$ for all subsequent positions $p$ such that $D(C_k(S, p)) = S[p..q]$. Upon retrieving $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..3n]$ such that $s_t = q$. For each such position $t$, we have $C_k^2(S, s_t) = C_k(S, p)C_k(S, q)$. We compute $\mu_t = \mu(t, \min\{v \in [1..3n] : s_v = q\})$ based on the output of the first instance of Proposition 3.16. If $\mu_t > \mu_{t-1}$, we construct $LZ(C_k^2(S, s_t))$ using Proposition 4.2(i) and Proposition 4.2(f).

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

## 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 \ge \delta \ge n^{-O(1)}$, an alphabet $\Sigma = [0..n^{O(1)})$, and a seed of $O(\log n)$ random bits) such that:

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

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

For two equal-length strings $X, Y$, the set of mismatch positions is defined as $\text{MP}(X, Y) = \{i \in [1..|X|] : X[i] \ne Y[i]\}$ and the mismatch information $\text{MI}(X, Y) = \{(i, X[i], Y[i]) : i \in \text{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 $\text{sk}_k^H$ (parameterized by integers $n \ge k \ge 1$, an alphabet $\Sigma = [0..\sigma)$, and a seed of $O(\log(n \log \sigma))$ random bits) such that:

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

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

*Proof.* The construction of [16] satisfies the required conditions provided that $\sigma = n^{O(1)}$. Henceforth, we assume without loss of generality that $\sigma$ is a power of two satisfying $\sigma \ge n \log \sigma$.
We interpret each character in $\Sigma$ as a block of $b = [\log_n \log \sigma] \text{ characters in } [0..n \log \sigma)$. Moreover, we consider the fingerprints $\psi$ of Fact 6.18 with $\delta_{6.18} = \frac{\delta}{2n}$ and $n_{6.18} = \sigma_{6.18} = n \log \sigma$. This construction uses $O(\log n_{6.18}) = O(\log(n \log \sigma))$ random bits and produces fingerprints of $O(\log \delta_{6.18}^{-1}) = O(\log n)$ bits.

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

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

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

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

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

Next, consider an alphabet $\hat{\Sigma} := \Sigma \times \mathbb{Z}_{\ge 0}$ and a function $\pi : \hat{\Sigma} \to \mathbb{Z}_{\ge 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

$$ \text{PMI}(X, Y) = \{(i, \pi(X[1..i]), \pi(Y[1..i])) : i \in \text{MP}(X, Y)\}. $$

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

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

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

*Proof.* Let us fix a complete binary tree $\mathcal{T}$ with $n$ leaves, numbered with $[1..n]$ in the left-to-right order, and let $v_1, \dots, v_{2n-1}$ denote the nodes of $\mathcal{T}$ in the pre-order. For each node $v_i \in \mathcal{T}$, let $[p_i..q_i) \subseteq [1..n]$ be the indices of the leaves in the subtree of $v_i$. Consider the fingerprints $\psi$ of Fact 6.18 parameterized by $\delta_{6.18} = \frac{\delta}{4n-2}$, $n_{6.18} = O(n \log(n\sigma))$, and $\sigma_{6.18} = 2$: Given a string $S \in \hat{\Sigma}^n$, we define a string $\mathcal{T}(S)[1..2n)$ so that $\mathcal{T}(S)[i] = (\pi(S[p_i..q_i]), \psi(S[p_i..q_i]))$ for every $i \in [1..2n)$, where $\psi$ expands each character of $\hat{\Sigma}$ into a sequence of $O(\log(n\sigma))$ bits.
We set $sk_k^P(S) := sk_{k_{6.19}}^H(T(S))$, where $sk_{k_{6.19}}^H$ is the sketch of Theorem 6.19 with $\delta_{6.19} = \frac{\delta}{2}$, $n_{6.19} = 2n - 1$, $k_{6.19} = \min(k[\log(2n)], n_{6.19})$, and $\sigma_{6.19} \le 2^{\mathcal{O}(\log(n/\delta_{6.18}))} \le n^{\mathcal{O}(1)}$.

This construction uses $\mathcal{O}(\log n_{6.18} + \log(n_{6.19} \log \sigma_{6.19})) = \mathcal{O}(\log(n \log \sigma))$ random bits and produces sketches of $\mathcal{O}(k_{6.19} \log(n_{6.19} \sigma_{6.19})) = \mathcal{O}(k \log^2 n)$ bits.

The encoding algorithm transforms $S$ into $T(S)$ and feeds $T(S)$ into the encoding procedure of Theorem 6.19. Construction of $T(S)$ is organized in $\mathcal{O}(\log n)$ layers, each responsible for nodes $v_i \in T$ at a fixed level. The intervals $[p_i..q_i)$ corresponding to these nodes are disjoint so, at any time, a layer produces a single character $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 $T$ is linearized in the post-order fashion, all levels can read the string $S$ with a common left-to-right pass and outputting $T(S)$ does not require any buffers. Overall, construction of $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_{6.19} \log(n_{6.19} \sigma_{6.19}) \log(n_{6.19} \log \sigma_{6.19})) = \mathcal{O}(n \log^2 n)$ time and uses $\mathcal{O}(k_{6.19} \log(n_{6.19} \sigma_{6.19})) = \mathcal{O}(k \log^2 n)$ bits of space.

The decoding algorithm first retrieves $\mathrm{MI}(T(X), T(Y))$ from $sk_{k_{6.19}}^H(T(X))$ and $sk_{k_{6.19}}^H(T(Y))$ using the decoder of Theorem 6.19. If the output of that subroutine can be interpreted as $\mathrm{MI}(T(X), T(Y))$, then we use Claim 6.21 below to retrieve $\mathrm{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 $\mathrm{hd}(X, Y) > k$.

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

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

Our assumption yields

$$ \mathrm{MP}(T(X), T(Y)) = \{i \in [1..2n) : [p_i..q_i) \cap \mathrm{MP}(X, Y) \neq \emptyset\}. $$

In particular, $\mathrm{MP}(X, Y) = \{p_i : v_i$ is a leaf and $i \in \mathrm{MP}(T(X), T(Y))\}$. Thus, it remains to describe how to extract $\pi(X[1..p))$ and $\pi(Y[1..p))$ for each $p \in \mathrm{MP}(X, Y)$; by symmetry, we focus on $\pi(X[1..p))$. For this, we process subsequent nodes $v_i$ on the path from the root of $T$ to the leaf $v_j$ such that $\{p\} = [p_j..q_j)$ maintaining $\pi(X[1..p_i))$. Note that the values $\pi(X[p_i..q_i))$ can be extracted from $\mathrm{MI}(T(X), T(Y))$ due to $p \in [p_i..q_i)$.

If $v_i$ is the root, then $\pi(X[1..p_i)) = \pi(\varepsilon) = 0$. If $v_i$ is the left child of $v_{i'}$, then $p_i = p_{i'}$, so $\pi(X[1..p_i)) = \pi(X[1..p_{i'}))$ has already been computed. If $v_i$ is the right child of $v_{i'}$, then $q_i = q_{i'}$, so $\pi(X[1..p_i)) + \pi(X[p_i..q_i)) = \pi(X[1..q_i)) = \pi(X[1..q_{i'})) = \pi(X[1..p_{i'})) + \pi(X[p_{i'}..q_{i'}))$. Consequently, $\pi(X[1..p_i))$ can be retrieved from $\pi(X[1..p_{i'}))$, which has already been computed, as well as $\pi(X[p_i..q_i))$ and $\pi(X[p_{i'}..q_{i'}))$, which are available in $\mathrm{MI}(T(X), T(Y))$. When this process reaches $v_j$, it results in the sought value $\pi(X[1..p)) = \pi(X[1..p_j))$. $\square$

It remains to analyze correctness of the decoding algorithm. The decoder of Theorem 6.19 fails with probability at most $\delta_{6.19} = \frac{\delta}{2}$ and the procedure of Claim 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 $\mathrm{hd}(T(X), T(Y)) \le k_{6.19}$, then the decoder of Theorem 6.19 retrieves $\mathrm{MI}(T(X), T(Y))$ and the procedure of Claim 6.21 results in $\mathrm{MI}(X, Y)$. Depending on whether $\mathrm{hd}(X, Y) = |\mathrm{MI}(X, Y)| \le k$ or not, our decoding algorithm thus correctly returns $\mathrm{MI}(X, Y)$ or certifies that $\mathrm{hd}(X, Y) > k$.

Otherwise, the algorithm of Theorem 6.19 certifies $\mathrm{hd}(T(X), T(Y)) > k_{6.19}$, and the whole decoding procedure certifies $\mathrm{hd}(X, Y) > k$. This is correct because of $\mathrm{hd}(T(X), T(Y)) \le$
hd(X, Y) [log(2n)]. To see this, observe that [pᵢ .. qᵢ) ∩ MP(X, Y) = ∅ implies X[pᵢ .. qᵢ) = Y[pᵢ .. qᵢ) and T(X)[i] = T(Y)[i]. However, every leaf of T has at most [log(2n)] ancestors (including itself). Consequently, for every j ∈ MP(X, Y), there are at most [log(2n)] nodes vᵢ such that j ∈ [pᵢ .. qᵢ). □

## 6.4 Edit Distance Sketches

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

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

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

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

*Proof.* Let $c_{3.16}$ be the constant of Proposition 3.16 for $\delta_{3.16} = \frac{\delta}{3}$, and let $c_{6.12}$ be the constant of Lemma 6.12. We shall use $\text{CE}_{k'}(W)$ with $k' = (c_{3.16} + 5)k$ and $W = W(n, r, S)$, where $r$ is a random seed of $\mathcal{O}(\log^2 n)$ bits. Observe that the alphabet of $\text{CE}_{k'}(W)$ can be interpreted as $[0..n^{O(k)}) \times [0..n]$ because the $|\text{LZ}(\tilde{C}_{k'}^2(S, s))| = \mathcal{O}(k)$ for each $s \in [1..|S|]$. We shall use Theorem 6.19 and Proposition 6.20 with $n_{6.19} = n_{6.20} = 3n$, $\delta_{6.19} = \delta_{6.20} = \frac{\delta}{3}$, $k_{6.19} = k_{6.20} = \min(n_{6.19}, \lfloor c_{6.12}(1 + c_{3.16})k \log(3n) \rfloor)$, and $\sigma_{6.19} = \sigma_{6.20} = n^{O(k)}$.

The sketch $\text{sk}_k^E(S)$ of a string $S \in \Sigma^{\le n}$ consists of $|S|$ as well as the sketches $\text{sk}_{k_{6.19}}^H(\text{CE}_{k'}(W))$ and $\text{sk}_{k_{6.20}}^P(\text{CE}_{k'}(W))$. This construction uses

$$ \mathcal{O}(\log^2 n + \log(n_{6.19} \log \sigma_{6.19}) + \log(n_{6.20} \log \sigma_{6.20})) = \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_{6.19} \log(n_{6.19} \sigma_{6.19}) + k_{6.20} \log^2 n_{6.20}) = \mathcal{O}(k \log n \log(n^{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 $\text{CE}_{k'}(W)$, which we forward to the encoders constructing $\text{sk}_{k_{6.19}}^H(\text{CE}_{k'}(S))$ and $\text{sk}_{k_{6.20}}^P(\text{CE}_{k'}(W))$. Thus, it takes $\tilde{\mathcal{O}}(nk' + n_{6.19} \log \sigma_{6.19} + n_{6.20}) = \tilde{\mathcal{O}}(nk)$ time and uses $\tilde{\mathcal{O}}(k' + k_{6.19} \log \sigma_{6.19} + k_{6.20}) = \tilde{\mathcal{O}}(k^2)$ space.

**Decoding Algorithm** Let $\mathcal{A}_W$ be the zip alignment of walks $W_X = (x_t)_{t=1}^{3n+1} = W(n, r, X)$ and $W_Y = (y_t)_{t=1}^{3n+1} = W(n, r, Y)$ over strings $X, Y \in \Sigma^{\le n}$.

Given sketches $\text{sk}_k^E(X)$, $\text{sk}_k^E(Y)$, we run the decoders for $\text{sk}_{k_{6.19}}^H(\text{CE}_{k'}(W_X))$, $\text{sk}_{k_{6.19}}^H(\text{CE}_{k'}(W_Y))$ and $\text{sk}_{k_{6.20}}^P(\text{CE}_{k'}(W_X))$, $\text{sk}_{k_{6.20}}^P(\text{CE}_{k'}(W_Y))$. We certify $\text{ed}(X, Y) > k$ if either procedure certifies $hd(\text{CE}_{k'}(W_X), \text{CE}_{k'}(W_Y)) > k_{6.19} = k_{6.20}$. Otherwise, the decoder interprets the outputs as $\text{MI}(\text{CE}_{k'}(W_X), \text{CE}_{k'}(W_Y))$ and $\text{PMI}(\text{CE}_{k'}(W_X), \text{CE}_{k'}(W_Y))$, respectively. In this case, we construct $\mathbb{E}^M(X, Y)$ for $M = \{(x, y) \in \mathcal{M}_{X,Y}(\mathcal{A}_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 $\text{GR}_k(X, Y)$ using Proposition 5.12 or $\min(\text{ed}(X, Y), k+1)$ using Corollary 5.5.

**Claim 6.22.** Given $\text{MI}(\text{CE}_{k'}(W_X), \text{CE}_{k'}(W_Y))$ and $\text{PMI}(\text{CE}_{k'}(W_X), \text{CE}_{k'}(W_Y))$, the encoding $\mathbb{E}^M(X, Y)$ can be constructed in $\tilde{\mathcal{O}}(k^3)$ time using $\tilde{\mathcal{O}}(k^2)$ space. Moreover, $|\text{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 $D(X')$ of a string $X' \in (\Sigma \cup \{\#\})^{|X'|}$ such that $X'[x] = X[x]$ if $x \in P_X$ and $X'[x] = \#$ otherwise. We initialize $X' := \#^{|X|}$ (via $LZ(\#^{|X|})$ using Proposition 4.2(h)). Next, we iterate over positions $t \in [1 \dots 3n]$ such that $\perp \neq CE_{k'}(W_X)[t] \neq CE_{k'}(W_Y)[t]$. We retrieve $x_t$ and $LZ(C_{k'}^2(X, x_t))$ from the mismatch information, convert $LZ(C_{k'}^2(X, x_t))$ to $D(C_{k'}^2(X, x_t))$ (Proposition 4.2(h)), and update $D(X')$, setting $X'[x_t \dots x_t + |C_{k'}^2(X, x_t)|] := C_{k'}^2(X, x_t)$ (Proposition 4.2(g)(i)). We also symmetrically construct the compressed representation $D(Y')$ of a string $Y' \in (\Sigma \cup \{\#\})^{|Y'|}$ such that $Y'[y] = Y[y]$ if $y \in P_Y$ and $Y'[y] = \#$ otherwise.

In the second phase, we convert $D(X')$ to $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_{AW} Y[y]$ for some $y \in P_Y$. For this, we iterate over dummy segments $Y'[y \dots y']$. By Lemma 6.12, $AW$ matches $Y[y \dots y']$ to a fragment of $X[x \dots x']$. Hence, we shall identify the shift $x-y$ and set $X^M[x \dots x'] := \#^{x'-x}$ (Proposition 4.2(h)(g)(i)). Let $MP_{CE} := MP(CE_{k'}(W_X), CE_{k'}(W_Y))$. Define $u, v \in [1 \dots 3n+1]$ so that $u=v=3n+1$ if $\pi(CE_{k'}(W_Y)[1 \dots t]) \neq y'$ for all $t \in MP_{CE}$; otherwise, $u$ is the smallest index in $MP_{CE}$ with $\pi(CE_{k'}(W_Y)[1 \dots u]) = y'$, whereas $v$ is the smallest index $MP_{CE}$ with $\pi(CE_{k'}(W_Y)[1 \dots v]) = \pi(CE_{k'}(W_Y)[1 \dots u])$. We claim that $x-y = \pi(CE_{k'}(W_X)[1 \dots v]) - \pi(CE_{k'}(W_Y)[1 \dots v])$.

If $y' \le |Y|$, then $y' - 1 \notin P_Y$ and $y' \in P_Y$. Hence, $Y[y']$ is covered by $C_{k'}^2(Y, y_t)$ for some $t \in MP_{CE}$ with $CE_{k'}(W_X)[t] \ne \perp$, whereas $Y[y' - 1]$ is not covered by $C_{k'}^2(Y, y_t)$. Hence, there is $t \in MP_{CE}$ with $y_t = y'$, and therefore $y_u = y'$. Similarly, $y_u = y'$ holds if $y' = |Y| + 1$. Let $w \in [1 \dots 3n]$ be the smallest index such that $CE_{k'}(W_Y)[w] \ne \perp$ and $C_{k'}^2(Y, y_t)$ covers $Y[y' - 1]$ (such an index exists by Lemma 6.9). Due to $y' - 1 \in P_Y$, we have $CE_{k'}(W_X)[w] = CE_{k'}(W_Y)[w]$, and hence $x-y = x_w - y_w$. Definition of $w$ further yields $CE_{k'}(W_Y)[w+1 \dots v) = \perp^{u-w-1}$, and thus $\pi(CE_{k'}(W_Y)[1 \dots v]) = y_w$. Moreover, since $\pi(CE_{k'}(W_Y)[1 \dots t)) = y_w$ for $t \in [w+1 \dots v]$, we have $\pi(CE_{k'}(W_X)[1 \dots v]) = x_w$ by definition of $v$. This completes the proof that $x-y = \pi(CE_{k'}(W_X)[1 \dots v]) - \pi(CE_{k'}(W_Y)[1 \dots v])$.

To derive $E^M(X, Y)$, it suffices to convert $D(Y')$ to $D(Y^M)$ (symmetrically), and to construct $D(X^MY^M)$ using Proposition 4.2(i). Since $\max LZ(C_{k'}^2(X, x_t)), \max LZ(C_{k'}^2(Y, y_t)) = O(k)$ holds for all $t \in [1 \dots 3n+1]$ and since $|MP_{CE}| = O(k \log n)$, the $\max LZ(\cdot)$ measure of all intermediate strings is $\tilde{O}(k^2)$. Consequently, the $\tilde{O}(k)$ applications of Proposition 4.2 cost $\tilde{O}(k^3)$ time and use $\tilde{O}(k^2)$ space. $\square$

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

It remains to argue that the decoding algorithm is correct. With $\delta_{3.16} = \frac{\delta}{3}$ probability loss, we may assume that $A_W \in GA_{c_{3.16}(\text{ed}(X,Y))^2}(X, Y)$ and $\text{width}(A_W) \le c_{3.16}\text{ed}(X, Y)$. With $\delta_{6.19} + \delta_{6.20} = \frac{2\delta}{3}$ further probability loss, we may assume that the decoders of Theorem 6.19 and Proposition 6.20 are successful. If $\text{ed}(X, Y) > k$, then the correctness follows from Proposition 5.12 and Corollary 5.5 because $M \subseteq M_{X,Y}(A_W)$ is a non-crossing matching. Otherwise, Proposition 3.16 guarantees $\text{cost}(A_W) \le c_{3.16}k^2$ and $\text{width}(A_W) \le c_{3.16}k$ so, in particular, $k' \ge \text{width}(A_W) + 5k$. By Lemma 6.12, we thus have $\text{hd}(CE_{k'}(W_X), CE_{k'}(W_X)) \le c_{6.12}(1 + c_{3.16})k \log(3n)$. Hence, the decoders of Theorem 6.19 and Proposition 6.20 report the mismatch information. Lemma 6.10 further implies that $\Delta_X(A, A_W) \subseteq P_X$ and $\Delta_Y(A, A_W) \subseteq P_Y$ for all $A \in GA_k(X, Y)$. In particular, $M_{X,Y}(A) \subseteq M$, and therefore $M_k(X, Y) \subseteq M$. Conse-
quently, the algorithms of Proposition 5.12 and Corollary 5.5 correctly compute $GR_k(X, Y)$ and $\min(\text{ed}(X, Y), k+1)$, respectively. $\square$

Next, we boost the success probability and strengthen the sketches so that we can retrieve $\mathbf{qGR}_k(X, Y)$ instead of $GR_k(X, Y)$.

**Corollary 6.23.** There is a sketch $\mathbf{sk}_k^q$ (parametrized by $\delta \in (0, \frac{1}{2})$, integers $n \ge k \ge 1$, an alphabet $\Sigma = [0..n^{\mathcal{O}(1)})$, and a seed of $\mathcal{O}(\log^2 n \log(1/\delta))$ random bits) such that:

(a) The sketch $\mathbf{sk}_k^q(S)$ of a string $\Sigma^{\le 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.

(b) There exists a decoding algorithm that, given $\mathbf{sk}_k^q(X), \mathbf{sk}_k^q(Y)$ for $X, Y \in \Sigma^{\le n}$, with probability at least $1 - \delta$ computes $\mathbf{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 $\mathbf{sk}_{k_{3.17}}^E$ of Theorem 3.17 with $\delta_{3.17} = \frac{1}{3}$, $n_{3.17} = n + 1$, $k_{3.17} = k + 1$, and independent seeds. For each of the $\mu$ sketches $\mathbf{sk}_{k_{3.17}}^E$, the sketch $\mathbf{sk}_k^q(S)$ contains $\mathbf{sk}_{k_{3.17}}^E(\$_1S)$, $\mathbf{sk}_{k_{3.17}}^E(\$_2S)$, where $\$_1, \$_2 \notin \Sigma$ are two distinct symbols. This construction uses $\tilde{\mathcal{O}}(\mu \log^2 n_{3.17}) = \tilde{\mathcal{O}}(\log^2 n \log(1/\delta))$ random bits and produces sketches of $\mathcal{O}(\mu k_{3.17}^2 \log^3 n_{3.17}) = \mathcal{O}(k^2 \log^3 n \log(1/\delta))$ bits.

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

The decoding algorithm, given $\mathbf{sk}_k^q(X), \mathbf{sk}_k^q(Y)$ for $X, Y \in \Sigma^{\le n}$, runs the decoder of Theorem 3.17 for $\mathbf{sk}_{k_{3.17}}^E(\$_1X), \mathbf{sk}_{k_{3.17}}^E(\$_1Y)$ for each of the $\mu$ sketches $\mathbf{sk}_{k_{3.17}}^E$. This yields $\mu$ candidates for $GR_{k_{3.17}}(\$_1X, \$_2Y)$, which we convert to candidates for $\mathbf{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 $\mathbf{D}(X^M Y^M)$.

Recall that the decoding procedures of Theorem 3.17 use $\tilde{\mathcal{O}}(\mu k_{3.17}^5) = \tilde{\mathcal{O}}(k^5 \log(1/\delta))$ time and $\tilde{\mathcal{O}}(\mu k_{3.17}^2) = \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_{3.17}^2) = \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_{3.17}^5) = \tilde{\mathcal{O}}(k^5 \log(1/\delta))$ time.

As for correctness, since the $\mu$ sketches $\mathbf{sk}_{k_{3.17}}^E$ 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$. $\square$

# 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.

**Definition 3.2 (k-periodic string).** A string $X$ is $k$-periodic if there exists a primitive string $Q$ with $|Q| \le |X|/128k$ such that the edit distance between $X$ and a prefix of $Q^\infty$ is at most $2k$. We call $Q$ a $k$-period of $X$.

**Claim 7.1.** Suppose that a string $X$ is a prefix of a string $Y$, where $|X| < |Y| \le 2|X|$. If $X$ is $k$-periodic with $k$-period $Q$, $|Q| \le |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' \neq Q$. Let $q = |Q|$ and $q' = |Q'|$. Assume first $q \le q'$. Fix an alignment of the smallest cost between $Y$ and a prefix of $(Q')^\infty$. It induces an alignment $A'$ of cost at most $2k$ between $X$ and a prefix of $(Q')^\infty$ and hence generates a partition $X = X_1X_2\dots X_z$, where each $X_i$, $1 \le i \le z-1$, is aligned with $Q'$ and $X_z$ is aligned with a prefix of $Q'$. From $|Q| \le |X|/128k$ we obtain $|X| \ge 128k$ and therefore

$$z \ge (|X| - 2k)/q' \ge \frac{128 - 2}{128} |X|/(|Y|/128k) \gg 20k$$

Consider fragments $X_1X_2X_3X_4$, $X_5X_6X_7X_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 $A'$. Fix an optimal alignment $A$ between $X$ and a prefix $Q^\infty$. The cost of $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'Q'Q'Q'$. On the other hand, $F = \text{suff}(Q)Q^j\text{pref}(Q)$, where $\text{suff}(Q)$ and $\text{pref}(Q)$ are some suffix and some prefix of $Q$, respectively.

Suppose first that $q'$ is a multiple of $q$. In this case, $Q' = (Q[\ell + 1..q]Q[1..\ell])^r$, where $\ell = q - |\text{suff}(Q)|$ and an integer $r$, which contradicts the fact that $Q'$ is primitive. Otherwise, consider the copy of $Q$ that contains $F[q']$. Consider also a substring $QQQ$ of $F$ formed by the copy of $Q$ that contains $F[2q']$, 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'$ is a multiple of $q$), and therefore $Q$ is not primitive, a contradiction.

The case $q > q'$ can be treated analogously. $\square$

Note that Claim 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 $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 \le \ell \le \lfloor \log |P| \rfloor$. Order the prefixes by lengths, and consider two consecutive prefixes $P'$, $P''$. If $P'$ is $k$-periodic with $k$-period $Q'$ while $P''$ is not $k$-periodic, we add two more prefixes to $\Pi$. Namely, if $\ell$ be the maximum integer such that $P[1..\ell]$ is $k$-periodic with $k$-period $Q'$, add to $\Pi$ the prefixes $P[1..\ell]$ and $P[1..\ell+1]$. Note that $P[1..\ell+1]$ is not $k$-periodic by Claim 7.1.

Let $\Pi = \{P_1, P_2, \dots, 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 $O(\log m)$ extra space in total. We also store, for each of the $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 $qGR_{32k}(D, D)$ and $qGR_{30k}(P[\ell_{i-1}+1..\ell_i], D^\infty[1..\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' of Y within edit distance at most $k \le m$ from X, as well as ed(Y', X) itself. The algorithm takes $O(km)$ time and $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 \le i \le z$, consider all $k$-edit occurrences of $P_{i-1}$ in $T[r - \ell_i - k + 1..r]$. We call such occurrences active. We denote the set of right endpoints of the active occurrences by $\text{aOCC}_k^E(P_{i-1}, T)$. By Corollaries 3.3 and 3.5, $\text{aOCC}_k^E(P_{i-1}, T)$ forms $O(k^3)$ chains. For each chain $C$, we store the following information:

1. The leftmost position $lp$ and the size $|C|$ of $C$;

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

3. If $|C| \ge 2$, we store the shift $\Delta$ of the difference $D = Q_{i-1}[1+\Delta \dots q_{i-1}]Q_{i-1}[1 \dots q_{i-1}]$ of $C$.

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

Furthermore, consider the moment when we detect the second position in $C$ (if it exists) and hence the difference $D$ of the chain. Starting from this moment, for every newly added position $p \in C$, at the position $(p+1)$ we start computing the greedy encoding $\text{qGR}_{32k}(T[p+1 \dots p+\Delta_i], D^{\infty}[1 \dots \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 \ge 1$, $r \in \text{aOCC}_k^E(P_i, T)$. Below we consider three possible cases for $i \ge 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 \text{aOCC}_k^E(P_i, T)$ iff one of the following conditions is satisfied:

1. The smallest edit distance from $P_{i-1}$ to a suffix of $T[1..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..r]$ and $P_i$);

2. The smallest edit distance from $P_{i-1}$ to a suffix of $T[1..r-1]$ is at most $k-1$ and $P_i[\ell_i] \ne 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..r]$ and $P_i$);

3. The smallest edit distance from $P_{i-1}$ to a suffix of $T[1..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..r]$ and $P_i$);

4. The smallest edit distance from $P_i$ to a suffix of $T[1..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..r]$ and $P_i$).

We can decide which of the conditions is satisfied, and therefore whether $r \in \text{aOCC}_k^E(P_i, T)$ in $O(k^3)$ time using $\text{aOCC}_k^E(P_{i-1}, T)$ and $\text{aOCC}_k^E(P_i, T)$. Moreover, we can compute the smallest edit distance from $P_i$ to a suffix of $T[1..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: