The Communication Complexity of Pattern Matching with Edits Revisited

Kociumaka, Tomasz; Nogler, Jakob; Wellnitz, Philip

doi:10.4230/LIPIcs.CPM.2026.26

The Communication Complexity of Pattern Matching with Edits Revisited

Tomasz Kociumaka

Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany Jakob Nogler

Massachusetts Institute of Technology, Cambridge, MA, USA Philip Wellnitz

National Institute of Informatics, Tokyo, Japan
The Graduate University for Advanced Studies, SOKENDAI, Tokyo, Japan

Abstract

The decades-old Pattern Matching with Edits problem, given a length- $n$ string $T$ (the text), a length- $m$ string $P$ (the pattern), and a positive integer $k$ (the threshold), asks to list the $k$ -error occurrences of $P$ in $T$ , that is, all fragments of $T$ whose edit distance to $P$ is at most $k$ . The one-way communication complexity of this problem is the minimum number of bits that Alice, given an instance $(P,T,k)$ of the problem, must send to Bob so that Bob can reconstruct the answer solely from that message.

In recent work [STOC’24], we showed that, in the natural parameter regime $0<k<m<n/2$ , $\Omega(n/m\cdot k\log(m/k))$ bits are necessary and $\mathcal{O}(n/m\cdot k\log^{2}m)$ bits are sufficient for this problem. More generally, for strings over an alphabet $\Sigma$ , we gave an $\mathcal{O}(n/m\cdot k\log m\log(m|\Sigma|))$ -bit encoding that allows one to recover a shortest sequence of edits for every $k$ -error occurrence of $P$ in $T$ .

In this paper, we revisit the original proof and improve the encoding size to $\mathcal{O}(n/m\cdot k\log(m|\Sigma|/k))$ , which matches the lower bound for constant-sized alphabets. We further establish a new tight lower bound of $\Omega(n/m\cdot k\log(m|\Sigma|/k))$ for the edit sequence reporting variant we solve. Our encoding size also matches the communication complexity established for the simpler Pattern Matching with Mismatches problem in the context of streaming algorithms [Clifford, Kociumaka, Porat; SODA’19].

Keywords and phrases:

Edit distance, Pattern matching, Communication complexity

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pattern matching ; Theory of computation

\rightarrow

Communication complexity ; Mathematics of computing

\rightarrow

Combinatorics on words

Editors:

Philip Bille and Nicola Prezza

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In the more-than-classic Pattern Matching with Edits problem (PMWE) [22], we are given a text $T$ of length $n$ , a pattern $P$ of length $m$ , and a threshold $k$ , and the task is to compute the starting positions of all substrings of $T$ whose edit distance to $P$ is at most $k$ . Formally, we aim to compute the set

\mathrm{Occ}^{E}_{k}(P,T)\coloneqq\{i\in\bm{[}\,0\,\bm{.\,.}\,n\,\bm{]}:% \exists_{j\in\bm{[}\,i\,\bm{.\,.}\,n\,\bm{]}}\>\delta_{E}(P,T\bm{[}\,i\,\bm{.% \,.}\,j\,\bm{)})\leq k\},

where $\delta_{E}(\star,\star)$ denotes the edit (Levenshtein) distance [21]. This metric quantifies the (dis)similarity between strings by counting the minimum number of single-character edits (insertions, deletions, and substitutions) required to transform one string into the other.

Research into this problem has expanded far beyond the classical setting [22, 19, 20, 9, 5, 6], with modern variants exploring compressed [11, 24, 3, 5], dynamic [5], streaming [23, 17, 2], weighted [7], and quantum [13, 15] settings. We recently investigated the problem’s one-way communication complexity [13], which involves determining the minimum space required to encode an instance so that the set of $k$ -error occurrences can be reconstructed without further access to the original input.

The communication complexity framework models this as a two-party game: Alice, who holds the problem instance, transmits a single message to Bob. Bob’s task is to derive the full output solely from this message. Because Bob lacks any initial input of his own, the problem reduces to a one-way single-round protocol, and the primary objective is to minimize the number of bits Alice must transmit.

In [13], we established that, in the natural parameter regime of $0<k<m<n/2$ , $\Omega(n/m\cdot k\log(m/k))$ bits are necessary for this problem, while $\mathcal{O}(n/m\cdot k\log^{2}m)$ bits are sufficient. More generally, we showed that if the shortest sequence of edits must be recovered for each $k$ -error occurrence, the upper bound increases to $\mathcal{O}(n/m\cdot k\log m\log(m|\Sigma|))$ , where $\Sigma$ is the input alphabet. The former result is implied by the latter by performing a simple alphabet reduction: all characters of $T$ not present in $P$ are mapped to a single character. The result of [13] is significant for three reasons.

1.

A central open question [9, 6] for PMWE is whether a static algorithm can match the $\mathcal{O}(n+n/m\cdot k^{2-\Omega(1)})$ conditional lower bound [1]. The current state-of-the-art algorithm by Charalampopoulos, Kociumaka, and Wellnitz [6] runs in $\tilde{\mathcal{O}}(n+n/m\cdot k^{3.5})$ time, and relies on structural results [5] that allow it to return the required output $\mathrm{Occ}^{E}_{k}(P,T)$ using $\tilde{\mathcal{O}}(n/m\cdot k^{3})$ bits. This encoding is fundamentally incompatible with reaching the lower bound; however, the results of [13] demonstrate that this barrier can indeed be overcome.
2.

A similar question was previously settled for the simpler Pattern Matching with Mismatches problem (PMWM) [8]; here $\Omega(n/m\cdot k\log(m/k))$ bits are necessary and $\mathcal{O}(n/m\cdot k\log(m|\Sigma|/k))$ bits suffice to also report the mismatches for all $k$ -mismatch occurrences. Thus, by [13] and up to essentially an $\mathcal{O}(\log m)$ factor, the edit distance setting behaves the same as the mismatch setting in terms of information density.
3.

Said result of [13] also paves the way for better algorithms in other computational models (e.g., the quantum algorithms for PMWE of [13, 15], which crucially rely on this result). The prior work on PMWM [8] suggests that one-way communication complexity is a stepping stone toward $\tilde{\mathcal{O}}(k)$ -space algorithms in the streaming and semi-streaming models. This is particularly relevant given the concurrent development of $\mathcal{O}(k\cdot n^{o(1)})$ -size edit distance sketches [18]. Although the state-of-the-art sketches do not yet offer the space-efficient sketch construction needed for a full streaming implementation, the advances in [13] represent significant steps toward it.

Our Results.

We re-examine the encoding provided in [13] and, through a series of refinements, eliminate the $\Theta(\log m)$ term separating the upper and lower bounds. Thereby, we place PMWE on par with PMWM. Formally, we show the following result.

Theorem 1.1.

Fix integers $n, m, k$ with $n\geq m\geq k>0$ and an input alphabet $\Sigma$ . The Pattern Matching with Edits problem admits a one-way deterministic communication protocol that sends $\mathcal{O}(n/m\cdot k\log(m|\Sigma|/k))$ bits. Within the same communication complexity, one can also reconstruct the set of all fragments $T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ satisfying $\delta_{E}(P,T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)})\leq k$ and, for each such fragment, the edit information (the positions and values of edited characters) of all optimal edit sequences transforming $P$ into the fragment $T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ .

$\blacktriangleright$ Remark 1.2.

Our result extends routinely beyond $n\geq m\geq k>0$ . If $n<m$ , it suffices to apply Theorem 1.1 with the text $T$ replaced by $\mathtt{0}^{m-n}\cdot T$ , where $\mathtt{0}\in\Sigma$ is an arbitrary character. Applying Theorem 1.1 with threshold $k=m$ allows one to reconstruct the entire pattern from the edit sequence for an empty fragment of the text and the entire text from the edit sequences for single-character fragments; this covers $k>m$ . Finally, the case $k=0$ is no harder than $k=1$ . Thus, in full generality, the communication complexity becomes

\mathcal{O}\left(\max\!\left(1,\tfrac{n}{m}\right)\cdot\min(m,k+1)\cdot\log% \tfrac{m|\Sigma|}{\min(m,k+1)}\right).

Through the aforementioned alphabet reduction, we also achieve $\mathcal{O}(n/m\cdot k\log m)$ bits for the variant where only the positions (but not the values) of edited characters are reported. This suffices for the baseline problem asking for the starting positions of $k$ -error occurrences, which means that we match the lower bound of [13] unless both $k\geq m^{1-o(1)}$ and $|\Sigma|\geq\omega(1)$ .

It is not difficult to show that a single optimal edit sequence for a single $k$ -error occurrence can be encoded using $\mathcal{O}(k\log(m|\Sigma|/k))$ bits. While the previous approach in [13] required storing information proportional to $\mathcal{O}(\log m)$ edit sequences for each length- $\Theta(m)$ block of the text, our improvement achieves the information content equivalent to $\mathcal{O}(1)$ edit sequences. Hence, in a $\Theta(m)$ -length block of $T$ , the cost of encoding all $k$ -error occurrences and their respective edit sequences is asymptotically no greater than the cost of encoding one!

We also establish a new lower bound proving that our protocol is optimal for edit retrieval.

Theorem 1.3.

Fix integers $n, m, k$ with $n\geq m\geq k>0$ and an input alphabet $\Sigma$ with $\mathtt{0}\in\Sigma$ and $|\Sigma|\geq 2$ . Consider an encoding that, for each fragment $T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ with $\delta_{E}(P,T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)})\leq k$ , allows to reconstruct an edit sequence $P\immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure0.pdf}}}% }T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ and the corresponding edit information. Such an encoding must use $\Omega(n/m\cdot k\log(|\Sigma|m/k))$ bits for $P=\mathtt{0}^{m}$ and some $T\in\Sigma^{n}$ .

Our Techniques.

On a very high level, in [13], the text $T$ is first partitioned into $\mathcal{O}(n/m)$ partially overlapping blocks, each of length $\mathcal{O}(m)$ and such that each $k$ -error occurrence of $P$ in $T$ is fully contained in some block. For each such block, the encoding contains:

1.

a set $S$ of $\mathcal{O}(\log m)$ $k$ -error occurrences of $P$ in $T$ , each stored together with an optimal edit sequence using $\mathcal{O}(k\log(m|\Sigma|/k))$ bits;
2.

the Lempel–Ziv LZ77 [25] compressed representation of a collection of fragments of $T$ selected based on $S$ . The total number of LZ77 phrases is proportional to the total cost of $k$ -error occurrences in $S$ , so they can be encoded using $\mathcal{O}(k\log m\log(m|\Sigma|/k))$ bits.

Overall, this yields an encoding cost of $\mathcal{O}(k\log m\log(m|\Sigma|/k))$ bits per block and $\mathcal{O}(n/m\cdot k\log m\log(m|\Sigma|/k))$ bits for the entire text. The underlying construction is relatively complex, relying on recent insights relating edit distance to compressibility [4, 12] via the so-called self-edit distance. Nevertheless, our key improvement is simple to describe at a high level: In (1), we partition the $i$ -th $k$ -error occurrence into $\Theta(2^{i})$ pieces and store the edit information only for the “cheapest” piece, incurring only $k_{i}=\mathcal{O}(k/2^{i})$ edits, for a total of $\mathcal{O}(k)$ instead of $\mathcal{O}(k\log m)$ . The fragments in (2) are defined essentially the same way and, thanks to the decreased total cost in (1), they can be encoded in $\mathcal{O}(k\log(m|\Sigma|/k))$ bits.

Generalizing the relevant concepts to capture pieces of $P$ requires several delicate steps, which we discuss in Section 3. Moreover, our approach breaks for $k=o(\log m)$ since $0$ -error pieces still need a $\Theta(\log m)$ -bit representation, which becomes a bottleneck when $|S|\geq\omega(k)$ . In that case, through the structural characterization of Charalampopoulos, Kociumaka, and Wellnitz [5], the existence of $\omega(k)$ occurrences implies that $P$ and the relevant part of $T$ are at edit distance $\mathcal{O}(k)$ from highly periodic strings. We then use this rigid structure to show that just three $\mathcal{O}(k)$ -error occurrences of $P$ in $T$ can play the role of $S$ in (1).

2 Preliminaries

Sets.

For integers $i,j\in\mathbb{Z}$ , we write $\bm{[}\,i\,\bm{.\,.}\,j\,\bm{]}$ to denote the set $\{i,\dots,j\}$ and $\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ to denote the set $\{i,\dots,j-1\}$ ; we define the sets $\bm{(}\,i\,\bm{.\,.}\,j\,\bm{]}$ and $\bm{(}\,i\,\bm{.\,.}\,j\,\bm{)}$ similarly.

For a set $S$ of integers and a parameter $k>0$ , we also define $\lfloor S/k\rfloor\coloneqq\{\lfloor s/k\rfloor:s\in S\}$ .

Strings.

An alphabet $\Sigma$ is a set of characters. We write $X=X\bm{[}\,0\,\bm{]}\,X\bm{[}\,1\,\bm{]}\cdots X\bm{[}\,n-1\,\bm{]}\in\Sigma^{n}$ to denote a string of length $|X|=n$ over $\Sigma$ . For a position $i\in\bm{[}\,0\,\bm{.\,.}\,n\,\bm{)}$ , we say that $X\bm{[}\,i\,\bm{]}$ is the $i$ -th character of $X$ . A string $Y$ is a substring of another string $X$ if $Y=X\bm{[}\,i\,\bm{]}\cdots X\bm{[}\,j-1\,\bm{]}$ holds for some integers $0\leq i\leq j\leq|X|$ . In this case, we say that there is an (exact) occurrence of $Y$ starting at position $i$ in $X$ . The occurrence is a fragment of $X$ denoted $X\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ ; formally, the fragment can be interpreted as a tuple $(X,i,j)$ consisting of a (reference to) $X$ and the two positions $i$ and $j$ . We may also write $X\bm{[}\,i\,\bm{.\,.}\,j-1\,\bm{]}$ , $X\bm{(}\,i-1\,\bm{.\,.}\,j-1\,\bm{]}$ , or $X\bm{(}\,i-1\,\bm{.\,.}\,j\,\bm{)}$ for the fragment $X\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ . A prefix of a string $X$ is a fragment of the form $X\bm{[}\,0\,\bm{.\,.}\,j\,\bm{)}$ , and a suffix of a string $X$ is a fragment of the form $X\bm{[}\,i\,\bm{.\,.}\,|X|\,\bm{)}$ .

For two strings $A$ and $B$ , we write $A B$ for their concatenation. We write $A^{k}$ for the concatenation of $k\in\mathbb{Z}_{\geq 0}$ copies of the string $A$ . Moreover, $A^{\infty}$ is an infinite string (indexed with non-negative integers) formed as the concatenation of an infinite number of copies of $A$ .

An integer $p\in\bm{[}\,1\,\bm{.\,.}\,n\,\bm{]}$ is a period of a string $X\in\Sigma^{n}$ if we have $X\bm{[}\,i\,\bm{]}=X\bm{[}\,i+p\,\bm{]}$ for all $i\in\bm{[}\,0\,\bm{.\,.}\,n-p\,\bm{)}$ . In this case, we also say that the string $X\bm{[}\,0\,\bm{.\,.}\,p\,\bm{)}$ is a string period of $X$ . In other words, a string $P$ is a string period of a string $X$ if $X$ is a prefix of $P^{\infty}$ and $|P|\leq|X|$ . The period of a non-empty string $X$ , denoted $\operatorname{per}(X)$ , is the smallest period of $X$ . A non-empty string $X$ is periodic if $\operatorname{per}(X)\leq|X|/2$ .

Periodicity Lemma.

For completeness, we restate Fine and Wilf’s Periodicity Lemma [10].

Lemma 2.1 (Periodicity Lemma [10]).

If $p, q$ are periods of a string $X$ of length $|X|\geq p+q-\gcd(p,q)$ , then $\gcd(p,q)$ is a period of $X$ .

Edit Distance and Alignments.

The edit distance (Levenshtein distance [21]) between two strings $X$ and $Y$ , denoted by $\delta_{E}(X,Y)$ , is the minimum number of character insertions, deletions, and substitutions required to transform $X$ into $Y$ . Formally, we first define an alignment between string fragments.

Definition 2.2 ([6, Definition 2.1]).

A sequence $\mathcal{A}=(x_{i},y_{i})_{i=0}^{\ell}$ is an alignment of $X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}$ onto $Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ , denoted by $\mathcal{A}:X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.407pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure1.pdf}}}}Y\bm{[}\,y\,\bm{.\,.}\,y^{% \prime}\,\bm{)}$ , if it satisfies $(x_{0},y_{0})=(x,y)$ , $(x_{i+1},y_{i+1})\in\{(x_{i}+1,\allowbreak y_{i}+1),(x_{i}+1,\allowbreak y_{i}% ),(x_{i},y_{i}+1)\}$ for $i\in\bm{[}\,0\,\bm{.\,.}\,\ell\,\bm{)}$ , and $(x_{\ell},y_{\ell})=(x^{\prime},y^{\prime})$ . Moreover, for $i\in\bm{[}\,0\,\bm{.\,.}\,\ell\,\bm{)}$ :

$\blacksquare$

If $(x_{i+1},y_{i+1})=(x_{i}+1,y_{i})$ , we say that $\mathcal{A}$ deletes $X\bm{[}\,x_{i}\,\bm{]}$ .
$\blacksquare$

If $(x_{i+1},y_{i+1})=(x_{i},y_{i}+1)$ , we say that $\mathcal{A}$ inserts $Y\bm{[}\,y_{i}\,\bm{]}$ .
$\blacksquare$

If $(x_{i+1},y_{i+1})=(x_{i}+1,y_{i}+1)$ , we say that $\mathcal{A}$ aligns $X\bm{[}\,x_{i}\,\bm{]}$ to $Y\bm{[}\,y_{i}\,\bm{]}$ . If also $X\bm{[}\,x_{i}\,\bm{]}=Y\bm{[}\,y_{i}\,\bm{]}$ , then $\mathcal{A}$ matches $X\bm{[}\,x_{i}\,\bm{]}$ and $Y\bm{[}\,y_{i}\,\bm{]}$ ; otherwise, $\mathcal{A}$ substitutes $X\bm{[}\,x_{i}\,\bm{]}$ with $Y\bm{[}\,y_{i}\,\bm{]}$ .

The cost of an alignment $\mathcal{A}$ of $X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}$ onto $Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ , denoted by $\operatorname{cost}(\mathcal{A})$ or $\delta_{E}^{\mathcal{A}}(X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)},Y\bm{[}\,y% \,\bm{.\,.}\,y^{\prime}\,\bm{)})$ , is the total number of characters that $\mathcal{A}$ inserts, deletes, or substitutes. The edit distance $\delta_{E}(X,Y)$ is the minimum cost of an alignment of $X\bm{[}\,0\,\bm{.\,.}\,|X|\,\bm{)}$ onto $Y\bm{[}\,0\,\bm{.\,.}\,|Y|\,\bm{)}$ . An alignment of $X$ onto $Y$ is optimal if its cost is equal to $\delta_{E}(X,Y)$ .

Given an alignment $\mathcal{A}:X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.33298pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure2.pdf}}}}Y\bm{[}\,y\,\bm{.\,.}\,y^{% \prime}\,\bm{)}$ and a fragment $X\bm{[}\,\bar{x}\,\bm{.\,.}\,\bar{x}^{\prime}\,\bm{)}$ contained in $X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}$ , we write $\mathcal{A}(X\bm{[}\,\bar{x}\,\bm{.\,.}\,\bar{x}^{\prime}\,\bm{)})$ for the fragment $Y\bm{[}\,\bar{y}\,\bm{.\,.}\,\bar{y}^{\prime}\,\bm{)}$ of $Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ that $\mathcal{A}$ aligns against $X\bm{[}\,\bar{x}\,\bm{.\,.}\,\bar{x}^{\prime}\,\bm{)}$ . As insertions and deletions may render this definition ambiguous, we set

\bar{y}\coloneqq\min\{\hat{y}:(\bar{x},\hat{y})\in\mathcal{A}\}\quad\text{and}% \quad\bar{y}^{\prime}\coloneqq\left\{\begin{array}[]{c l}y^{\prime}&\text{if }% \bar{x}^{\prime}=x^{\prime},\\ \min\{\hat{y}^{\prime}:(\bar{x}^{\prime},\hat{y}^{\prime})\in\mathcal{A}\}&% \text{otherwise}.\end{array}\right.

This particular choice satisfies the following decomposition property.

Observation 2.3 ([6, Fact 2.2]).

For an alignment $\mathcal{A}:X\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure3.pdf}}}}Y$ and a decomposition $X=X_{1}\cdots X_{t}$ into $t$ fragments, $Y=\mathcal{A}(X_{1})\cdots\mathcal{A}(X_{t})$ is a decomposition into $t$ fragments with $\delta_{E}^{\mathcal{A}}(X,Y)=\sum_{i=1}^{t}\delta_{E}^{\mathcal{A}}(X_{i},% \mathcal{A}(X_{i}))$ . If $\mathcal{A}$ is optimal, then $\delta_{E}(X,Y)=\sum_{i=1}^{t}\delta_{E}(X_{i},\mathcal{A}(X_{i}))$ .

We use the following edit information notion to encode alignments.

Definition 2.4 (Edit information of an alignment).

For an alignment $(x_{i},y_{i})_{i=0}^{\ell}\!=\mathcal{A}:X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,% \bm{)}\immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure4.pdf}}}% }Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ , the edit information is the set of 4-tuples $\mathsf{E}_{X,Y}(\mathcal{A})=\{(x_{i},\mathsf{cx}_{i}:y_{i},\mathsf{cy}_{i}):% i\in\bm{[}\,0\,\bm{.\,.}\,\ell\,\bm{)}\text{ and }\mathsf{cx}_{i}\neq\mathsf{% cy}_{i}\}$ , where

\mathsf{cx}_{i}=\left\{\begin{array}[]{@{\;}c@{\quad}l@{}}X\bm{[}\,x_{i}\,\bm{% ]}&\text{if }x_{i+1}=x_{i}+1,\\ \varepsilon&\text{otherwise};\end{array}\right.\qquad\text{and}\qquad\mathsf{% cy}_{i}=\left\{\begin{array}[]{@{\;}c@{\quad}l@{}}Y\bm{[}\,y_{i}\,\bm{]}&\text% {if }y_{i+1}=y_{i}+1,\\ \varepsilon&\text{otherwise}.\end{array}\right.

By monotonicity of the alignment, the order of the tuples $(x_{i},\mathsf{cx}_{i}:y_{i},\mathsf{cy}_{i})$ with respect to $i$ coincides with their lexicographic order by $(x_{i},y_{i})$ and by $(y_{i},x_{i})$ .

Observe that, given two strings $X$ and $Y$ , the endpoints $x,x^{\prime},y,y^{\prime}$ , and the edit information $\mathsf{E}_{X,Y}(\mathcal{A})$ of an alignment $\mathcal{A}:X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.33298pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure5.pdf}}}}Y\bm{[}\,y\,\bm{.\,.}\,y^{% \prime}\,\bm{)}$ , we are able to fully reconstruct $\mathcal{A}$ . Indeed, each tuple of $\mathsf{E}_{X,Y}(\mathcal{A})$ specifies a non-matching operation, whereas all pairs of $\mathcal{A}$ before the first tuple, between consecutive tuples, and after the last tuple must be matches. Moreover, given the characters of $X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}$ and the edit information $\mathsf{E}_{X,Y}(\mathcal{A})$ , one can recover the characters of $Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ . Indeed, the tuples of $\mathsf{E}_{X,Y}(\mathcal{A})$ reveal all characters of $Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ created by insertions and substitutions, while the remaining characters of $Y\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ correspond to matches and can therefore be copied from $X\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}$ .

Pattern Matching with Edits.

In the context of two strings $P$ (referred to as the pattern) and $T$ (referred to as the text), along with a positive integer $k$ (referred to as the threshold), we say that $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ is a $k$ -error occurrence of $P$ in $T$ if $\delta_{E}(P,T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)})\leq k$ holds.

3 Upper Bound: Proof Overview

In this section, we provide an overview of the proof of Theorem 1.1¹¹1This paper provides an overview of the full version [16].. To this end, we fix two strings $P\in\Sigma^{m}$ and $T\in\Sigma^{n}$ , and a positive threshold $k$ . Throughout this section, we assume that $k=o(m)$ , $n\leq 2m-2k$ , and $P$ has $k$ -error occurrences as a prefix and as a suffix of $T$ . In [13, Claim 4.31²²2All references to numbers of theorems, lemmas, and definitions of [13] refer to their full version [14].], a standard block-splitting argument is employed to demonstrate that a protocol using $\mathcal{O}(k\log m\log(m|\Sigma|))$ bits for this specific case is sufficient to achieve $\mathcal{O}(n/m\cdot k\log m\log(m|\Sigma|))$ bits in general. We improve the former communication bound to $\mathcal{O}(k\log(m|\Sigma|/k))$ bits and a similar proof to [13, Claim 4.31] to drop the assumptions.

The remainder of this section is structured as follows. In Section 3.1, we provide a concise overview of the proof from [13], focusing specifically on the components we adapt to achieve our improvements. Subsequently, in Section 3.2, we outline our improved construction.

3.1 Previous Encoding

3.1.1 The Graph $\mathbf{G}_{S}$ and the Induced Periodic Structure

The main ingredient of the encoding of [13] is a set $S$ of $\mathcal{O}(\log m)$ alignments of $P$ onto fragments of $T$ with cost at most $k$ each. The starting point of [13] is to analyze how much information such a set of alignments carries, in order to better understand how one should choose which alignments to include and what additional information is needed to fully encode $\mathrm{Occ}^{E}_{k}(P,T)$ . To enable this analysis, the set $S$ is associated with a graph $\mathbf{G}_{S}$ , which we call the inference graph.

Definition 3.1 ([13, Definition 4.1]).

Let $S$ be a set of alignments $\mathcal{X}:P\bm{[}\,p\,\bm{.\,.}\,p^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.407pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure6.pdf}}}}T\bm{[}\,t\,\bm{.\,.}\,t^{% \prime}\,\bm{)}$ . We define the undirected graph $\mathbf{G}_{S}=(V,E)$ as follows. The vertex set $V$ contains

1.

$|P|$ vertices representing characters of $P$ ;
2.

$|T|$ vertices representing characters of $T$ ; and
3.

one special vertex $\bot$ .

The edge set $E$ contains the following edges for each alignment $\mathcal{X}\in S$ .

1.

$\{P\bm{[}\,x\,\bm{]},\bot\}$ for every character $P\bm{[}\,x\,\bm{]}$ that $\mathcal{X}$ deletes;
2.

$\{\bot,T\bm{[}\,y\,\bm{]}\}$ for every character $T\bm{[}\,y\,\bm{]}$ that $\mathcal{X}$ inserts;
3.

$\{P\bm{[}\,x\,\bm{]},T\bm{[}\,y\,\bm{]}\}$ for every pair of characters $P\bm{[}\,x\,\bm{]}$ and $T\bm{[}\,y\,\bm{]}$ that $\mathcal{X}$ aligns.

We say that an edge $\{P\bm{[}\,x\,\bm{]},T\bm{[}\,y\,\bm{]}\}$ is black if $\mathcal{X}$ matches $P\bm{[}\,x\,\bm{]}$ and $T\bm{[}\,y\,\bm{]}$ . All other edges are red.

A connected component of $\mathbf{G}_{S}$ is red if it contains at least one red edge; otherwise, the connected component is black. We denote the number of black components with $\operatorname{bc}(\mathbf{G}_{S})$ .

Note that all vertices contained in black components correspond to characters of $P$ and $T$ . Moreover, all characters of a single black component are the same, because the presence of a black edge indicates that some alignment in $S$ matches the two corresponding characters.

The inference graph $\mathbf{G}_{S}$ is represented implicitly via the edit information $\mathsf{E}_{P,T}(\mathcal{X})$ for each alignment $\mathcal{X}:P\bm{[}\,p\,\bm{.\,.}\,p^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.33298pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure7.pdf}}}}T\bm{[}\,t\,\bm{.\,.}\,t^{% \prime}\,\bm{)}$ in $S$ . In [13] we naively use the fact that $\mathcal{O}(k\log(m|\Sigma|))$ bits suffice to encode this information; here, we provide a (slightly) more efficient encoding argument that is required to obtain our tight results for small alphabets.

Lemma 3.2.

Let $S$ be a set of alignments $\mathcal{X}:P\bm{[}\,p\,\bm{.\,.}\,p^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.407pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure8.pdf}}}}T\bm{[}\,t\,\bm{.\,.}\,t^{% \prime}\,\bm{)}$ . The set $\{\mathsf{E}_{P,T}(\mathcal{X}):\mathcal{X}\in S\}$ together with the starting/ending points for each $\mathcal{X}\in S$ can be encoded using

\mathcal{O}\left(|S|\log m+\sum\nolimits_{\mathcal{X}\in S:\operatorname{cost}% (\mathcal{X})>0}\operatorname{cost}(\mathcal{X})\cdot\log\left(\tfrac{m|\Sigma% |}{\operatorname{cost}(\mathcal{X})}\right)\right)\text{ bits.}

This information, together with the bit encoding of $n=|T|$ and $m=|P|$ , suffices to fully reconstruct the complete edge set of $\mathbf{G}_{S}$ and the color of each edge. Moreover, this information suffices to identify the character $\sigma\in\Sigma$ for every node in a red component.

Proof.

For each $\mathcal{X}\in S$ with $\operatorname{cost}(\mathcal{X})>0$ , the elements in $\mathsf{E}_{P,T}(\mathcal{X})$ are monotone in their first and third components. Using a “stars and bars” encoding, these components take $\mathcal{O}(\log\binom{m+\operatorname{cost}(\mathcal{X})}{\operatorname{cost}% (\mathcal{X})})$ bits. If $\operatorname{cost}(\mathcal{X})\leq k=o(m)$ , this simplifies to $\mathcal{O}(\operatorname{cost}(\mathcal{X})\log(m/\operatorname{cost}(% \mathcal{X})))$ . The second and fourth components are encoded separately using $\mathcal{O}(\operatorname{cost}(\mathcal{X})\log|\Sigma|)$ bits. For each $\mathcal{X}\in S$ with $\operatorname{cost}(\mathcal{X})=0$ we only need to store the endpoints using $\mathcal{O}(\log m)$ bits each.

Finally, for every character in $P$ and $T$ within a red component, there exists a path of black edges (possibly of length zero) connecting that character to one incident to a red edge. Since black edges connect identical characters, the character value is invariant along this path. Because we explicitly store all characters incident to red edges, we can deduce the character at the origin of any such path. $\hfill\blacktriangleleft$

Lemma 3.2 provides an encoding that reveals all characters contained in red components of in the inference graph $\mathbf{G}_{S}$ . Thus, the case $\operatorname{bc}(\mathbf{G}_{S})=0$ is easy as we can then fully retrieve $P$ and $T$ .

Consequently, we assume $\operatorname{bc}(\mathbf{G}_{S})>0$ for the rest of the section, as this is the remaining case. Even though one cannot learn the characters in black components via the edit information $\mathsf{E}_{P,T}(\mathcal{X})$ for each alignment $\mathcal{X}:P\bm{[}\,p\,\bm{.\,.}\,p^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.33298pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure9.pdf}}}}T\bm{[}\,t\,\bm{.\,.}\,t^{% \prime}\,\bm{)}$ in $S$ (and storing all of them would be prohibitive), one can still infer which character belongs to which component.

The key observation of [13] is that black components are extremely structured and appear in a periodic fashion. To make this structure more formal, we define two strings, $T_{|S}$ and $P_{|S}$ , obtained by retaining only the characters that belong to black connected components.

Definition 3.3 ([13, Definition 4.3]).

Let $T_{|S}$ and $P_{|S}$ denote the subsequences of $T$ and $P$ , respectively, consisting of the characters contained in black components of $\mathbf{G}_{S}$ . We denote the lengths of $T_{|S}$ and $P_{|S}$ by $n_{S}$ and $m_{S}$ , respectively.

The first structural observation is that the black edges of the inference graph $\mathbf{G}_{S}$ induced by a single alignment $\mathcal{X}\in S$ correspond to an exact occurrence of $P_{|S}$ in $T_{|S}$ .

Lemma 3.4 ([13, Claim 4.5]).

Let $\mathcal{X}:P\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure10.pdf}}% }}T\bm{[}\,y\,\bm{.\,.}\,y^{\prime}\,\bm{)}\in S$ , and define $y_{\mathcal{X}},y_{\mathcal{X}}^{\prime}\in\bm{[}\,0\,\bm{.\,.}\,n_{S}\,\bm{]}$ as the number of characters of $T_{|S}$ contained in $T\bm{[}\,0\,\bm{.\,.}\,y\,\bm{)}$ and $T\bm{[}\,0\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ , respectively. Then, we have $P_{|S}=T_{|S}\bm{[}\,y_{\mathcal{X}}\,\bm{.\,.}\,y^{\prime}_{\mathcal{X}}\,\bm% {)}$ , and $\mathcal{X}$ induces edges between $P_{|S}\bm{[}\,p\,\bm{]}$ and $T_{|S}\bm{[}\,y_{\mathcal{X}}+p\,\bm{]}$ for every $p\in\bm{[}\,0\,\bm{.\,.}\,|P_{|S}|\,\bm{)}$ , and no other edges incident to characters of $P_{|S}$ or $T_{|S}$ .

Many overlapping exact occurrences induce periods of the pattern; thus, in [13] we enforce the following condition on $S$ to ensure the induced exact matchings overlap.

Definition 3.5 ([13, Definition 4.2]).

We say $S$ encloses $T$ if $|T|\leq 2|P|-2k$ and there exist two alignments $\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}}\in S$ such that $\mathcal{X}_{\mathsf{pref}}$ aligns $P$ with a prefix of $T$ and $\mathcal{X}_{\mathsf{suf}}$ aligns $P$ with a suffix of $T$ , or equivalently $(0,0)\in\mathcal{X}_{\mathsf{pref}}$ and $(|P|,|T|)\in\mathcal{X}_{\mathsf{suf}}$ .

Given this condition on $S$ , we show that not only are $P_{|S}$ and $T_{|S}$ periodic, but even the membership of their characters in black components follows a periodic structure.

Lemma 3.6 ([13, Lemma 4.4]).

If $S$ encloses $T$ , then, for every $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , there is a black connected component with node set $\{P_{|S}\bm{[}\,i\,\bm{]}:i\equiv_{\operatorname{bc}(\mathbf{G}_{S})}c\}\cup\{% T_{|S}\bm{[}\,i\,\bm{]}:i\equiv_{\operatorname{bc}(\mathbf{G}_{S})}c\}$ , that is, a black connected component containing all characters of $P_{|S}$ and $T_{|S}$ appearing at positions congruent to $c$ modulo $\operatorname{bc}(\mathbf{G}_{S})$ . Moreover, the last characters of $P_{|S}$ and $T_{|S}$ are contained in the same black connected component, that is, $|T_{|S}|\equiv_{\operatorname{bc}(\mathbf{G}_{S})}|P_{|S}|$ .

Lemma 3.6 allows us to define the following quantities related to the periodic structure:

$\blacksquare$

For $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , we define the $c$ -th black connected component as the black connected component containing $P_{|S}[c]$ and set $m_{c}:=\left\lceil(m_{S}-c)/\operatorname{bc}(\mathbf{G}_{S})\right\rceil$ and $n_{c}:=\left\lceil(n_{S}-c)/\operatorname{bc}(\mathbf{G}_{S})\right\rceil$ as the number of characters in $P$ and $T$ , respectively, that belong to the $c$ -th black connected component.
$\blacksquare$

For $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ and $j\in\bm{[}\,0\,\bm{.\,.}\,m_{c}\,\bm{)}$ , we define $\pi_{j}^{c}\in\bm{[}\,0\,\bm{.\,.}\,m\,\bm{)}$ as the position of $P_{|S}\bm{[}\,c+j\cdot\operatorname{bc}(\mathbf{G}_{S})\,\bm{]}$ in $P$ . Similarly, for $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ and $i\in\bm{[}\,0\,\bm{.\,.}\,n_{c}\,\bm{)}$ , we define $\tau_{i}^{c}\in\bm{[}\,0\,\bm{.\,.}\,n\,\bm{)}$ as the position of $T_{|S}\bm{[}\,c+i\cdot\operatorname{bc}(\mathbf{G}_{S})\,\bm{]}$ in $T$ . Note that, for any $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , the characters $\{T\bm{[}\,\tau_{i}^{c}\,\bm{]}\}^{n_{c}-1}_{i=0}\cup\{P\bm{[}\,\pi_{j}^{c}\,% \bm{]}\}^{m_{c}-1}_{j=0}$ are exactly those in the $c$ -th black component. Consequently, they are all identical.

3.1.2 Constructing $𝑺$ and the Encoding

In [13], based on $S$ and a weight $w=\mathcal{O}(k|S|)$ , we identify a subset of black components $C_{S}\subseteq\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ so that the characters $P\bm{[}\,\pi_{0}^{c}\,\bm{]}$ with $c\in C_{S}$ belong to fragments of $T$ whose LZ77 parses consist of $w=\mathcal{O}(k|S|)$ phrases in total. The construction ensures several desirable properties specified below. This is the most technical component of [13], and it is not significantly affected by our modifications, so we omit deeper insights here.

These desirable properties concern all fragments $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ such that if we were to align $P$ onto $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ , then $\pi_{0}^{0}$ would be close enough to $\tau_{i}^{0}$ for some $i\in\bm{[}\,0\,\bm{.\,.}\,n_{0}\,\bm{)}$ . More formally:

Definition 3.7 ([13, Definition 4.28]).

We say that $S$ captures $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ if $S$ encloses $T$ and either $\operatorname{bc}(\mathbf{G}_{S})=0$ or $|\tau_{i}^{0}-t-\pi_{0}^{0}|\leq w+3k$ holds for some $i\in\bm{[}\,0\,\bm{.\,.}\,n_{0}\,\bm{)}$ .

For all such $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ , the information carried by $S$ and $C_{S}$ is sufficient to infer whether $\delta_{E}(P,T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)})\leq k$ and, if so, provide the exact distance and infer the edit sequence.

Theorem 3.8 ([13, Corollary 4.30]).

Let $S$ be a set of $k$ -edit alignments of $P$ onto fragments of $T$ such that $S$ encloses $T$ and $\operatorname{bc}(\mathbf{G}_{S})>0$ . Construct $P^{\#}$ and $T^{\#}$ by replacing, for every $c\notin C_{S}$ , every character in the $c$ -th black component with a unique character $\#_{c}$ .

If $S$ captures all $k$ -error occurrences, then

1.

$\delta_{E}(P,T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)})=\delta_{E}(P^{\#},T^{% \#}\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)})$ and $\mathsf{E}_{P,T}(\mathcal{X})=\mathsf{E}_{P^{\#},T^{\#}}(\mathcal{X})$ for all optimal alignments $\mathcal{X}:P\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure11.pdf}}% }}T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ of cost at most $k$ .
2.

$\delta_{E}(P,T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)})\leq\delta_{E}(P^{\#},T% ^{\#}\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)})$ for all integers $0\leq t\leq t^{\prime}\leq n$ .

Theorem 3.8 makes sure that one can encode the desired information for all captured $k$ -error occurrences. For those that are not captured, the following result is shown in [13].

Lemma 3.9 ([13, Lemma 4.27]).

Let $\mathcal{Y}:P\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure12.pdf}}% }}T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ be an alignment of cost at most $k$ . If $|\tau_{i}^{0}-t-\pi_{0}^{0}|>w+2k$ holds for every $i\in\bm{[}\,0\,\bm{.\,.}\,n_{0}-m_{0}\,\bm{]}$ , then there is no $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ such that $\mathcal{Y}$ aligns $P\bm{[}\,\pi_{0}^{c}\,\bm{]}$ with $T\bm{[}\,\tau_{i}^{c}\,\bm{]}$ for some $i\in\bm{[}\,0\,\bm{.\,.}\,n_{c}\,\bm{)}$ .

An alignment $\mathcal{Y}$ as in Lemma 3.9 satisfies $\operatorname{bc}(\mathbf{G}_{S\cup\{\mathcal{Y}\}})\leq\operatorname{bc}(% \mathbf{G}_{S})/2$ , since each black component becomes red or is merged with another black component. Thus, adding $\mathcal{Y}$ to $S$ allows for significant progress towards $\operatorname{bc}(\mathbf{G}_{S})=0$ . Altogether, the construction proceeds as follows.

$\blacksquare$

In the beginning, we set $S=\{\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}}\}$ .
$\blacksquare$

While $S$ does not capture all $k$ -error occurrences, select an uncaptured $k$ -error occurrence $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ and add to $S$ an optimal alignment $\mathcal{Y}:P\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.33298pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure13.pdf}% }}}T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ .
$\blacksquare$

Return the edit information $\mathsf{E}_{P,T}(\mathcal{X})$ for alignments $\mathcal{X}\in S$ , encoded using Lemma 3.2, and the set $\{(c,P\bm{[}\,\pi_{0}^{c}\,\bm{]}):c\in C_{S}\}$ , encoded using the LZ77-compressed fragments of $P$ .

Since the second step can be executed at most $\mathcal{O}(\log m)$ times before $S$ captures all $k$ -error occurrences, the entire encoding requires $\mathcal{O}(k\log m\log(m|\Sigma|/k))$ bits. To decode, it suffices to retrieve the inference graph $\mathbf{G}_{S}$ from the edit information and, using the encoding of $C_{S}$ as described in Theorem 3.8, construct $P^{\#}$ and $T^{\#}$ , which preserve the solution to the original problem.

3.2 Improved Encoding

To tighten our upper bound on the communication complexity, we revisit the step where an uncaptured alignment $\mathcal{Y}$ is added to $S$ . For this, we strengthen the conclusion of Lemma 3.9, which applies only to the initial character $P\bm{[}\,\pi_{0}^{c}\,\bm{]}$ of each black component $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ . In the full version version, we prove that $\mathcal{Y}$ cannot match any characters within the same black component.

Lemma 3.10.

Let $\mathcal{Y}:P\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure14.pdf}}% }}T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ be an optimal alignment with $\operatorname{cost}(\mathcal{Y})\leq k$ . If $C_{S}\neq\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ and $|\tau_{i}^{0}-t-\pi_{0}^{0}|>w+2k$ holds for every $i\in\bm{[}\,0\,\bm{.\,.}\,n_{0}\,\bm{)}$ , then there is no $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ such that $\mathcal{Y}$ aligns $P\bm{[}\,\pi_{j}^{c}\,\bm{]}$ with $T\bm{[}\,\tau_{i}^{c}\,\bm{]}$ for some $i\in\bm{[}\,0\,\bm{.\,.}\,n_{c}\,\bm{)}$ and $j\in\bm{[}\,0\,\bm{.\,.}\,m_{c}\,\bm{)}$ .

Lemma 3.10 brings us to the main idea of our improvement: rather than adding an entire uncaptured alignment $\mathcal{Y}$ to $S$ , it suffices to add only the subset of edges required to merge every black component with another component. More specifically, if we decompose $P$ into

P\bm{[}\,0\,\bm{.\,.}\,\pi_{0}^{0}\,\bm{)}\circ\left(\bigcirc_{j=0}^{m_{0}-2}P% \bm{[}\,\pi_{j}^{0}\,\bm{.\,.}\,\pi_{j+1}^{0}\,\bm{)}\right)\circ P\bm{[}\,\pi% _{m_{0}-1}^{0}\,\bm{.\,.}\,|P|\,\bm{)},

then at least one of the middle $m_{0}-1$ fragments of $P$ in this decomposition carries at most $\mathcal{O}(k/m_{0})$ edits in $\mathcal{Y}$ . So ideally, we would like to add to $S$ and the corresponding edges $\mathcal{Y}$ restricted to this fragment. If we managed to show that the periodic structure is preserved already by adding such a subset, then not only $\operatorname{bc}(\mathbf{G}_{S})$ would halve, but also the parameter $m_{0}$ would at least double in each iteration. Hence, with this new strategy, we could hope that the total cost of alignment or partial alignment in $S$ is bounded by $\sum_{i=1}^{\infty}k/2^{i}=\mathcal{O}(k)$ .

On a technical level, the proof is delicate: The selection of the fragment $P\bm{[}\,\pi_{j}^{0}\,\bm{.\,.}\,\pi_{j+1}^{0}\,\bm{)}$ , as described so far, depends on $\mathcal{Y}$ and the black components defined relative to $S$ . However, the structure of the black components changes when going from $S$ to $S\cup\mathcal{Y}$ , and the fragment is not guaranteed to contain the same black components as in $S\cup\mathcal{Y}$ . Thus, for our proof of correctness, we need to be careful to get rid of any such undesired dependence on the future.

Finally, we note that Lemma 3.10 is not a strict strengthening of Lemma 3.9, as it introduces three additional conditions: now $i\in\bm{[}\,0\,\bm{.\,.}\,n_{0}\,\bm{)}$ instead of $i\in\bm{[}\,0\,\bm{.\,.}\,n_{0}-m_{0}\,\bm{]}$ , $\mathcal{Y}$ is optimal, and that $C_{S}\neq\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ . We observe that all conditions are relatively harmless. Since we are only concerned with capturing all optimal alignments, the first two conditions are perfectly acceptable. Moreover, whenever $C_{S}=\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , we have $P=P^{\#}$ and $T=T^{\#}$ , where $P^{\#}$ and $T^{\#}$ are defined as in Theorem 3.8. At this point, we know that $P$ and $T$ already have a sufficiently cheap encoding to be sent directly.

3.2.1 Redefining $𝑺$

Let us start making our improvement formal. To this end, we relax the definition of $S$ : we let $S$ be a set of alignments of fragments of $P$ onto fragments of $T$ with cost at most $k$ , and we denote by $\operatorname{cost}(S)\coloneqq\sum_{\mathcal{X}\in S}\operatorname{cost}(% \mathcal{X})$ the sum of all costs of the alignments contained in $S$ .

Based on such $S$ , we can define the inference graph $\mathbf{G}_{S}$ as before and argue that all characters in red components follow from the edit information for all $\mathcal{X}\in S$ . We conclude again that $\operatorname{bc}(\mathbf{G}_{S})=0$ is easy, and we assume that $\operatorname{bc}(\mathbf{G}_{S})>0$ in this (sub)section. We also define $P_{|S}$ and $T_{|S}$ as before. Lemma 3.4 can be extended quite easily to fragments of $P$ ; see the full version.

Lemma 3.11.

Let $\mathcal{X}:P\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\hbox{\lower 3.407pt\hbox{{\includegraphics{}{}{dagpub-% tikzpictures/p026-Kociumaka.latexml-figure15.pdf}}}}T\bm{[}\,y\,\bm{.\,.}\,y^{% \prime}\,\bm{)}\in S$ and define $y_{\mathcal{X}},y_{\mathcal{X}}^{\prime}\in\bm{[}\,0\,\bm{.\,.}\,n_{S}\,\bm{]}$ as the number of characters of $T_{|S}$ contained in $T\bm{[}\,0\,\bm{.\,.}\,y\,\bm{)}$ and $T\bm{[}\,0\,\bm{.\,.}\,y^{\prime}\,\bm{)}$ . Similarly, define $x_{\mathcal{X}},x_{\mathcal{X}}^{\prime}\in\bm{[}\,0\,\bm{.\,.}\,m_{S}\,\bm{]}$ as the number of characters of $P_{|S}$ contained in $P\bm{[}\,0\,\bm{.\,.}\,x\,\bm{)}$ and $P\bm{[}\,0\,\bm{.\,.}\,x^{\prime}\,\bm{)}$ .

Then, $P_{|S}\bm{[}\,x_{\mathcal{X}}\,\bm{.\,.}\,x^{\prime}_{\mathcal{X}}\,\bm{)}=T_{% |S}\bm{[}\,y_{\mathcal{X}}\,\bm{.\,.}\,y^{\prime}_{\mathcal{X}}\,\bm{)}$ , and $\mathcal{X}$ induces edges between $P_{|S}\bm{[}\,x_{\mathcal{X}}+p\,\bm{]}$ and $T_{|S}\bm{[}\,y_{\mathcal{X}}+p\,\bm{]}$ for $p\in\bm{[}\,0\,\bm{.\,.}\,x_{\mathcal{X}}^{\prime}-x_{\mathcal{X}}\,\bm{)}$ , and no other edges incident to characters of $P_{|S}$ or $T_{|S}$ .

We next give the new condition on $S$ needed to observe the periodic structure.

Definition 3.12.

We say $S$ encloses $T$ if $|T|\leq 2\cdot|P|-2k$ and $S$ can be written as

S=\{\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}},\mathcal{A}_{1},% \ldots,\mathcal{A}_{a},\mathcal{B}_{1},\ldots,\mathcal{B}_{b}\}

such that the following conditions hold:

(a)

$\mathcal{X}_{\mathsf{pref}}$ aligns the whole $P$ with a prefix of $T$ ;
(b)

$\mathcal{X}_{\mathsf{suf}}$ aligns the whole $P$ with a suffix of $T$ ;
(c)

$\mathcal{A}_{1},\ldots,\mathcal{A}_{a}$ align the whole $P$ with fragments of $T$ .

We say $S$ is degenerate if $y_{\mathcal{X}_{\mathsf{pref}}}=y_{\mathcal{X}_{\mathsf{suf}}}=y_{\mathcal{A}_% {1}}=\ldots=y_{\mathcal{A}_{a}}=0$ . Moreover, we define

g_{0}\coloneqq\left\{\begin{array}[]{@{\;}c@{\quad}l@{}}m_{S}&\text{if $S$ is % degenerate,}\\ \gcd\{y_{\mathcal{X}_{\mathsf{pref}}},y_{\mathcal{X}_{\mathsf{suf}}},y_{% \mathcal{A}_{1}},\ldots,y_{\mathcal{A}_{a}}\}&\text{otherwise}.\end{array}\right.

For each $i\in\bm{[}\,1\,\bm{.\,.}\,b\,\bm{]}$ , we define $g_{i}\coloneqq\gcd(g_{i-1},y_{\mathcal{B}_{i}}-x_{\mathcal{B}_{i}}).$ We further say that $S$ succinctly encloses $T$ if the following condition holds for every $i\in\bm{[}\,1\,\bm{.\,.}\,b\,\bm{]}$ .

(d)

The alignment $\mathcal{B}_{i}:P\bm{[}\,x_{i}\,\bm{.\,.}\,x_{i}^{\prime}\,\bm{)}\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{\includegraphics{}{}{% dagpub-tikzpictures/p026-Kociumaka.latexml-figure16.pdf}}}}T\bm{[}\,y_{i}\,\bm% {.\,.}\,y_{i}^{\prime}\,\bm{)}$ satisfies $x_{\mathcal{B}_{i}}^{\prime}-x_{\mathcal{B}_{i}}\geq g_{i-1}+1$ .

If $S$ encloses $T$ , then each of the alignments $\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}},\mathcal{A}_{1},\dots,% \mathcal{A}_{a}$ aligns the entire string $P$ with a fragment of $T$ , and the edges they induce connect to all vertices of $P_{|S}$ . Consequently, we have $x_{\mathcal{X}_{\mathsf{pref}}}=x_{\mathcal{X}_{\mathsf{suf}}}=x_{\mathcal{A}_% {1}}=\dots=x_{\mathcal{A}_{a}}=0$ and $x_{\mathcal{X}_{\mathsf{pref}}}^{\prime}=x_{\mathcal{X}_{\mathsf{suf}}}^{% \prime}=x_{\mathcal{A}_{1}}^{\prime}=\dots=x_{\mathcal{A}_{a}}^{\prime}=m_{S}$ . Moreover, note that whenever $S$ succinctly encloses $T$ and $S$ is degenerate, then $b=0$ , since the condition (d) cannot hold for $i=1$ if $b>0$ .

We can also prove something more about the exact matching induced by $\mathcal{X}_{\mathsf{pref}}$ and $\mathcal{X}_{\mathsf{suf}}$ .

Lemma 3.13.

If $S$ encloses $T$ , then $y_{\mathcal{X}_{\mathsf{pref}}}=0$ , $y_{\mathcal{X}_{\mathsf{suf}}}=n_{S}-m_{S}$ , and $n_{S}\leq 2m_{S}$ .

The proof, provided for completeness in the full version, is the same as [13, Claim 4.6]. This is because the argument relies exclusively on the alignments $\mathcal{X}_{\mathsf{pref}}$ and $\mathcal{X}_{\mathsf{suf}}$ (and not any $\mathcal{B}_{i}$ ).

Lemma 3.13 also implies that, when $S$ is degenerate, then $m_{S}=n_{S}$ and every alignment $\mathcal{X}\in\{\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}},% \mathcal{A}_{1},\ldots,\mathcal{A}_{a}\}$ induces in $\mathbf{G}_{S}$ an edge $\{P_{|S}[p],T_{|S}[t]\}$ iff $p=t$ . In this case, for each $p\in\bm{[}\,0\,\bm{.\,.}\,m_{S}\,\bm{)}$ , there is a black component consisting solely of $P_{|S}[p]$ and $T_{|S}[p]$ .

The following generalization of the inference graph $\mathbf{G}_{S}$ lets us work with graphs of more predictable structure.

Definition 3.14.

Suppose $S$ encloses $T$ . We define the sets $S^{0}\coloneqq\{\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}},% \mathcal{A}_{1},\ldots,\mathcal{A}_{a}\}$ and $S^{i}\coloneqq\{\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}},% \mathcal{A}_{1},\ldots,\mathcal{A}_{a},\mathcal{B}_{1},\ldots,\mathcal{B}_{i}\}$ for $i\in\bm{[}\,1\,\bm{.\,.}\,b\,\bm{]}$ .

Moreover, for $i\in\bm{[}\,0\,\bm{.\,.}\,b\,\bm{]}$ , we define the graph $\mathbf{G}^{i}_{S}$ obtained from $\mathbf{G}_{S}$ as follows. We remove vertices (along with their incident edges) that are not in black components in $\mathbf{G}_{S}$ (so only vertices in $P_{|S}$ and $T_{|S}$ remain), and we additionally remove any edge that is not induced by alignments in the set $S^{i}$ .

We now proceed to argue this definition successfully preserves the periodic structure.

Lemma 3.15.

Suppose $S$ encloses $T$ . Then, the following hold for each $i\in\bm{[}\,0\,\bm{.\,.}\,b\,\bm{)}$ .

1.

If condition (d) in Definition 3.12 holds for all indices in $\bm{[}\,1\,\bm{.\,.}\,i\,\bm{]}$ , then, for each $c\in\bm{[}\,0\,\bm{.\,.}\,g_{i}\,\bm{)}$ , the graph $\mathbf{G}^{i}_{S}$ has a connected component with node set $C^{i}_{c}\coloneqq\{P_{|S}[j]:j\equiv_{g_{i}}c\}\cup\{T_{|S}[j]:j\equiv_{g_{i}% }c\}$ , where $j$ ranges over $\bm{[}\,0\,\bm{.\,.}\,m_{S}\,\bm{)}$ and $\bm{[}\,0\,\bm{.\,.}\,n_{S}\,\bm{)}$ , respectively.

In particular, in $\mathbf{G}_{S}=\mathbf{G}^{b}_{S}$ , for every $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , there exists a black connected component with node set $\{P_{|S}[i]:i\equiv_{\operatorname{bc}(\mathbf{G}_{S})}c\}\cup\{T_{|S}[i]:i% \equiv_{\operatorname{bc}(\mathbf{G}_{S})}c\}$ .
2.

The last characters of $P_{|S}$ and $T_{|S}$ are in the same component of $\mathbf{G}^{i}_{S}$ .

Proof.

We first prove (1). If $S$ is degenerate (and hence $b=0$ ), we have already argued that $\mathbf{G}_{S}=\mathbf{G}_{S^{0}}=\mathbf{G}_{S}^{0}$ has the claimed structure. Therefore, we assume that $S$ is not degenerate.

Let us assign a unique label $\$_{C}$ to each component $C$ of $\mathbf{G}_{S}^{i}$ and define strings $P_{\operatorname{cc}}$ and $T_{\operatorname{cc}}$ of length $m_{S}$ and $n_{S}$ , respectively, as follows. For $i\in\bm{[}\,0\,\bm{.\,.}\,m_{S}\,\bm{)}$ , set $P_{\operatorname{cc}}[i]=\$_{C}$ , where $C$ is the component of $\mathbf{G}_{S}^{i}$ containing $P_{|S}[i]$ . Similarly, for $i\in\bm{[}\,0\,\bm{.\,.}\,n_{S}\,\bm{)}$ , set $T_{\operatorname{cc}}[i]=\$_{C}$ , where $C$ is the black connected component of $\mathbf{G}_{S}^{i}$ containing $T_{|S}[i]$ .

By Lemmas 3.11 and 3.13, $\{0,|T_{\operatorname{cc}}|-|P_{\operatorname{cc}}|\}\subseteq\{y_{\mathcal{X}% _{\mathsf{pref}}},y_{\mathcal{X}_{\mathsf{suf}}},y_{\mathcal{A}_{1}},\ldots,y_% {\mathcal{A}_{a}}\}\subseteq\mathrm{Occ}(P_{\operatorname{cc}},T_{% \operatorname{cc}})$ . Since $|T_{\operatorname{cc}}|\leq 2|P_{\operatorname{cc}}|$ , we can use the following claim already proved in [13].

Claim 3.16 ([13, Lemma 3.2]).

Consider a non-empty pattern $P^{\prime}$ and a text $T^{\prime}$ with $|T^{\prime}|\leq 2|P^{\prime}|+1$ . If $\{0,|T^{\prime}|-|P^{\prime}|\}\subseteq\mathrm{Occ}(P^{\prime},T^{\prime})$ , that is, $P^{\prime}$ occurs both as a prefix and as a suffix of $T^{\prime}$ , then $\gcd(\mathrm{Occ}(P^{\prime},T^{\prime}))$ is a period of $T^{\prime}$ .

It follows that $\gcd(\mathrm{Occ}(P_{\operatorname{cc}},T_{\operatorname{cc}}))$ is a period of $T_{\operatorname{cc}}$ . Hence, $\gcd\{y_{\mathcal{X}_{\mathsf{pref}}},y_{\mathcal{X}_{\mathsf{suf}}},y_{% \mathcal{A}_{1}},\ldots,y_{\mathcal{A}_{a}}\}$ is a period of both $T_{\operatorname{cc}}$ and its prefix $P_{\operatorname{cc}}$ , and thus $g_{0}$ is a period of both $T_{\operatorname{cc}}$ and $P_{\operatorname{cc}}$ .

We now prove by induction that $T_{\operatorname{cc}}$ and $P_{\operatorname{cc}}$ have period $g_{i}$ for all $i\in\bm{[}\,0\,\bm{.\,.}\,b\,\bm{]}$ . The base case $i=0$ follows from the argument above. For $i>0$ , assuming $T_{\operatorname{cc}}$ and $P_{\operatorname{cc}}$ have period $g_{i-1}$ , we observe that the condition on $\mathcal{B}_{i}$ ensures $x_{\mathcal{B}_{i}}^{\prime}-x_{\mathcal{B}_{i}}\geq g_{i-1}+1\geq g_{i-1}$ . The following new claim allows us to conclude that $T_{\operatorname{cc}}$ and $P_{\operatorname{cc}}$ have period $g_{i}=\gcd(g_{i-1},y_{\mathcal{B}_{i}}-x_{\mathcal{B}_{i}})$ .

Claim 3.17.

Consider strings $P^{\prime}$ and $T^{\prime}$ with a common string period $Q$ . If there are matching fragments $P^{\prime}\bm{[}\,x\,\bm{.\,.}\,x^{\prime}\,\bm{)}=T^{\prime}\bm{[}\,y\,\bm{.% \,.}\,y^{\prime}\,\bm{)}$ of length $x^{\prime}-x\geq|Q|$ , then $P^{\prime}$ and $T^{\prime}$ also have a common period $\gcd(|Q|,y-x)$ .

Proof.

The claim is trivial if $y=x$ , so we henceforth assume otherwise. By symmetry between the fragments, we can also assume without loss of generality that $y>x$ . Since $P^{\prime}$ and $T^{\prime}$ are prefixes of $Q^{\infty}$ , we have $Q^{\infty}\bm{[}\,x\,\bm{.\,.}\,x+|Q|\,\bm{)}=Q^{\infty}\bm{[}\,y\,\bm{.\,.}\,% y+|Q|\,\bm{)}$ . Observe that $y-x$ is a period of $Q^{\infty}$ : for each $i\in\mathbb{Z}_{\geq 0}$ , we indeed have $Q^{\infty}\bm{[}\,i\,\bm{]}=Q^{\infty}\bm{[}\,x+(i-x)\bmod|Q|\,\bm{]}=Q^{% \infty}\bm{[}\,y+(i-x)\bmod|Q|\,\bm{]}=Q^{\infty}\bm{[}\,i+y-x\,\bm{]}$ . From the Periodicity Lemma (Lemma 2.1) applied for $Q^{\infty}\bm{[}\,0\,\bm{.\,.}\,|Q|+y-x\,\bm{)}$ , we conclude that $\gcd(|Q|,y-x)$ is a period of $Q^{\infty}\bm{[}\,0\,\bm{.\,.}\,|Q|+y-x\,\bm{)}$ and hence of $Q$ . As a divisor of $|Q|$ , it is also a common period of $Q^{\infty}$ , $P^{\prime}$ , and $T^{\prime}$ . $\hfill\vartriangleleft$

Consequently, for each $c\in\bm{[}\,0\,\bm{.\,.}\,g_{i}\,\bm{)}$ , the set $C^{i}_{c}$ belongs to a single connected component of $\mathbf{G}_{S}^{i}$ . It remains to prove $g_{i}=\operatorname{bc}(\mathbf{G}_{S}^{i})$ . We do this by demonstrating that no edge of $\mathbf{G}_{S}^{i}$ leaves $C^{i}_{c}$ . Note that Lemma 3.11 further implies that every edge incident to $P_{|S}$ or $T_{|S}$ connects $P_{|S}\bm{[}\,p\,\bm{]}$ with $T_{|S}\bm{[}\,t\,\bm{]}$ such that $t=p+(y_{\mathcal{X}}-x_{\mathcal{X}})$ for some $\mathcal{X}\in S$ and $p\in\bm{[}\,x_{\mathcal{X}}\,\bm{.\,.}\,x_{\mathcal{X}}^{\prime}\,\bm{)}$ . In particular, $t\equiv_{g_{i}}p$ , so $P_{|S}\bm{[}\,p\,\bm{]}\in C^{i}_{c}$ holds if and only if $T_{|S}\bm{[}\,t\,\bm{]}\in C^{i}_{c}$ .

As for (2), since $P_{\operatorname{cc}}$ is a suffix of $T_{\operatorname{cc}}$ , the last characters of $P_{|S}$ and $T_{|S}$ are connected. $\hfill\blacktriangleleft$

3.2.2 New Iterative Construction of $𝑺$

For the new construction of $S$ , we use the following key lemma.

Lemma 3.18.

Suppose $S$ encloses $T$ and condition (d) of Definition 3.12 holds up to $i$ (inclusive) for some $i\in\bm{[}\,0\,\bm{.\,.}\,b-1\,\bm{)}$ (if $i=0$ , then this statement is void). Further, suppose that there exists an integer $z$ such that all characters of $P_{|S^{i}}\bm{[}\,z\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{.\,.}\,(z+2% )\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{)}$ are in the pre-image of $\mathcal{B}_{i+1}$ . Then, either $\operatorname{bc}(\mathbf{G}_{S})=0$ or condition (d) also holds for $i+1$ .

Proof.

By Lemma 3.15(1), in the inference graph $\mathbf{G}_{S^{i}}$ , for each $c\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{)}$ , there is a black component with node set $\{P_{|{S^{i}}}[j]:j\equiv_{\operatorname{bc}(\mathbf{G}_{S^{i}})}c\}\cup\{T_{|% S^{i}}[j]:j\equiv_{\operatorname{bc}(\mathbf{G}_{S^{i}})}c\}$ . Consider the graph $\mathbf{G}_{S}^{i}$ . This graph is identical to $\mathbf{G}_{S^{i}}$ except that the components that become red in $\mathbf{G}_{S}$ are removed. Let $R\subseteq\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{)}$ index these removed components.

If $R=\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{)}$ , then $\operatorname{bc}(\mathbf{G}_{S})=0$ , and the proof is complete. Otherwise, we proceed as follows. Choose an arbitrary $r\in\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{)}\setminus R$ , and consider the fragment

P_{|{S^{i}}}\bm{[}\,z\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})+r\,\bm{.\,.}\,% (z+1)\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})+r\,\bm{]}\subseteq P_{|S^{i}}% \bm{[}\,z\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{.\,.}\,(z+2)\cdot% \operatorname{bc}(\mathbf{G}_{S^{i}})\,\bm{)},

whose characters, by our assumption, are also contained in the pre-image of $\mathcal{B}_{i+1}$ . The characters $P_{|{S^{i}}}\bm{[}\,z\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})+r\,\bm{]}$ and $P_{|{S^{i}}}\bm{[}\,(z+1)\cdot\operatorname{bc}(\mathbf{G}_{S^{i}})+r\,\bm{]}$ belong to the same black component of $\mathbf{G}_{S^{i}}$ . Since $r\notin R$ , these characters survive in $\mathbf{G}_{S}^{i}$ and correspond to some characters $P_{|S}\bm{[}\,p\,\bm{]}$ and $P_{|S}\bm{[}\,p^{\prime}\,\bm{]}$ . Note that we must have $|p^{\prime}-p|\geq g_{i}$ as, by Lemma 3.15(1), characters in the same component of $\mathbf{G}_{S}^{i}$ lie at least $g_{i}$ positions apart. Thus, $|P_{|S}\bm{[}\,p\,\bm{.\,.}\,p^{\prime}\,\bm{]}|\geq g_{i}+1$ . Since $P_{|S}\bm{[}\,p\,\bm{.\,.}\,p^{\prime}\,\bm{]}$ is contained in $P_{|S}\bm{[}\,x_{\mathcal{B}_{i+1}}\,\bm{.\,.}\,x_{\mathcal{B}_{i+1}}^{\prime}% \,\bm{)}$ , we get $x_{\mathcal{B}_{i+1}}^{\prime}-x_{\mathcal{B}_{i+1}}\geq g_{i}+1$ . $\hfill\blacktriangleleft$

Algorithm 1 Construction of

S

that succinctly encloses

T

.

Finally, we can provide the new construction of $S$ . As in [13], we construct, from $S$ , a set $C_{S}$ of black components and a parameter $w$ based on a weight function covering $S$ . We use the following facts (proved in the full version):

1.

Lemma 3.10 still holds, and after replacing “enclosure” with “succinct enclosure” in Definition 3.7, Theorem 3.8 still holds.
2.

We can improve the bound for encoding $\{(c,T\bm{[}\,\tau_{0}^{c}\,\bm{]}):c\in C_{S}\}$ from $\mathcal{O}(w\log m)$ additional bits (on top of the edit information of $S$ ) to $\mathcal{O}\left((w+k)\log(1+m|\Sigma|/(w+k))\right)$ bits.
3.

All of this is possible with $w=\mathcal{O}(\operatorname{cost}(S))$ instead of $w=\mathcal{O}(k|S|)$ .

Lemma 3.19.

Suppose that $n\leq 2m-2k$ and that there are $k$ -error occurrences of $P$ appearing as both a prefix and a suffix of $T$ . Then, Algorithm 1 computes a set $S$ of size $|S|=\mathcal{O}(\min(\log m,|\lfloor\mathrm{Occ}^{E}_{k}(P,T)/k\rfloor|))$ and $\operatorname{cost}(S)=\mathcal{O}(k)$ such that the following hold:

1.

$S$ succinctly encloses $T$ ,
2.

$C_{S}=\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ or $S$ captures all $k$ -error occurrences of $P$ in $T$ ,
3.

the set $\{\mathsf{E}_{P,T}(\mathcal{X}):S\ni\mathcal{X}:P\bm{[}\,p\,\bm{.\,.}\,p^{% \prime}\,\bm{)}\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.33298pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure17.pdf}% }}}T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}\}$ together with all starting/ending points of the alignments in $S$ can be encoded in $\mathcal{O}(k\log(m|\Sigma|/k)+|S|\log m)$ bits.

Proof sketch (full proof in the full version).

In Algorithm 1, we maintain the invariant that $S$ succinctly encloses $T$ at the start of every iteration of the loops in Lines 2 and 7.

This invariant holds at the beginning as we set $S\coloneqq\{\mathcal{X}_{\mathsf{pref}},\mathcal{X}_{\mathsf{suf}}\}$ . We proceed by adding at most two alignments $\mathcal{A}_{\ell}$ to $S$ corresponding to uncaptured $k$ -error occurrences in the loop of Line 2. After the $\ell$ -th iteration, one of $\operatorname{bc}(\mathbf{G}_{S})=0$ , $C_{S}=\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , or $s_{P}\geq 2^{\ell}$ holds, where $s_{P}$ is the minimum number of characters of $P$ in a black component of $\mathbf{G}_{S}$ . Indeed, by Lemma 3.10, after adding $\mathcal{Y}$ to $S$ , each black component of $\mathbf{G}_{S}$ either becomes red or is merged with another component. Hence, unless $\operatorname{bc}(\mathbf{G}_{S\cup\{\mathcal{Y}\}})=0$ , every black component of $\mathbf{G}_{S\cup\{\mathcal{Y}\}}$ contains at least two black components of $\mathbf{G}_{S}$ , so $s_{P}$ at least doubles.

Adding the two alignments of the form $\mathcal{A}_{\ell}$ ensures that $m_{0}\geq s_{P}\geq 2^{2}=4$ when we enter the loop at Line 7 (so that $m_{0}\geq 3$ in Line 11, and the quantifier $j\in\bm{[}\,0\,\bm{.\,.}\,m_{0}-2\,\bm{)}$ is well-defined). There, we start adding alignments of the form $\mathcal{B}_{\ell}$ to $S$ . Each time we add such an alignment, we use Lemmas 3.18 and 3.10 to prove that $S$ still succinctly encloses $T$ . Using a similar argument as before, $\operatorname{bc}(\mathbf{G}_{S})=0$ , $C_{S}=\bm{[}\,0\,\bm{.\,.}\,\operatorname{bc}(\mathbf{G}_{S})\,\bm{)}$ , or $m_{0}\geq s_{P}\geq 2^{2+\ell}$ at the end of the $\ell$ -th iteration. Since $s_{P}\leq m$ , this ensures that the loop finishes after $\mathcal{O}(\log m)$ iterations and $|S|=\mathcal{O}(\log m)$ . When it does, all $k$ -error occurrences are captured.

Next, we argue why the bound on $\operatorname{cost}(S)$ holds. Since each of the alignments $\mathcal{Y}_{j}$ can overlap only with at most two others, we obtain that the sum of the costs of the alignments $\mathcal{Y}_{j}$ for all $j\in\bm{[}\,0\,\bm{.\,.}\,m_{0}-2\,\bm{)}$ is at most $2k$ . Consequently, in the $\ell$ -th iteration the cost of the alignment $\mathcal{Y}_{j}$ selected at Line 11 is at most $\operatorname{cost}(\mathcal{Y}_{j})\leq 2k/(m_{0}-2)\leq 2k/(2^{\ell+1}-2)% \leq k/2^{\ell-1}$ . Thus, $\operatorname{cost}(S)\leq 4k+k\cdot\sum_{\ell=1}^{\mathcal{O}(\log m)}\frac{1% }{2^{\ell-1}}\leq 6k=\mathcal{O}(k)$ .

Lastly, we give the bound on the encoding size. The endpoints of the alignments $\mathcal{X}\in S$ can be encoded in $\mathcal{O}(|S|\log m)$ bits. On top of that, by Lemma 3.2, the edit information $\{\mathsf{E}_{P,T}(\mathcal{X}):\mathcal{X}\in S\}$ can be encoded in space asymptotically bounded as follows, using $S^{+}\coloneqq\{\mathcal{X}\in S:\operatorname{cost}(\mathcal{X})>0\}$ and the monotonicity of $x\log(k/x)$ for $0<x\leq k/e$ :

\sum_{\mathcal{X}\in S^{+}}\operatorname{cost}(\mathcal{X})\cdot\log\left(% \tfrac{m|\Sigma|}{\operatorname{cost}(\mathcal{X})}\right)=\operatorname{cost}% (S)\cdot\log\left(\tfrac{m|\Sigma|}{k}\right)+\sum_{\mathcal{X}\in S^{+}}% \operatorname{cost}(\mathcal{X})\cdot\log\left(\tfrac{k}{\operatorname{cost}(% \mathcal{X})}\right)\\ \leq k\log\left(\tfrac{m|\Sigma|}{k}\right)+\mathcal{O}(k)+k\cdot\sum_{\ell=1}% ^{\mathcal{O}(\log m)}\tfrac{\ell-1}{2^{\ell-1}}\leq\mathcal{O}\left(k\log% \left(\tfrac{m|\Sigma|}{k}\right)\right)\text{ bits.}

To show $|S|=\mathcal{O}(|\lfloor\mathrm{Occ}^{E}_{k}(P,T)/k\rfloor|)$ , we argue in the full proof that the alignments $\mathcal{Y}$ in Line 10 start at least $k$ positions away from each other. $\hfill\blacktriangleleft$

Now, following the approach in [13], we can encode the set $\{\mathsf{E}_{P,T}(\mathcal{X}):\mathcal{X}\in S\}$ and the pairs $\{(c,T\bm{[}\,\tau_{0}^{c}\,\bm{]}):c\in C_{S}\}$ using $\mathcal{O}(k\log(m|\Sigma|/k)+|S|\log m)$ bits. Decoding would then proceed via an appropriately modified version of Theorem 3.8. Unfortunately, this falls short of proving Theorem 1.1 because the $|S|\log m$ term might dominate the encoding size; consequently, we must develop an alternative for cases where this term is prohibitively large.

Workaround.

Note that $|S|\log m=\mathcal{O}(|S|\log\frac{m}{\log m})\leq\mathcal{O}(\log m\cdot\log% \frac{m}{\log m})$ , so $|S|\log m=\mathcal{O}(k\log\frac{m}{k})$ holds as long as $k\geq\log m$ or $|S|=\mathcal{O}(k)$ . Thus, the critical scenario arises when $k<\log m$ and $|S|=\omega(k)$ . Not coincidentally, we also proved $|S|=\mathcal{O}(|\lfloor\mathrm{Occ}^{E}_{k}(P,T)/k\rfloor|)$ in Lemma 3.19, which lets us derive $|\lfloor\mathrm{Occ}^{E}_{k}(P,T)/k\rfloor|=\omega(k)$ in this case. This condition characterizes one of the two fundamental structural results for PMwE from [5]: in a setting (almost) identical to ours, there is a primitive string $Q$ with $|Q|\leq m/128k$ such that the edit distance between $P$ and a prefix of $Q^{\infty}$ does not exceed $2k$ . Moreover, [5, Theorem 5.2] upper-bounds the distance between $T$ and a prefix of $Q^{\infty}$ by $6k$ . The subsequent characterization in [5, Section 5] implies that, for every $k$ -error occurrence $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ of $P$ , there exists an exact occurrence of $Q$ in $P$ that is matched perfectly both in the alignment from $P$ to the prefix of $Q^{\infty}$ and in the alignment from $P$ via $T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}$ to a fragment of $Q^{\infty}$ .

Our workaround is to initialize $S$ so that the periodic structure of $\mathbf{G}_{S}$ essentially coincides with the structure induced by $Q$ . Namely, every black component corresponds to a position $r\in\bm{[}\,0\,\bm{.\,.}\,|Q|\,\bm{)}$ and consists of all characters of $P$ and $T$ that the alignments with prefixes of $Q^{\infty}$ match with characters of the form $Q^{\infty}\bm{[}\,r+j|Q|\,\bm{]}$ for $j\in\mathbb{Z}_{\geq 0}$ . By Lemma 3.10 and the above characterization of $k$ -error occurrences, this guarantees that all $k$ -error occurrences are captured by $S$ . To achieve such $\mathbf{G}_{S}$ , we include in $S$ alignments for the two approximate occurrences of $P$ as a prefix and a suffix of $T$ , and a third $14k$ -edit alignment that, for every $j$ , aligns the $j$ th copy of $Q$ in $P$ with the $(j+1)$ th copy of $Q$ in $T$ . This yields the following lemma proved in the full version.

Lemma 3.20.

Suppose that $n\leq 3/2\cdot m-28k$ , that there are $k$ -error occurrences of $P$ appearing as both a prefix and a suffix of $T$ , and that there is a primitive string $Q$ with $|Q|\leq m/128k$ and ${\delta_{E}}(P,Q^{*})\leq 2k$ . Then, we can construct a set $S$ of at most three $14k$ -edit alignments of $P$ onto fragments of $T$ such that, when the notions of succinctly enclosing and capturing are interpreted with threshold $14k$ , all of the following hold:

1.

$S$ succinctly encloses $T$ ,
2.

$S$ captures all $k$ -error occurrences of $P$ in $T$ ,
3.

the set $\{\mathsf{E}_{P,T}(\mathcal{X}):S\ni\mathcal{X}:P\bm{[}\,p\,\bm{.\,.}\,p^{% \prime}\,\bm{)}\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.33298pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure18.pdf}% }}}T\bm{[}\,t\,\bm{.\,.}\,t^{\prime}\,\bm{)}\}$ together with all starting/ending points of the alignments in $S$ can be encoded in $\mathcal{O}(k\log(m|\Sigma|/k))$ bits.

4 Lower Bound

Theorem 1.3. [Restated, see original statement.]

Fix integers $n, m, k$ with $n\geq m\geq k>0$ and an input alphabet $\Sigma$ with $\mathtt{0}\in\Sigma$ and $|\Sigma|\geq 2$ . Consider an encoding that, for each fragment $T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ with $\delta_{E}(P,T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)})\leq k$ , allows to reconstruct an edit sequence $P\immediate\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\hbox{\lower 3.407pt\hbox{{% \includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure0.pdf}}}% }T\bm{[}\,i\,\bm{.\,.}\,j\,\bm{)}$ and the corresponding edit information. Such an encoding must use $\Omega(n/m\cdot k\log(|\Sigma|m/k))$ bits for $P=\mathtt{0}^{m}$ and some $T\in\Sigma^{n}$ .

Proof.

Set $p\coloneqq\lfloor n/m\rfloor$ and $T\coloneqq S_{0}\cdot S_{1}\cdots S_{p-1}\cdot\mathtt{0}^{n-pm}$ , where $S_{0},\ldots,S_{p-1}\in\Sigma^{m}$ are strings that contain at most $k$ characters from $\Sigma\setminus\{\mathtt{0}\}$ and all remaining characters are equal to $\mathtt{0}$ . Clearly, $\delta_{E}(P,T\bm{[}\,qm\,\bm{.\,.}\,(q+1)m\,\bm{)})\leq k$ for every $q\in\bm{[}\,0\,\bm{.\,.}\,p\,\bm{)}$ . Moreover, for every $q\in\bm{[}\,0\,\bm{.\,.}\,p\,\bm{)}$ , there is a unique optimal alignment $\mathcal{A}_{q}:P\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 3.33298pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p026-Kociumaka.latexml-figure19.pdf}% }}}T\bm{[}\,qm\,\bm{.\,.}\,(q+1)m\,\bm{)}$ that performs substitutions exactly in the positions where the non-zero characters appear (it is not difficult to verify that any deletions or insertions would increase the cost). Thus, $\mathcal{A}_{q}$ allows us to fully recover $S_{q}$ from the edit information $\mathsf{E}_{P,T}(\mathcal{A}_{q})$ , and consequently $T$ can be fully recovered.

Finally, the number of possibilities for each block $S_{q}$ is $\sum_{i=0}^{k}\binom{m}{i}(|\Sigma|-1)^{i}$ . If $k\leq m/2$ , then this quantity is at least $\binom{m}{k}(|\Sigma|-1)^{k}$ , and the standard estimate $\binom{m}{k}=2^{\Omega(k\log(m/k))}$ yields $\binom{m}{k}=2^{\Omega(k\log(|\Sigma|m/k))}$ for $|\Sigma|=2$ and $\binom{m}{k}(|\Sigma|-1)^{k}\geq\binom{m}{k}(|\Sigma|/2)^{k}=2^{\Omega(k\log(|% \Sigma|m/k))}$ for $|\Sigma|>2$ . Otherwise, the sum contains the term $\binom{m}{\lceil m/2\rceil}(|\Sigma|-1)^{\lceil m/2\rceil}$ . If $|\Sigma|=2$ , then this term is simply $\binom{m}{\lceil m/2\rceil}\geq 2^{m}/m\geq 2^{\Omega(m)}\geq 2^{\Omega(m\log|% \Sigma|)}$ . If $|\Sigma|>2$ , then the term is at least $(\Sigma-1)^{\lceil m/2\rceil}\geq(|\Sigma|/2)^{m/2}=2^{\Omega(m\log|\Sigma|)}$ . In either case, we have $2^{\Omega(m\log|\Sigma|)}\geq 2^{\Omega(k\log(|\Sigma|m/k))}$ when $m/2<k\leq m$ . Therefore, the number of possibilities for $T$ is $2^{\Omega(n/m\cdot k\log(|\Sigma|m/k))}$ . $\hfill\blacktriangleleft$

References

[1] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM Journal on Computing, 2018. doi:10.1137/15M1053128.
[2] Sudatta Bhattacharya and Michal Koucký. Streaming $k$ -edit approximate pattern matching via string decomposition. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, 2023. doi:10.4230/LIPIcs.ICALP.2023.22.
[3] Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing, 2015. doi:10.1137/130936889.
[4] Alejandro Cassis, Tomasz Kociumaka, and Philip Wellnitz. Optimal algorithms for bounded weighted edit distance. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, 2023. doi:10.1109/FOCS57990.2023.00135.
[5] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster approximate pattern matching: A unified approach. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 2020. doi:10.1109/FOCS46700.2020.00095.
[6] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster pattern matching under edit distance: A reduction to dynamic puzzle matching and the seaweed monoid of permutation matrices. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, 2022. doi:10.1109/FOCS54457.2022.00072.
[7] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Pattern matching under weighted edit distance, 2025. Accepted at FOCS 2025. doi:10.48550/arXiv.2510.17752.
[8] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming $k$ -mismatch problem. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 2019. doi:10.1137/1.9781611975482.68.
[9] Richard Cole and Ramesh Hariharan. Approximate string matching: A simpler faster algorithm. SIAM Journal on Computing, 2002. doi:10.1137/S0097539700370527.
[10] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 1965. doi:10.1090/S0002-9939-1965-0174934-9.
[11] Paweł Gawrychowski and Damian Straszak. Beating $\mathcal{O}(nm)$ in approximate LZW-compressed pattern matching. In 24th International Symposium on Algorithms and Computation, ISAAC 2013, LNCS, 2013. doi:10.1007/978-3-642-45030-3_8.
[12] Daniel Gibney, Ce Jin, Tomasz Kociumaka, and Sharma V. Thankachan. Near-optimal quantum algorithms for bounded edit distance and Lempel-Ziv factorization. In 35th ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, 2024. doi:10.1137/1.9781611977912.11.
[13] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. On the communication complexity of approximate pattern matching. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, 2024. doi:10.1145/3618260.3649604.
[14] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. On the communication complexity of approximate pattern matching, 2024. doi:10.48550/arXiv.2403.18812.
[15] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. Near-optimal-time quantum algorithms for approximate pattern matching. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 517–534. SIAM, 2025. doi:10.1137/1.9781611978322.15.
[16] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. The communication complexity of pattern matching with edits revisited, 2026. arXiv:2604.15601.
[17] Tomasz Kociumaka, Ely Porat, and Tatiana Starikovskaya. Small-space and streaming pattern matching with $k$ edits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, 2021. doi:10.1109/FOCS52979.2021.00090.
[18] Michal Koucký and Michael Saks. Almost linear size edit distance sketch. In 56th Annual ACM Symposium on the Theory of Computing; STOC 2024, 2024.
[19] Gad M. Landau and Uzi Vishkin. Fast string matching with $k$ differences. Journal of Computer and System Sciences, 1988. doi:10.1016/0022-0000(88)90045-1.
[20] Gad M. Landau and Uzi Vishkin. Fast parallel and serial approximate string matching. Journal of Algorithms, 1989. doi:10.1016/0196-6774(89)90010-2.
[21] Vladimir Iosifovich Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Doklady Akademii Nauk SSSR, 1965.
[22] Peter H. Sellers. The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms, 1980. doi:10.1016/0196-6774(80)90016-4.
[23] Tatiana Starikovskaya. Communication and streaming complexity of approximate pattern matching. In 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, 2017. doi:10.4230/LIPIcs.CPM.2017.13.
[24] Alexander Tiskin. Threshold approximate matching in grammar-compressed strings. In Prague Stringology Conference, PSC 2014, 2014. URL: http://www.stringology.org/event/2014/p12.html.
[25] Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977. doi:10.1109/TIT.1977.1055714.

[bib.bib1] [1] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM Journal on Computing, 2018. doi:10.1137/15M1053128.

[bib.bib2] [2] Sudatta Bhattacharya and Michal Koucký. Streaming $k$ -edit approximate pattern matching via string decomposition. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, 2023. doi:10.4230/LIPIcs.ICALP.2023.22.

[bib.bib3] [3] Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing, 2015. doi:10.1137/130936889.

[bib.bib4] [4] Alejandro Cassis, Tomasz Kociumaka, and Philip Wellnitz. Optimal algorithms for bounded weighted edit distance. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, 2023. doi:10.1109/FOCS57990.2023.00135.

[bib.bib5] [5] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster approximate pattern matching: A unified approach. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 2020. doi:10.1109/FOCS46700.2020.00095.

[bib.bib6] [6] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster pattern matching under edit distance: A reduction to dynamic puzzle matching and the seaweed monoid of permutation matrices. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, 2022. doi:10.1109/FOCS54457.2022.00072.

[bib.bib7] [7] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Pattern matching under weighted edit distance, 2025. Accepted at FOCS 2025. doi:10.48550/arXiv.2510.17752.

[bib.bib8] [8] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming $k$ -mismatch problem. In 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 2019. doi:10.1137/1.9781611975482.68.

[bib.bib9] [9] Richard Cole and Ramesh Hariharan. Approximate string matching: A simpler faster algorithm. SIAM Journal on Computing, 2002. doi:10.1137/S0097539700370527.

[bib.bib10] [10] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 1965. doi:10.1090/S0002-9939-1965-0174934-9.

[bib.bib11] [11] Paweł Gawrychowski and Damian Straszak. Beating $\mathcal{O}(nm)$ in approximate LZW-compressed pattern matching. In 24th International Symposium on Algorithms and Computation, ISAAC 2013, LNCS, 2013. doi:10.1007/978-3-642-45030-3_8.

[bib.bib12] [12] Daniel Gibney, Ce Jin, Tomasz Kociumaka, and Sharma V. Thankachan. Near-optimal quantum algorithms for bounded edit distance and Lempel-Ziv factorization. In 35th ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, 2024. doi:10.1137/1.9781611977912.11.

[bib.bib13] [13] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. On the communication complexity of approximate pattern matching. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, 2024. doi:10.1145/3618260.3649604.

[bib.bib14] [14] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. On the communication complexity of approximate pattern matching, 2024. doi:10.48550/arXiv.2403.18812.

[bib.bib15] [15] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. Near-optimal-time quantum algorithms for approximate pattern matching. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 517–534. SIAM, 2025. doi:10.1137/1.9781611978322.15.

[bib.bib16] [16] Tomasz Kociumaka, Jakob Nogler, and Philip Wellnitz. The communication complexity of pattern matching with edits revisited, 2026. arXiv:2604.15601.

[bib.bib17] [17] Tomasz Kociumaka, Ely Porat, and Tatiana Starikovskaya. Small-space and streaming pattern matching with $k$ edits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, 2021. doi:10.1109/FOCS52979.2021.00090.

[bib.bib18] [18] Michal Koucký and Michael Saks. Almost linear size edit distance sketch. In 56th Annual ACM Symposium on the Theory of Computing; STOC 2024, 2024.

[bib.bib19] [19] Gad M. Landau and Uzi Vishkin. Fast string matching with $k$ differences. Journal of Computer and System Sciences, 1988. doi:10.1016/0022-0000(88)90045-1.

[bib.bib20] [20] Gad M. Landau and Uzi Vishkin. Fast parallel and serial approximate string matching. Journal of Algorithms, 1989. doi:10.1016/0196-6774(89)90010-2.

[bib.bib21] [21] Vladimir Iosifovich Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Doklady Akademii Nauk SSSR, 1965.

[bib.bib22] [22] Peter H. Sellers. The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms, 1980. doi:10.1016/0196-6774(80)90016-4.

[bib.bib23] [23] Tatiana Starikovskaya. Communication and streaming complexity of approximate pattern matching. In 28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, 2017. doi:10.4230/LIPIcs.CPM.2017.13.

[bib.bib24] [24] Alexander Tiskin. Threshold approximate matching in grammar-compressed strings. In Prague Stringology Conference, PSC 2014, 2014. URL: http://www.stringology.org/event/2014/p12.html.

[bib.bib25] [25] Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977. doi:10.1109/TIT.1977.1055714.

The Communication Complexity of Pattern Matching with Edits Revisited

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our Results.

Theorem 1.1.

▶ Remark 1.2.

Theorem 1.3.

Our Techniques.

2 Preliminaries

Sets.

Strings.

Periodicity Lemma.

Lemma 2.1 (Periodicity Lemma [10]).

Edit Distance and Alignments.

Definition 2.2 ([6, Definition 2.1]).

Observation 2.3 ([6, Fact 2.2]).

Definition 2.4 (Edit information of an alignment).

Pattern Matching with Edits.

3 Upper Bound: Proof Overview

3.1 Previous Encoding

3.1.1 The Graph 𝐆𝑺 and the Induced Periodic Structure

Definition 3.1 ([13, Definition 4.1]).

Lemma 3.2.

Proof.

Definition 3.3 ([13, Definition 4.3]).

Lemma 3.4 ([13, Claim 4.5]).

Definition 3.5 ([13, Definition 4.2]).

Lemma 3.6 ([13, Lemma 4.4]).

3.1.2 Constructing 𝑺 and the Encoding

Definition 3.7 ([13, Definition 4.28]).

Theorem 3.8 ([13, Corollary 4.30]).

Lemma 3.9 ([13, Lemma 4.27]).

3.2 Improved Encoding

Lemma 3.10.

3.2.1 Redefining 𝑺

Lemma 3.11.

Definition 3.12.

Lemma 3.13.

Definition 3.14.

Lemma 3.15.

Proof.

Claim 3.16 ([13, Lemma 3.2]).

Claim 3.17.

Proof.

3.2.2 New Iterative Construction of 𝑺

Lemma 3.18.

Proof.

Lemma 3.19.

Proof sketch (full proof in the full version).

Workaround.

Lemma 3.20.

4 Lower Bound

Theorem 1.3. [Restated, see original statement.]

Proof.

References

$\blacktriangleright$ Remark 1.2.

3.1.1 The Graph $\mathbf{G}_{S}$ and the Induced Periodic Structure

3.1.2 Constructing $𝑺$ and the Encoding

3.2.1 Redefining $𝑺$

3.2.2 New Iterative Construction of $𝑺$