DIENS, École normale supérieure de Paris, PSL Research University, France and
LaBRI, Université de Bordeaux,
<EMAIL_ADDRESS>Max Planck Institute for
Informatics, Saarland Informatics Campus, Germany DIENS, École normale
supérieure de Paris, PSL Research University,
<EMAIL_ADDRESS>Gabriel Bathie, Tomasz
Kociumaka, and Tatiana Starikovskaya [500]Theory of computation Streaming,
sublinear, and near linear time algorithms [500]Theory of computation Pattern
matching Partially funded by the grant ANR-20-CE48-0001 from the French
National Research Agency.

# Small-Space Algorithms for the Online Language Distance Problem for
Palindromes and Squares

Gabriel Bathie  Tomasz Kociumaka  Tatiana Starikovskaya

###### Abstract

We study the online variant of the language distance problem for two classical
formal languages, the language of palindromes and the language of squares, and
for the two most fundamental distances, the Hamming distance and the edit
(Levenshtein) distance. In this problem, defined for a fixed formal language
$L$, we are given a string $T$ of length $n$, and the task is to compute the
minimal distance to $L$ from _every_ prefix of $T$. We focus on the low-
distance regime, where one must compute only the distances smaller than a
given threshold $k$. In this work, our contribution is twofold:

  1. 1.

First, we show _streaming_ algorithms, which access the input string $T$ only
through a single left-to-right scan. Both for palindromes and squares, our
algorithms use $O(k\operatorname*{polylog}n)$ space and time per character in
the Hamming-distance case and $O(k^{2}\operatorname*{polylog}n)$ space and
time per character in the edit-distance case. These algorithms are randomised
by necessity, and they err with probability inverse-polynomial in $n$.

  2. 2.

Second, we show _deterministic read-only_ online algorithms, which are also
provided with read-only random access to the already processed characters of
$T$. Both for palindromes and squares, our algorithms use
$O(k\operatorname*{polylog}n)$ space and time per character in the Hamming-
distance case and $O(k^{4}\operatorname*{polylog}n)$ space and amortised time
per character in the edit-distance case.

###### keywords:

Approximate pattern matching, streaming algorithms, palindromes, squares

##  1 Introduction

The _language distance_ problem is one of the most fundamental problems in
formal language theory. In this problem, the task is to compute the minimal
distance between a given string $S$ and any string belonging to a formal
language $L$. Introduced in the early 1970s by Aho and Peterson [2], the
language distance problem has been studied extensively for regular languages
under Hamming and edit distances [5], for general context-free languages,
mainly focusing on the edit distance [1, 2, 9, 11, 28, 30, 33, 36, 37, 38],
and the Dyck language (the language of well-nested parentheses sequences) in
particular [1, 4, 9, 11, 13, 14, 16, 24, 25, 35, 36, 37].

##### Our results.

In this work, we study the complexity of the online and low-distance version
of the language distance problem, where we are given a string $T$ of length
$n$, and the task is to compute the minimal distance from _every_ prefix of
$T$ to a formal language $L$ (the distance and the language are specified in
the problem definition). We focus on the low-distance regime, i.e., we assume
to be given a threshold parameter $k$ such that distances larger than $k$ do
not need to be computed. We consider the edit distance (defined as the minimum
number of character insertions, deletions, and substitutions needed to
transform one string into the other) and, as a preliminary step, the Hamming
distance (allowing for substitutions only). We study the problem for two
classical languages: the language PAL of all palindromes, where a palindrome
is a string that is equal to its reversed copy, and the language SQ of all
squares, where a square is the concatenation of two copies of a string. These
two languages are very similar yet very different in nature: PAL is not
regular but is context-free, whereas SQ is not even context-free. Formally,
the problems we consider are defined as follows:

######  Problem .

$k$-LHD-PAL (resp. $k$-LHD-SQ)
Input: A string $T$ of length $n$ and a positive integer $k$.
Output: For each $1\leq i\leq n$, report $\min\\{k+1,hd_{i}\\}$, where
$hd_{i}$ is the minimum Hamming distance between $T[1.\,.i]$ and a string in
PAL (resp. in SQ).

######  Problem .

$k$-LED-PAL (resp. $k$-LED-SQ)
Input: A string $T$ of length $n$ and a positive integer $k$.
Output: For each $1\leq i\leq n$, report $\min\\{k+1,ed_{i}\\}$, where
$ed_{i}$ is the minimum edit distance between $T[1.\,.i]$ and a string in PAL
(resp. in SQ).

Problem | Model | Time per character | Space complexity | Reference
---|---|---|---|---
$k$-LHD-PAL | Streaming | $O(k\log^{3}n)$ | $O(k\log n)$ | Thm 3.1
$k$-LHD-SQ | Streaming | $\tilde{O}(k)$ | $O(k\log^{2}n)$ | Thm 3.2
$k$-LHD-PAL/SQ | Read-only | $O(k\log n)$ | $O(k\log n)$ | Thms 4.5 and 4.7
$k$-LED-PAL/SQ | Streaming | $\tilde{O}(k^{2})$ | $\tilde{O}(k^{2})$ | Thms 5.1 and 5.2
$k$-LED-PAL/SQ | Read-only |  $\tilde{O}(k^{4})$ (amortised) | $\tilde{O}(k^{4})$ | Thms 5.3 and 5.4
Table 1: Summary of the complexities of the algorithms introduced in this
work.

Amir and Porat [3] showed that there is a randomised streaming algorithm that
solves the $k$-LHD-PAL problem in $\tilde{O}(k)$ space and $\tilde{O}(k^{2})$
time per input character.111Hereafter, $\tilde{O}(\cdot)$ hides factors
polynomial in $\log n$. We continue their line of research and show streaming
algorithms for all four problems that use $\operatorname*{poly}(k,\log n)$
time per character and $\operatorname*{poly}(k,\log n)$ space. While streaming
algorithms are extremely efficient (in particular, the space complexities
above account for _all_ the space used by the algorithms, including the space
needed to store information about the input), it is important to note that
they are randomised in nature, which means that they may produce incorrect
results with a certain probability (inverse polynomial in the input size $n$).
Motivated by this, we also study the problems in the read-only model, where
random access to the input is allowed (and not accounted for in the space
usage). In this model, we show _deterministic_ algorithms for the four
problems that use $\operatorname*{poly}(k,\log n)$ time per character and
$\operatorname*{poly}(k,\log n)$ space; see Table 1 for a summary. As a side
result of independent interest, we develop the first
$\operatorname*{poly}(k,\log n)$ space read-only algorithms for computing
$k$-mismatch and $k$-edit occurrences of a pattern in a text.

Due to the lack of space, descriptions of the algorithms for the Language edit
distance problems ($k$-LED-PAL and $k$-LED-SQ) are omitted from this version
of the paper, but can be found in the full one.

###  1.1 Related work.

Offline model. In the classical _offline_ model, the problem of finding _all
maximal substrings_ that are within Hamming distance $k$ from PAL can be
solved in $O(nk)$ time as a simple application of the kangaroo jumps technique
[18]. For the edit distance, Porto and Barbosa [32] showed an $O(nk^{2})$
solution. For the SQ language, the best known solutions take $O(nk\log
k+\mathrm{output})$ time for the Hamming distance [23] and
$O(nk\log^{2}k+\mathrm{output})$ for the edit distance [26, 39, 40].

Online model. The problems $k$-LHD-PAL and $k$-LED-PAL can be viewed as a
generalization of the classical online palindrome recognition problem (see
[17] and references therein).

Streaming algorithms for PAL and SQ. Berebrink et al. [6] followed by
Gawrychowski et al. [20] studied the question of computing the length of a
maximal substring of a stream that belongs to PAL. Merkurev and Shur [29]
considered a similar question for the SQ language.

##  2 Preliminaries

We assume to be given an alphabet $\Sigma$, the elements of which, called
characters, can be stored in a single machine word of the RAM model. For an
integer $n\geq 0$, we denote the set of all length-$n$ strings by
$\Sigma^{n}$, and we set $\Sigma^{\leq n}=\bigcup_{m=0}^{n}\Sigma^{m}$ as well
as $\Sigma^{*}=\bigcup_{n=0}^{\infty}\Sigma^{n}$. The empty string is denoted
by $\varepsilon$.

For two strings $S,T\in\Sigma^{*}$, we use $ST$ or $S\cdot T$ indifferently to
denote their concatenation. For an integer $m\geq 0$, the string obtained by
concatenating $S$ to itself $m$ times is denoted by $S^{m}$; note that
$S^{0}=\varepsilon$. A string $S$ is a _square_ if there exists a string $T$
such that $S=T^{2}$.

For a string $T\in\Sigma^{n}$ and an index $i\in[1.\,.n]$,222For integers
$i,j\in\mathbb{Z}$, denote $[i.\,.j]=\\{k\in\mathbb{Z}:i\leq k\leq j\\}$,
$[i.\,.j)=\\{k\in\mathbb{Z}:i\leq k<j\\}$, and
$(i.\,.j]={\\{k\in\mathbb{Z}:i<k\leq j\\}}$. the $i$th character of $T$ is
denoted by $T[i]$. We use $|T|=n$ to denote the length of $T$. For indices
$1\leq i,j\leq n$, $T[i.\,.j]$ denotes the substring $T[i]T[{i+1}]\cdots T[j]$
of $T$ if $i\leq j$ and the empty string otherwise. When $i=1$ or $j=n$, we
omit these indices, i.e., we write $T[.\,.j]=T[1.\,.j]$ and
$T[i.\,.]=T[i.\,.n]$. We extend the above notation with
$T[i.\,.j)=T[i.\,.j-1]$ and $T(i.\,.j]=T[i+1.\,.j]$. We say that a string $P$
is a _prefix_ of $T$ if there exists $j\in[1.\,.n]$ such that $P=T[.\,.j]$,
and a _suffix_ of $T$ if there exists $i\in[1.\,.n]$ such that $P=T[i.\,.]$.
We use $T^{R}$ to denote the reverse of $T$, that is $T^{R}=T[n]T[n-1]\cdots
T[1]$. A string $T$ is a _palindrome_ if $T^{R}=T$.

We define the _forward cyclic rotation_ $\mathsf{rot}(T)=T[2]\cdots T[n]T[1]$.
In general, a cyclic rotation $\mathsf{rot}^{s}(T)$ with shift
$s\in\mathbb{Z}$ is obtained by iterating $\mathsf{rot}$ or the inverse
operation $\mathsf{rot}^{-1}$. A non-empty string $T\in\Sigma^{n}$ is
_primitive_ if it is distinct from its non-trivial rotations, i.e., if
$T=\mathsf{rot}^{s}(T)$ holds only when $n$ divides $s$.

Given two strings $U,V$ and two indices $i\in[1.\,.|U|]$ and $j\in[1.\,.|V|]$,
the _longest common prefix_ (LCP) of $U[i.\,.]$ and $V[j.\,.]$, denoted
$\textsf{LCP}(U[i.\,.],V[j.\,.])$, is the length of the longest string that is
a prefix of both $U[i.\,.]$ and $V[j.\,.]$.

Given two non-empty strings $U,Q$ and an operator $F$ defined over pairs of
strings, we use the notation $F(U,Q^{\infty})$ for the application of $F$ to
$U$ and the prefix of $Q^{\infty}=QQ\cdots$ that has the same length as $U$,
i.e., $F(U,Q^{\infty})=F(U,Q^{m}[.\,.|U|])$, where $m$ is any integer such
that $|Q^{m}|\geq|U|$. We define $F(Q^{\infty},U)$ symmetrically.

###  2.1 Hamming distance, palindromes, and squares

The Hamming distance between two strings $S,T$ (denoted $\mathsf{hd}(S,T)$) is
defined to be equal to infinity if $S$ and $T$ have different lengths, and
otherwise to the number of positions where the two strings differ
(mismatches). We define the _mismatch information_ between two length-$n$
strings $S$ and $T$, $\mathsf{MI}(S,T)$ as the set
$\\{(i,S[i],T[i]):i\in[1.\,.n]\text{ and }S[i]\neq T[i]\\}$. For two strings
$P,T$, a position $i\in[|P|.\,.|T|]$ of $T$ is a $k$-mismatch occurrence of
$P$ in $T$ if $\mathsf{hd}(T(i-|P|.\,.i],P)\leq k$. For an integer $k$, we
denote $\mathsf{hd}_{\leq k}(X,Y)=\mathsf{hd}(X,Y)$ if $\mathsf{hd}(X,Y)\leq
k$ and $\infty$ otherwise.

Due to the self-similarity of palindromes and squares, the Hamming distance
from a string $U$ to PAL and SQ can be measured in terms of the self-
similarity of $U$.

######  Property .

Each string $U\in\Sigma^{m}$ satisfies
$\mathsf{hd}(U,\textsc{PAL})=\mathsf{hd}(U[.\,.\lfloor{m/2}\rfloor],U(\lceil{m/2}\rceil.\,.]^{R})=\frac{1}{2}\mathsf{hd}(U,U^{R})$.

###### Proof.

Denote $U_{1}=U[.\,.\lfloor{m/2}\rfloor]$ and
$U_{2}=U(\lceil{m/2}\rceil.\,.]$. For the second equality, we have
$\mathsf{hd}(U,U^{R})=\mathsf{hd}(U_{1},U_{2}^{R})+\mathsf{hd}(U_{2},U_{1}^{R})=2\cdot\mathsf{hd}(U_{1},U_{2}^{R})$.

The first equality is equivalent to
$\mathsf{hd}(U_{1},U_{2}^{R})=\mathsf{hd}(U,\textsc{PAL})$. As the Hamming
distance between $U$ and the palindrome $U_{2}^{R}U_{2}$ (or $U_{2}^{R}aU_{2}$
if $m$ is odd) is $\mathsf{hd}(U_{1},U_{2}^{R})$, we have
$\mathsf{hd}(U_{1},U_{2}^{R})\geq\mathsf{hd}(U,\textsc{PAL})$.

Conversely, let $V$ be a palindrome such that
$\mathsf{hd}(U,V)=\mathsf{hd}(U,\textsc{PAL})$. We decompose similarly $V$
into $V_{1}V_{1}^{R}$ (or $V_{1}bV_{1}^{R}$ for odd $m$) and obtain
$\mathsf{hd}(U,V)\geq\mathsf{hd}(U_{1},V_{1})+\mathsf{hd}(U_{2},V_{1}^{R})$.
Using the fact that
$\mathsf{hd}(U_{2},V_{1}^{R})=\mathsf{hd}(U_{2}^{R},V_{1})$ and applying the
triangle inequality, we get
$\mathsf{hd}(U_{1},U_{2}^{R})\leq\mathsf{hd}(U,\textsc{PAL})$. ∎

######  Property .

Each string $U\in\Sigma^{m}$ satisfies
$\mathsf{hd}(U,\textsc{SQ})=\mathsf{hd}(U[.\,.m/2],U(m/2.\,.])$ if $m$ is even
and $\mathsf{hd}(U,\textsc{SQ})=\infty$ if $m$ is odd.

###### Proof.

Every square has even length; hence, if $m$ is odd, the distance between $U$
and SQ is infinite. In what follows, we assume that $m=2i$ for some
$i\in\mathbb{N}$. Let $U_{1}=U[.\,.i]$ and $U_{2}=U(i.\,.]$. By modifying the
copy of $U_{1}$ in $U$ into $U_{2}$, we obtain a square $U_{2}U_{2}$; hence,
$\mathsf{hd}(U,\textsc{SQ})\leq\mathsf{hd}(U_{1},U_{2})$.

For the converse inequality, let $V^{2}$ be a square such that
$\mathsf{hd}(U,\textsc{SQ})=\mathsf{hd}(U,V^{2})$. We have
$|V|=|U_{1}|=|U_{2}|$; hence,
$\mathsf{hd}(U,V^{2})=\mathsf{hd}(U_{1},V)+\mathsf{hd}(V,U_{2})$. Applying the
triangle inequality, we obtain
$\mathsf{hd}(U,\textsc{SQ})=\mathsf{hd}(U,V^{2})\geq\mathsf{hd}(U_{1},U_{2})$.
∎

###  2.2 Models of computation

In this work, we focus on two by now classical models of computation:
streaming and read-only random access. In the streaming model, we assume that
the input string $T$ arrives as a stream, one character at a time. For each
prefix $T[1.\,.i]$, we must report the distance to PAL or SQ as soon as we
receive $T[i]$. We account for all the space used, including the space needed
to store any information about $T$. In contrast, in the read-only model, we do
not account for the space occupied by the input string. We assume that $T$ is
read from the left to the right. After having read $T[1.\,.i]$, we assume to
have constant-time read-only random access to the first $i$ characters of $T$.
Similar to the streaming model, the distance from $T[1.\,.i]$ to PAL or SQ
must be reported as soon as we read $T[i]$.

##  3 Warm-up: Streaming algorithms for the LHD problems

In this section, we present streaming algorithms for $k$-LHD-PAL and $k$-LHD-
SQ. Our solutions use the Hamming distance sketches introduced by Clifford,
Kociumaka, and Porat [12] to solve the streaming $k$-mismatch problem.

######  Fact .

There exists a function $\mathsf{sk}^{\mathsf{hd}}_{k}$ (parameterized by a
constant $c>1$, integers $n\geq k\geq 1$, and a seed of $O(\log n)$ random
bits) that assigns an $O(k\log n)$-bit sketch to each string in $\Sigma^{\leq
n}$. Moreover:

  1. 1.

There is an $O(k\log^{2}n)$-time _encoding_ algorithm that, given
$U\in\Sigma^{\leq k}$, builds $\mathsf{sk}^{\mathsf{hd}}_{k}(U)$.

  2. 2.

There is an $O(k\log n)$-time algorithm that, given any two among
$\mathsf{sk}^{\mathsf{hd}}_{k}(U),\mathsf{sk}^{\mathsf{hd}}_{k}(V)$, or
$\mathsf{sk}^{\mathsf{hd}}_{k}(UV)$, computes the third one (provided that
$|UV|\leq n$).

  3. 3.

There is an $O(k\log^{3}n)$-time _decoding_ algorithm that, given
$\mathsf{sk}^{\mathsf{hd}}_{k}(U)$ and $\mathsf{sk}^{\mathsf{hd}}_{k}(V)$,
computes $\mathsf{MI}(U,V)$ if $\mathsf{hd}(U,V)\leq k$. The error probability
is $O(n^{-c})$.

###  3.1 A streaming algorithm for $k$-LHD-PAL

We first show that the sketches described in Section 3 give a simple algorithm
improving upon the result of Amir and Porat [3] and achieving the time
complexity of $\tilde{O}(k)$ per letter.

######  Theorem 3.1.

There is a randomised streaming algorithm that solves the $k$-LHD-PAL problem
for a string $T\in\Sigma^{n}$ using $O(k\log n)$ bits of space and
$O(k\log^{3}n)$ time per character. The algorithm errs with probability
inverse-polynomial in $n$.

Using Property 2.1, we can reduce the $k$-LHD-PAL problem to that of computing
the threshold Hamming distance between the current prefix of the input string
and its reverse. The algorithm maintains the sketches
$\mathsf{sk}^{\mathsf{hd}}_{2k}(T[.\,.i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{2k}(T[.\,.i]^{R})$. When it receives $T[i]$, it
constructs $\mathsf{sk}^{\mathsf{hd}}_{2k}(T[i])$, updates both
$\mathsf{sk}^{\mathsf{hd}}_{2k}(T[.\,.i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{2k}(T[.\,.i]^{R})$, and computes
$d=\mathsf{hd}_{\leq 2k}(T[.\,.i],T[.\,.i]^{R})$ (in $O(k\log^{3}n)$ total
time by Section 3). Section 2.1 implies $\mathsf{hd}_{\leq
k}(T[.\,.i],\textsc{PAL})=d/2$. The error probability of the algorithm follows
from the error probability for the decoding algorithm for Hamming distance
sketches.

The algorithm uses $O(k\log n)$ bits, which is nearly optimal: Indeed, by
Property 2.1, if $U=VW$, with $|V|=|W|$, then
$\mathsf{hd}(U,U^{R})=2\cdot\mathsf{hd}(V,W^{R})$. Therefore, using a standard
reduction from streaming algorithms to one-way communication complexity
protocols, we obtain a lower bound of $\Omega(k)$ bits for the space
complexity of streaming algorithms for the $k$-LHD-PAL problem from the
$\Omega(k)$ bits lower bound for the communication complexity of the Hamming
distance [21].

###  3.2 A streaming algorithm for $k$-LHD-SQ

In this section, we show the following theorem:

######  Theorem 3.2.

There is a randomised streaming algorithm that solves the $k$-LHD-SQ problem
for a string $T\in\Sigma^{n}$ using $O(k\log^{2}n)$ bits of space and
$\tilde{O}(k)$ time per character. The algorithm errs with probability
inverse-polynomial in $n$.

Property 2.1 allows us to derive $\mathsf{hd}_{\leq k}(T[.\,.2i],\textsc{SQ})$
from the sketches $\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.2i])$: we can combine them to obtain
$\mathsf{sk}^{\mathsf{hd}}_{k}(T(i.\,.2i])$, and a distance computation on
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{k}(T(i.\,.2i])$ returns $\mathsf{hd}_{\leq
k}(T[.\,.i],T(i.\,.2i])=\mathsf{hd}_{\leq k}(T[.\,.2i],\textsc{SQ})$.

Naively applying this procedure requires storing the sketch
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ until the algorithm has read
$T[.\,.2i]$, that is, storing $\Theta(n)$ sketches at the same time. To reduce
the number of sketches stored, we use a filtering procedure based on the
following observation: If $\mathsf{hd}(T[.\,.2i],\textsc{SQ})\leq k$ and
$\ell\in[1.\,.i]$, then $i+\ell$ is a $k$-mismatch occurrence of
$T[.\,.\ell]$, that is, $\mathsf{hd}(T[.\,.\ell],T(i.\,.i+\ell])\leq k$. For
example, for $k=1,\ell=2$ and $i=3$, the word $S=abc\mathbf{ac}c$ is a
$1$-mismatch square (by Section 2.1) and the substring
$P^{\prime}=\mathbf{ac}$ is a 1-mismatch occurrence of the prefix $P=ab$ of
$S$.

This observation motivates our filtering procedure: if we choose some prefix
$P=T[.\,.\ell]$ of the string, we only need to store every $i\leq\ell$ such
that $i+\ell$ is a $k$-mismatch occurrence of $P$. Clifford, Kociumaka and
Porat [12] showed a data structure $\mathcal{S}$ that exploits the structure
of such occurrences and stores them using $O(k\log^{2}n)$ bits of space while
allowing reporting the occurrence at position $i+\ell$ when $T[i+\ell+\Delta]$
is pushed into $\mathcal{S}$ – we say that $\mathcal{S}$ reports the
$k$-mismatch occurrences of $P$ in $T$ with _a constant delay_ $\Delta$ [12].
Our algorithm needs to receive the occurrence at position $i+\ell$ when
$T[2i]$ is pushed into the stream, i.e. we require $\mathcal{S}$ to report
occurrences with a non-decreasing delay. In Section 3.2.1 we present a
modification of the data structure [12] to allow non-decreasing delays, and in
Section 3.2.2 we explain how we use it to implement a space-efficient
streaming algorithm for $k$-LHD-SQ.

####  3.2.1 Reporting $k$-mismatch occurrences with nondecreasing delay.

The algorithm of Clifford, Kociumaka, and Porat [12] reports additional
information along with the position of the $k$-mismatch occurrences: it
produces the _stream of $k$-mismatch occurrences of $P$ in $T$_, defined as
follows.

######  Definition 3.3 ([12, Definition 3.2]).

The stream of $k$-mismatch occurrences of a pattern $P$ in a text $T$ is a
sequence $S_{P}^{k}$ such that
$S_{P}^{k}[i]=(i,\;\mathsf{MI}(T(i-|P|.\,.i],P),\;\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i-|P|]))$
if $\mathsf{hd}(P,T(i-|P|.\,.i])\leq k$ and $\bot$ otherwise.

As explained next, the algorithm of [12] can report the $k$-mismatch
occurrences with a prescribed delay.

######  Corollary 3.4 (of [12]).

There is a streaming algorithm that, given a pattern $P$ followed by a text
$T\in\Sigma^{n}$, reports the $k$-mismatch occurrences of $P$ in $T$ using
$O(k\log^{2}n)$ bits of space and $O(\sqrt{k\log^{3}n}+\log^{4}n)$ time per
character. The algorithm can report each occurrence $i$ with no delay (that
is, upon receiving $T[i]$) or with any prescribed delay $\Delta=\Theta(|P|)$
(that is, upon receiving $T[i+\Delta]$). For each reported occurrence $i$, the
underlying tuple $S_{P}^{k}[i]$ can be provided on request in $O(k\log^{2}n)$
time.

######  Proof 3.5.

If no delay is required, we use [12, Theorem 1.2], which reports $k$-mismatch
occurrences of $P$ in $T$ and, upon request, provides the mismatch information
$\mathsf{MI}(T(i-|P|.\,.i],P)$; this algorithm uses $O(k\log^{2}n)$ bits of
space and takes $O(\sqrt{k\log^{3}n}+\log^{4}n)$ time per character. We also
use [12, Fact 4.4] to maintain the sketch
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ (reported on request); this
algorithm uses $O(k\log n)$ bits of space and takes $O(\log^{2}n)$ time per
character.

Whenever requested to provide $S_{P}^{k}[i]$ for some $k$-mismatch occurrence
$i$ of $P$ in $T$, we retrieve the mismatch information
$\mathsf{MI}(T(i-|P|.\,.i],P)$ (in $O(k)$ time) and the sketch
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ (in $O(k\log^{2}n)$ time). Combining
$\mathsf{sk}^{\mathsf{hd}}_{k}(P)$ with $\mathsf{MI}(T(i-|P|.\,.i],P)$, we
build $\mathsf{sk}^{\mathsf{hd}}_{k}(T(i-|P|.\,.i])$ (using [12, Lemma 6.4] in
$O(k\log^{2}n)$ time) and then derive
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i-|P|])$ using Section 3 (in $O(k\log n)$
time). Overall, processing the request takes $O(k\log^{2}n)$ time and
$O(k\log^{2}n)$ bits of space.

If a delay $\Delta=\Theta(|P|)$ is required, our approach depends on whether
there exists $p\in[1.\,.k]$ such that
$\mathsf{hd}(P[.\,.|P|-p],P(p.\,.|P|])\leq 2k$ (such $p$ is called a
$2k$-period in [12]). This property is tested using a streaming algorithm of
[12, Lemma 4.3], which takes $O(k\log n)$ bits of space, $O(\sqrt{k\log n})$
time per character of $P$, and requires $O(k\sqrt{k\log n})$-time post-
processing (performed while reading $T[.\,.k]$). If $P$ satisfies this
condition, then we just use [12, Theorem 4.2], whose statement matches that of
Corollary 3.4.

Otherwise, [12, Observation 4.1] shows that $P$ has at most one $k$-mismatch
occurrence among any $k$ consecutive positions in $T$. In that case, we use
the aforementioned approach to produce the stream $S_{P}^{k}$ with no delay
and the buffer of [12, Proposition 3.3] to delay the stream by $\Delta$
characters. The buffering algorithm takes $O(k\log^{2}n)$ bits of space and
processes each character $T[i]$ in $O(k\log^{2}n+\log^{3}n)$ time (if $P$ has
$k$-mismatch occurrences at positions $i$ or $i-\Delta$) or $O(\sqrt{k\log
n}+\log^{3}n)$ time (otherwise). Since the former case holds for at most two
out of every $k$ consecutive positions, we can achieve
$O(\sqrt{k\log^{3}n}+\log^{4}n)$ worst-case time per character by decreasing
the delay to $\Delta-k$ and buffering up to $k$ characters of $T$ and up to
$k$ elements of $S_{P}^{k}$. While the algorithm processes $T[i+\Delta]$, the
latter buffer already contains $S_{P}^{k}[i]$, but $O(k)$ time is still needed
to output this value (if $S_{P}^{k}[i]\neq\bot$).

The algorithm of Corollary 3.4 has a fixed delay $\Delta$, i.e., it outputs
$S_{P}^{k}[i]$ upon receiving $T[i+\Delta]$. Our application requires a
variable delay: we need to access $S_{P}^{k}[i+|P|]$ upon reading $T[2i]$. We
present a black-box construction that extends the data structure of Corollary
3.4 to support non-decreasing delays $\Delta_{i}$, $i\in[1.\,.d]$. Naively,
one could use the algorithm $\mathcal{A}$ of Corollary 3.4 with a fixed delay
$\Delta_{1}$ and buffer the input characters so that $\mathcal{A}$ receives
$T[i+\Delta_{1}]$ only when we actually process $T[i+\Delta_{i}]$.
Unfortunately, this requires storing $T[i+\Delta_{1}.\,.i+\Delta_{i})$, which
could take too much space. Thus, we feed $\mathcal{A}$ with
$T[1.\,.\Delta_{1}]$ followed by blank characters $\bot$ (issued at
appropriate time steps without the necessity of buffering input characters) so
that $\mathcal{A}$ reports $k$-mismatch occurrences $i\in[1.\,.\Delta_{1}]$
with prescribed delays. Then, we use another instance of the algorithm of
Corollary 3.4, with a fixed delay $\Delta_{1+\Delta_{1}}$, to output
$k$-mismatch occurrences
$i\in(\Delta_{1}.\,.\Delta_{1}+\Delta_{1+\Delta_{1}}]$; we continue this way
until the whole interval $[1.\,.d]$ is covered. We formalise this idea in the
following lemma.

######  Lemma 3.6.

Let $\Delta_{1}\leq\Delta_{2}\leq\cdots\leq\Delta_{d}$ be a non-decreasing
sequence of $d=O(|P|)$ integers $\Delta_{i}=\Theta(|P|)$, represented by an
oracle that reports each element $\Delta_{i}$ in constant time.

There is a streaming algorithm that, given a pattern $P$ followed by a text
$T$, reports the $k$-mismatch occurrences of $P$ in $T$ using $O(k\log^{2}n)$
bits of space and $O(\sqrt{k\log^{3}n}+\log^{4}n)$ time per character. The
algorithm reports each occurrence $i\in[1.\,.d]$ with delay $\Delta_{i}$, that
is, upon receiving $T[i+\Delta_{i}]$. For each reported occurrence
$i\in[1.\,.d]$, the underlying tuple $S_{P}^{k}[i]$ can be provided on request
in $O(k\log n)$ time.

######  Proof 3.7.

We use multiple instances $\mathcal{A}_{1},\ldots,\mathcal{A}_{t}$ of the
algorithm of Corollary 3.4. We define a sequence $(s_{r})_{r=0}^{t}$ so that
$\mathcal{A}_{r}$ works with a fixed delay $\Delta_{s_{r-1}}$, it is given
$T[1.\,.s_{r})\cdot\bot^{\Delta_{s_{r-1}}}$, and it reports $k$-mismatch
occurrences $i\in[s_{r-1}.\,.s_{r})$. Specifically, we set $s_{0}=1$ and
$s_{r}=s_{r-1}+\Delta_{s_{r-1}}$, with $t$ chosen as the smallest integer such
that $s_{t}>d$. Note that $s_{r}-s_{r-1}=\Delta_{s_{r-1}}\geq\Delta_{1}$
implies $t\leq 1+\frac{d}{\Delta_{1}}=O(1)$.

We assign three different roles to the algorithms
$\mathcal{A}_{1},\ldots,\mathcal{A}_{r}$: _passive_ , _active_ , and
_inactive_. While we process $T[j]$, the algorithm $\mathcal{A}_{r}$ is
passive if $j<s_{r}$, active if $j\in[s_{r-1}.\,.s_{r})$, and inactive if
$j\geq s_{r}$. Our invariant is that, once we process $T[j]$, each passive
algorithm $\mathcal{A}_{r}$ has already received $T[1.\,.j]$, the unique
active algorithm $\mathcal{A}_{r}$ has already received
$T[1.\,.s_{r})\cdot\bot^{1+i-s_{r-1}}$, where $i$ is the largest integer such
that $i+\Delta_{i}\leq j$, and each inactive algorithm $\mathcal{A}_{r}$ has
already received its entire input, that is,
$T[1.\,.s_{r})\cdot\bot^{\Delta_{s_{r-1}}}$.

Upon receiving $T[j]$, we simply forward $T[j]$ to all passive algorithms.
Moreover, if $j=i+\Delta_{i}$ for some $i\in[1.\,.d]$, we feed the active
algorithm with $\bot$ so that it checks whether $i$ is a $k$-mismatch
occurrence of $P$ in $T$ and, upon request, outputs $S_{P}^{k}[i]$.

Let us argue that this approach is correct from the perspective of a fixed
algorithm $\mathcal{A}_{r}$. As we process $T[1.\,.s_{r})$, the algorithm is
passive, and it is fed with subsequent characters of $T$. For $j=s_{r}-1$, the
position $i=s_{r-1}-1$ is the maximum one such that $i+\Delta_{i}\leq j$.
Consequently, the input $T[1.\,.s_{r})$ already satisfies the invariant for
passive algorithms. For subsequent iterations $j\in[s_{r}.\,.s_{r+1})$, as
$\mathcal{A}_{r}$ is active, it receives $\bot$ whenever $i$ increases, so its
input stays equal to $T[1.\,.s_{r})\cdot\bot^{1+i-s_{r-1}}$. The length of
this string is $s_{r}+i-s_{r-1}=i+\Delta_{s_{r-1}}$, so the algorithm indeed
checks whether $i$ is a $k$-mismatch occurrence of $P$ in $T$ at each such
iteration (recall that its fixed delay is $\Delta_{s_{r-1}}$), and it
satisfies the invariant for active algorithms. Once we reach $j=s_{r+1}-1$, we
have $i=s_{r}-1=s_{r-1}+\Delta_{s_{r-1}}-1$, so the input becomes
$T[1.\,.s_{r})\cdot\bot^{\Delta_{s_{r-1}}}$, and it already satisfies the
invariant for inactive algorithms. The state of inactive algorithms does not
change, so this invariant remains satisfied as $\mathcal{A}_{r}$ stays
inactive indefinitely.

The time and space complexity follow from the fact that $t=O(1)$.

####  3.2.2 Algorithm

We now show how to use the data structure of Lemma 3.6 to implement our
filtering procedure using low space.

######  Claim 1.

For each $j\in[1.\,.\lfloor\log n\rfloor]$, let $\mathsf{Occ}_{j}$ be the set
of $k$-mismatch occurrences of $P_{j}$ in $T_{j}=T[3\ell_{j}/2.\,.4\ell_{j})$.
If $\mathsf{hd}(T[.\,.2i],\textsc{SQ})\leq k$ and
$2i\in[3\ell_{j}.\,.6\ell_{j})$, then $p=i-\ell_{j}/2\in\mathsf{Occ}_{j}$.

######  Proof 3.8.

Since $\ell_{j}\leq i$, Section 3.2 implies that $i+\ell_{j}$ is a
$k$-mismatch occurrence of $P_{j}$ in $T$. Moreover, when
$2i\in[3\ell_{j}.\,.6\ell_{j})$, we have $3\ell_{j}/2\leq i3\ell_{j}$,
therefore that $k$-mismatch occurrence of $P_{j}$ is fully contained within
$T_{j}$, and it appears at index $i+\ell_{j}-3\ell_{j}/2=i-\ell_{j}/2$ in
$T_{j}$.

In what follows, we use $p$ to denotes indices in $T_{j}$, and $i$ to denote
indices in the original text $T$. As $T_{j}=T(3\ell_{j}/2.\,.4\ell_{j}]$, the
correspondance is given by $i=p+3\ell_{j}/2$. In other words, we only need to
compute $\mathsf{hd}_{\leq k}(T[.\,.2i],\textsc{SQ})$ when
$i-\ell_{j}/2\in\mathsf{Occ}_{j}$. As noted in Property 2.1, it suffices to
know the sketches $\mathsf{sk}^{\mathsf{hd}}_{k}(T(i.\,.2i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$. We store
$\mathsf{sk}^{\mathsf{hd}}_{k}(P_{j})=\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.\ell_{j}])$
and maintain $\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.2i])$ in a rolling manner as
we receive the characters of the text.

We use the algorithm of Lemma 3.6, asking for $k$-mismatch occurrences of
$P_{j}$ in $T_{j}$, to report
$\mathsf{sk}^{\mathsf{hd}}_{k}(T_{j}[.\,.i-\ell_{j}])=\mathsf{sk}^{\mathsf{hd}}_{k}(T(\ell_{j}.\,.i])$
for every $i\in\mathsf{Occ}_{j}$. We specify the delay sequence as
$\Delta_{p}=p-\ell_{j}/2$ for $p\in[\ell_{j}.\,.5\ell_{j}/2)$ so that the
conditions of Lemma 3.6 are satisfied. (Note that $\Delta_{p}$ does not need
to be defined for $p<\ell_{j}$, as there cannot be a $k$-mismatch occurrence
of $P_{j}$ before position $\ell_{j}$) This way, for every
$i\in[3\ell_{j}/2.\,.3\ell_{j})$, we receive $S_{P_{j}}^{k}[i+\ell_{j}]$
(which corresponds to a potential $k$-mismatch occurrence starting at position
$i+1$) while processing $T_{j}[p+\Delta_{p}]$ for
$p=i+\ell_{j}-3\ell_{j}/2=i-\ell_{j}/2$. As $\Delta_{p}=p-\ell_{j}/2$, this
correponds to position $p^{\prime}=2p-\ell_{j}/2$ in $T_{j}$, or position
$i^{\prime}=2p+\ell_{j}=2i$ in $T$, i.e. this happens precisely as we are
processing $T[2i]$. See Figure 1 for an illustration of the above. If
$S_{P_{j}}^{k}[i+\ell_{j}]$ is blank, we move on to the next position.
Otherwise, we retrieve the sketch
$\mathsf{sk}^{\mathsf{hd}}_{k}(T_{j}[.\,.i])=\mathsf{sk}^{\mathsf{hd}}_{k}(T[3\ell_{j}/2.\,.i])$,
combine it with $s_{j}=\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.3\ell_{j}/2))$
(stored separately) and $\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.2i])$ to obtain
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{k}(T(i.\,.2i])$, and use the latter two sketches
to compute $\mathsf{hd}_{\leq k}(T[.\,.i],T(i.\,.2i])$, which is equal to
$\mathsf{hd}_{\leq k}(T[.\,.2i],\textsc{SQ})$ by Section 2.1.

$T$$3\ell_{j}/2$$4\ell_{j}$$i$$i+\ell_{j}$$2i$$P_{j}$$P^{\prime}$$T_{j}$$0$$p=i-\ell_{j}/2$$\Delta_{p}=p-\ell_{j}/2$
Figure 1:  Illustration of our filtering procedure. Here, $P^{\prime}$ is a
$k$-mismatch occurrence of $P_{j}$ at position $i+\ell_{j}$ in $T$ and
position $p=i-\ell_{j}/2$ in $T_{j}$, reported with delay
$\Delta_{p}=p-\ell_{j}/2$ in $T_{j}$, hence it arrives at time $2i$ in $T$.

We proceed with the complexity analysis of our algorithm. The $k$-mismatch
pattern matching algorithm of Lemma 3.6 uses $O(k\log^{2}n)$ bits of space and
$\tilde{O}(k)$ time per character, and we maintain $O(\log n)$ instances of
this algorithm. However, since all the patterns $P_{j}$ are prefixes of $T$,
the instances can share the pattern processing phase. Moreover, since
$P_{j}\cdot T_{j}$ are prefixes of $T$ and any position is contained in at
most three fragments $T_{j}$, at most three instances contribute to the time
and space complexity at any given moment. Thus, the entire algorithm uses
$O(k\log^{2}n)$ bits of space and $\tilde{O}(k)$ time per character, which
completes the proof of Theorem 3.2.

Our streaming algorithm for $k$-LED-SQ (Theorem 5.2) relies on the streaming
algorithm for $k$-LHD-SQ. It requires testing
$\mathsf{hd}(T[.\,.2i],\textsc{SQ})\leq k$ only for selected positions $i$,
and thus it benefits from the following variant of Theorem 3.2:

######  Proposition 3.9.

There is a randomised streaming algorithm that, given a string
$T\in\Sigma^{n}$, upon receiving $T[2i]$, can be requested to test whether
$\mathsf{hd}(T[.\,.2i],\textsc{SQ})\leq k$ and, if so, report the mismatch
information between $T[.\,.2i]$ and a closest square. The algorithm uses
$O(k\log^{2}n)$ bits of space and processes each character in
$\tilde{O}(\sqrt{k})$ or $\tilde{O}(k)$ time, depending on whether the request
has been issued at that character.

######  Proof 3.10.

We follow the algorithm behind Theorem 3.2 with minor modifications. First,
instead of maintaining $\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.2i])$ explicitly,
we apply [12, Fact 4.4], which uses $O(k\log n)$ bits of space, takes
$O(\log^{2}n)$ time per character, and reports
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.2i])$ on demand in $O(k\log^{2}n)$ time.

To process a request concerning position $2i$, we retrieve
$\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.2i])$ and ask the pattern-matching
algorithm of Lemma 3.6 to output $S_{P_{j}}^{k}[i]$ (normally, the algorithm
only reports whether $i$ is a $k$-mismatch occurrence of $P_{j}$ in $T_{j}$).
In this case, we build $\mathsf{sk}^{\mathsf{hd}}_{k}(T[.\,.i])$ and
$\mathsf{sk}^{\mathsf{hd}}_{k}(T(i.\,.2i])$ as in the proof of Theorem 4.7.
The decoding algorithm not only results in $\mathsf{hd}_{\leq
k}(T[.\,.i],T(i.\,.2i])=\mathsf{hd}_{\leq k}(T[.\,.2i],\textsc{SQ})$ but, if
$\mathsf{hd}(T[.\,.2i],\textsc{SQ})\leq k$, also the underlying mismatch
information.

The space complexity of the modified algorithm is still $O(k\log^{2}n)$ bits.
The running time is $\tilde{O}(\sqrt{k})$ if we do not ask the algorithm to
test $\mathsf{hd}(T[.\,.2i],\textsc{SQ})\leq k$ and $\tilde{O}(k)$ if we do.

##  4 Deterministic read-only algorithms for the LHD problems

In this section, we present deterministic read-only algorithms for $k$-LHD-PAL
and $k$-LHD-SQ. We start by recalling structural results for $k$-mismatch
occurrences used by the algorithms.

###  4.1 Structure of $k$-mismatch occurrences

######  Definition 4.1 ([10]).

A string $U$ is $d$-mismatch periodic if there exists a primitive string $Q$
such that $|Q|\leq|U|/128d$ and $\mathsf{hd}(U,Q^{\infty})\leq 2d$. Such a
string $Q$ is called the _$d$ -mismatch period_ of $U$.

The condition $|Q|\leq|U|/128d$ implies that $Q$ is equal to some substring of
$U$; hence, given the starting and ending positions of $Q$ in $U$ and random
access to $U$, we can simulate random access to $Q$.

######  Claim 2 (From [22, Claim 7.1]).

Let $U$ and $V$ be strings such that $U$ is a prefix of $V$, and $|V|\leq
2|U|$. If $U$ is $d$-mismatch periodic with $d$-mismatch period $Q$, then $V$
either is not $d$-mismatch periodic or has $d$-mismatch period $Q$.

Charalampopoulos, Kociumaka, and Wellnitz [10] showed that the set of
$k$-mismatch occurrences has a very regular structure:

######  Fact 3 (See [10, Section 3]).

Let $P$ and $T$ be two strings such that $|P|\leq|T|\leq 3/2|P|$.

  1. 1.

If $P$ is not $k$-mismatch periodic, then there are $O(k)$ $k$-mismatch
occurrences of $P$ in $T$.

  2. 2.

If $P$ is $k$-mismatch periodic with period $Q$, then any two $k$-mismatch
occurrences $i\leq i^{\prime}$ of $P$ in $T$ satisfy $i\equiv
i^{\prime}\pmod{|Q|}$ and $\mathsf{hd}(T(i-|P|.\,.i^{\prime}],Q^{\infty})\leq
3k$.

They also presented efficient offline algorithms for computing the
$k$-mismatch period and the $k$-mismatch occurrences in the so-called PILLAR
model. In this model, one is given a family of strings $\mathcal{X}$ for
preprocessing. The elementary objects are fragments $X[i.\,.j]$ of strings
$X\in\mathcal{X}$. Given elementary objects $S,S_{1},S_{2}$, the PILLAR
operations are:

  1. 1.

$\mathsf{Access}(S,i)$: Assuming $i\in[1.\,.|S|]$, retrieve $S[i]$.

  2. 2.

$\mathsf{Length}(S)$: Retrieve the length $|S|$ of $S$.

  3. 3.

$\textsf{LCP}(S_{1},S_{2})$: Compute the length of the longest common prefix
of $S_{1}$ and $S_{2}$.

  4. 4.

$\textsf{LCP}^{R}(S_{1},S_{2})$: Compute the length of the longest common
suffix of $S_{1}$ and $S_{2}$.

  5. 5.

$\mathsf{IPM}(S_{1},S_{2})$: Assuming that $|S_{2}|\leq 2|S_{1}|$, compute the
set of the starting positions of occurrences of $S_{1}$ in $S_{2}$, which by
Fine and Wilf periodicity lemma [15] can be represented as one arithmetic
progression.

In the read-only model, operations $\mathsf{Access}$ and $\mathsf{Length}$ can
be implemented in constant time and $O(\log m)$ bits. The operations LCP and
$\textsf{LCP}^{R}$ can be implemented naively via character-by-character
comparison in $O(\min\\{|S_{1}|,|S_{2}|\\})$ total time and $O(\log m)$ bits.
Finally, the $\mathsf{IPM}$ operation can be implemented in
$O(|S_{1}|+|S_{2}|)$ total time and $O(\log m)$ bits (see e.g. [34]).

As a corollary, we immediately obtain:

######  Corollary 4.2 (From [10, Lemma 4.4]).

Given random access to a string $U$, testing whether it is $d$-mismatch
periodic, and, if so, computing its $d$-mismatch period, can be done using
$O(d|U|)$ time and $O(d)$ space.

###  4.2 Read-only algorithm for the pattern matching with $k$ mismatches

The above implementation of the PILLAR operations further implies an offline
algorithm that finds all $k$-mismatch occurrences of $P$ in $T$ in
$\tilde{O}(k^{2}\cdot|T|)$ time and $\tilde{O}(k^{2})$ space (see [10, Main
Theorem 8]). Nevertheless, we provide a more efficient online algorithm that
additionally provides the mismatch information for every $k$-mismatch
occurrence of $P$.

######  Theorem 4.3.

There is a deterministic online algorithm that finds all $k$-mismatch
occurrences of a length-$m$ pattern $P$ within a text $T$ using $O(k\log m)$
space and $O(k\log m)$ worst-case time per character. The algorithm outputs
the mismatch information along with every reported $k$-mismatch occurrence of
$P$.

Consistently with the streaming algorithm of [12], our algorithm uses a family
of exponentially-growing prefixes to filter out candidate positions. However,
in order to use the structural properties of 3 efficiently, we construct a
different family $\mathcal{P}$ to ensure that we are either working in an
approximately periodic region of the text or processing an aperiodic prefix.

We first add to $\mathcal{P}$ the prefixes
$R_{j}=P[.\,.\min\\{m,\lfloor(3/2)^{j}\rfloor\\}]$ for
$j\in[0.\,.\lceil\log_{3/2}m\rceil]$. If $R_{j}$ is $k$-mismatch periodic but
$R_{j+1}$ is not, we also add to $\mathcal{P}$ the shortest extension of
$R_{j}$ that is not $k$-mismatch periodic. Hereafter, let
$\mathcal{P}=(P_{j})_{j=1}^{t}$ denote the resulting sequence of prefixes,
sorted in order of increasing lengths, and let $\ell_{j}=|P_{j}|$ for every
$j\in[1.\,.t]$.

######  Claim 4.

The sequence $\mathcal{P}=(P_{j})_{j=1}^{t}$ satisfies the following
properties:

  1. (a)

$P_{1}=P[1]$ and $P_{t}=P$,

  2. (b)

$t=|\mathcal{P}|=O(\log m)$,

  3. (c)

for every $j\in[1.\,.t)$, we have $\ell_{j+1}\leq 3\ell_{j}/2$,

  4. (d)

for every $j\in[1.\,.t)$, if $P_{j}$ is $k$-mismatch periodic with period
$Q_{j}$, then $\mathsf{hd}(P_{j+1},Q_{j}^{\infty})\leq 2k+1$.

######  Proof 4.4.

Properties (a), (b), and (c) are straightforward. For Property (d), there are
two possible cases: if $P_{j+1}$ is $k$-mismatch periodic, 2 implies that
$P_{j+1}$ has the same $k$-mismatch period $Q_{j}$ as $P_{j}$, that is
$\mathsf{hd}(P_{j+1},Q_{j}^{\infty})\leq 2k$. Otherwise, by construction,
$P_{j+1}$ is the shortest extension of $P_{j}$ that is not $k$-mismatch
periodic. By minimality, removing its last character yields a $k$-mismatch
periodic prefix, and by 2, it has the same $k$-mismatch period $Q_{j}$ as
$P_{j}$, i.e., we have $\mathsf{hd}(P[.\,.\ell_{j+1}),Q_{j}^{\infty})\leq 2k$
for $i<\ell_{j}$. Adding one more character to $P[.\,.\ell_{j+1})$ can
increase the Hamming distance by at most one.

##### Processing the pattern.

In the preprocessing phase, we build $\mathcal{P}$ and, for each $k$-mismatch
periodic prefix $P_{j}\in\mathcal{P}\setminus\\{P\\}$, we also retrieve the
period $Q_{j}$ (represented as a fragment of $P_{j}$) and the mismatch
information $\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$. For subsequent indices
$j\in[0.\,.\lceil\log_{3/2}m\rceil]$, we add the prefix $R_{j}$ to
$\mathcal{P}$. If $R_{j}\neq P$, we apply Corollary 4.2 to test whether
$R_{j}$ is $k$-mismatch periodic and, if so, retrieve the period $Q$. If
$R_{j}$ is $k$-mismatch periodic, we build $\mathsf{MI}(R_{j},Q^{\infty})$ and
extend $R_{j}$ while maintaining the mismatch information with the appropriate
prefix of $Q^{\infty}$. We proceed until we reach length $|R_{j+1}|$ or $2k+1$
mismatches, whichever comes first. We add the obtained extension
$R_{j}^{\prime}$ to $\mathcal{P}$ and store the mismatch information
$\mathsf{MI}(R_{j}^{\prime},Q^{\infty})$. If
$\mathsf{hd}(R_{j}^{\prime},Q^{\infty})\leq 2k$, then $R_{j}^{\prime}=R_{j+1}$
is $k$-mismatch periodic with the same period $Q$. Otherwise, by 2, neither
$R_{j}^{\prime}$ nor $R_{j+1}$ are $k$-mismatch periodic. Processing each $j$
takes $O(|R_{j+1}|k)$ time and $O(k)$ space, for a total of $O(mk)$ time and
$O(k\log m)$ space across $j\in[0.\,.\lceil\log_{3/2}m\rceil]$.

##### Processing the text.

Our online algorithm processing the text $T$ consists of $t=|\mathcal{P}|$
layers, each of which reports the $k$-mismatch occurrences of
$P_{j}\in\mathcal{P}$, along with the underlying mismatch information.

The first layer, responsible for $P_{1}=P[1]$, is implemented naively in
$O(1)$ space and time per character.

Each of the subsequent layers receives the $k$-mismatch occurrences of $P_{j}$
and outputs the $k$-mismatch occurrences of $P_{j+1}$. The processing is based
on the following simple observation:

If $P_{j+1}$ has a $k$-mismatch occurrence at position $i$ of $T$, then
$P_{j}$ has a $k$-mismatch occurrence at position $i-\ell_{j+1}+\ell_{j}$ of
$T$.

We partition $T$ into blocks of length $b:=\lceil\ell_{j}/2\rceil$ and, for
each block $T(rb.\,.(r+1)b]$, use a separate subroutine to output $k$-mismatch
occurrences of $P_{j+1}$ at positions $i\in(rb.\,.(r+1)b]$. This subroutine
receives the $k$-mismatch occurrences of $P_{j}$ at positions
$i-\ell_{j+1}+\ell_{j}\in(rb-\ell_{j+1}+\ell_{j}.\,.(r+1)b-\ell_{j+1}+\ell_{j}]$.
It is considered _active_ as the algorithm reads
$T(rb-\ell_{j+1}+\ell_{j}.\,.(r+1)b]$; since
$\ell_{j+1}\leq\frac{3}{2}\ell_{j}$, at most two subroutines are active at any
given time. The implementation of the subroutine depends on whether $P_{j}$ is
$k$-mismatch periodic or not.

#####  $P_{j}$ is not $k$-mismatch periodic.

In this case, for every received $k$-mismatch occurrence $i^{\prime}$ of
$P_{j}$, the subroutine stores the mismatch information
$\mathsf{MI}(T(i^{\prime}-\ell_{j}.\,.i^{\prime}],P_{j})$ and, as the
algorithm receives subsequent characters $T[i]$ for
$i\in(i^{\prime}.\,.i^{\prime}+\ell_{j+1}-\ell_{j}]$, we maintain
$\mathsf{MI}(T(i^{\prime}-\ell_{j}\allowbreak.\,.i],P[.\,.\ell_{j}+i-i^{\prime}])$
as long as there are at most $k$ mismatches. If this is still the case for
$i=i^{\prime}+\ell_{j+1}-\ell_{j}$, we report a $k$-mismatch occurrence of
$P_{j+1}$ and output
$\mathsf{MI}(T(i^{\prime}-\ell_{j}\allowbreak.\,.i],P[.\,.\ell_{j}+i-i^{\prime}])=\mathsf{MI}(T(i-\ell_{j+1}.\,.i],P_{j+1})$.
By Section 4.2, no $k$-mismatch occurrence of $P_{j+1}$ is missed. Moreover, 3
guarantees that the subroutine receives $O(k)$ $k$-mismatch occurrences of
$P_{j}$, and thus it uses $O(k)$ space and $O(k)$ time per character.

#####  $P_{j}$ is $k$-mismatch periodic with period $Q_{j}$.

In this case, we wait for the leftmost $k$-mismatch occurrence
$p\in(rb-\ell_{j+1}+\ell_{j}.\,.(r+1)b-\ell_{j+1}+\ell_{j}]$ of $P_{j}$ and
ignore all the subsequent occurrences of $P_{j}$. We use the received mismatch
information $\mathsf{MI}(T(p-\ell_{j}.\,.p],P_{j})$ and the preprocessed
mismatch information $\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$ to construct
$\mathsf{MI}(T(p-\ell_{j}.\,.p],Q_{j}^{\infty})$; by the triangle inequality,
the size of this set is guaranteed to be at most $3k$. As the algorithm
receives subsequent characters of $T[i]$ for $i\in(p.\,.(r+1)b]$, we maintain
$\mathsf{MI}(T(p-\ell_{j}.\,.i],Q_{j}^{\infty})$ as long as the number of
mismatches does not exceed $6k+1$. Whenever $i\geq p+\ell_{j+1}-\ell_{j}$ and
$i\equiv p+\ell_{j+1}-\ell_{j}\pmod{|Q_{j}|}$, we extract
$\mathsf{MI}(T(i-\ell_{j+1}.\,.i],Q_{j}^{\infty})$ from
$\mathsf{MI}(T(p-\ell_{j}.\,.i],Q_{j}^{\infty})$ and use the precomputed
mismatch information $\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$ to construct
$\mathsf{MI}(T(i-\ell_{j+1}.\,.i],P_{j})$. If it is of size at most $k$, we
report $i$ as a $k$-mismatch occurrence of $P_{j}$.

As for the correctness, we argue that we miss no $k$-mismatch occurrence
$i\in(rb.\,.(r+1)b]$ of $P_{j+1}$ in $T$. Since
$\mathsf{hd}(T(i-\ell_{j+1}.\,.i],P_{j+1})\leq k$ and
$\mathsf{hd}(P_{j+1},Q_{j}^{\infty})\leq 2k+1$, we have
$\mathsf{hd}(T(i-\ell_{j+1}.\,.i],Q_{j}^{\infty})\leq 3k+1$. Moreover, by
Section 4.2, $i-\ell_{j+1}+\ell_{j}$ is a $k$-mismatch occurrence of $P_{j}$.
3 further implies that $i-\ell_{j+1}+\ell_{j}\equiv p\pmod{|Q_{j}|}$ and
$\mathsf{hd}(T(p-\ell_{j}.\,.i-\ell_{j+1}],Q_{j}^{\infty})\leq 3k$.
Consequently, $\mathsf{hd}(T(p-\ell_{j}.\,.i],Q_{j}^{\infty})\leq 6k+1$, and
thus we compute $\mathsf{MI}(T(i-\ell_{j+1}.\,.i],Q_{j}^{\infty})$ and report
$i$ as a $k$-mismatch occurrence of $P_{j+1}$.

We conclude with the complexity analysis: the working space is $O(k)$,
dominated by the maintained mismatch information. Moreover, whenever we
compute $\mathsf{MI}(T(i-\ell_{j+1}.\,.i],P_{j})$, the size of this set is, by
the triangle inequality, at most $6k+1+2k+1\leq 8k+2$, and it can be computed
in $O(k)$ time.

##### Summary.

Overall, each subroutine of each level takes $O(k)$ space and $O(k)$ time per
character. Since there are $t=O(\log m)$ levels and each level contains at
most two active subroutines, the algorithm takes $O(k\log m)$ space and
$O(k\log m)$ time per text character. Although our pattern preprocessing
algorithm is an offline procedure, we can run it while the algorithm reads the
first $m/2$ characters of the text. Then, while the algorithm reads further
$m/2$ characters, it can process two characters at a time to catch up with the
input stream. This does not result in any delay on the output because the
leftmost $k$-mismatch occurrence of $P$ is at position $m$ or larger.

###  4.3 Read-only algorithm for $k$-LHD-PAL

######  Theorem 4.5.

There is a deterministic online algorithm that solves the $k$-LHD-PAL problem
for a string of length $n$ using $O(k\log n)$ space and $O(k\log n)$ worst-
case time per character.

The algorithm uses a filtering approach to select positions where a prefix
close to PAL can end. Define a family
$\mathcal{P}=\\{P_{j}=T[.\,.\lfloor(3/2)^{j}\rfloor]:j\in[1.\,.\lfloor\log_{3/2}n\rfloor]\\}$
of prefixes of the text, and let $\ell_{j}=|P_{j}|$, setting $\ell_{0}=0$ for
notational convenience.

######  Claim 5.

Consider $j\in[1.\,.\lfloor\log_{3/2}n\rfloor]$ and a position
$i\in(2\ell_{j-1}.\,.2\ell_{j}]$. If $\mathsf{hd}(T[.\,.i],\textsc{PAL})\leq
k$, then $i$ is a $2k$-mismatch occurrence of $P_{j}^{R}$ in $T$. Moreover,
$\mathsf{hd}(T[.\,.i],\textsc{PAL})=\mathsf{hd}(T(i-i^{\prime}.\,.i],P_{j}[1.\,.i^{\prime})^{R})$
for $i^{\prime}=\lfloor i/2\rfloor$.

######  Proof 4.6.

Note that $i>2\ell_{j-1}\geq\ell_{j}$ implies that $P_{j}$ is a prefix of
$T[.\,.i]$ and, equivalently, $P_{j}^{R}$ is a suffix of $T[.\,.i]^{R}$.
Section 2.1 implies
$2\cdot\mathsf{hd}(T[.\,.i],\textsc{PAL})=\mathsf{hd}(T[.\,.i],T[.\,.i]^{R})\geq\mathsf{hd}(T(i-\ell_{j}.\,.i],P_{j})$.
Thus, if $\mathsf{hd}(T[.\,.i],\textsc{PAL})\leq k$, then $i$ is a
$2k$-mismatch occurrence of $P_{j}$ in $T$. Since $T[.\,.i^{\prime}]$ is a
prefix of $P_{j}$, Section 2.1 further implies
$\mathsf{hd}(T[.\,.i],\textsc{PAL})=\mathsf{hd}(T(i-i^{\prime}.\,.i],T[.\,.i^{\prime}]^{R})=\mathsf{hd}(T(i-i^{\prime}.\,.i],P_{j}[1.\,.i^{\prime})^{R})$.

The algorithm constructs the family $\mathcal{P}$ as it reads the text. For
each level $j$, we implement a subroutine responsible for positions
$i\in(2\ell_{j-1}.\,.2\ell_{j}]$. First, while reading
$T[\ell_{j}.\,.2\ell_{j-1})$, we launch the pattern-matching algorithm of
Theorem 4.3 in order to compute the $2k$-mismatch occurrences of $P_{j}^{R}$
in $T_{j}=T[.\,.2\ell_{j})$ and feed the pattern-matching algorithm with the
pattern $P_{j}$ and a prefix $T[.\,.2\ell_{j-1})$ of $T_{j}$, ignoring any
output produced. The total number of characters provided is
$\ell_{j}+2\ell_{j-1}\leq 7\cdot(2\ell_{j-1}-\ell_{j})$, so we can feed the
algorithm with $O(1)$ characters for every scanned character of $T$. Then,
while reading $T[2\ell_{j-1}.\,.2\ell_{j})$, we feed the pattern-matching
algorithm with subsequent characters of $T$. For every reported $2k$-mismatch
occurrence $i$ of $P_{j}^{R}$ in $T_{j}$, we retrieve the mismatch information
$\mathsf{MI}(T(i-\ell_{j}.\,.i],P_{j}^{R})$ and obtain
$\mathsf{MI}(T(i-i^{\prime}.\,.i],P_{j}[.\,.i^{\prime}]^{R})$ by removing the
entries corresponding to the leftmost $\ell_{j}-i^{\prime}$ positions. We
report the size of this set (or $\infty$ if the size exceeds $k$) as
$\mathsf{hd}_{\leq k}(T[.\,.i],\textsc{PAL})$.

By 5, all positions $i\in(2\ell_{j-1}.\,.2\ell_{j}]$ such that
$\mathsf{hd}(T[.\,.i],\textsc{PAL})\leq k$ pass the test and the distance
$\mathsf{hd}(T[.\,.i],\textsc{PAL})$ is equal to the size of the set
$\mathsf{MI}(T(i-i^{\prime}.\,.i],P_{j}[.\,.i^{\prime}]^{R})$. As for the
complexity analysis, observe that, for each level $j$, the pattern-matching
algorithm uses $O(k\cdot j)$ space and takes $O(k\cdot j)$ time per character.
Since, at any time, there is a constant number of active levels, the main
algorithm uses $O(k\log n)$ space and takes $O(k\log n)$ time per character.

###  4.4 Read-only algorithm for $k$-LHD-SQ

######  Theorem 4.7.

There is a deterministic online algorithm that solves the $k$-LHD-SQ problem
for a string $T\in\Sigma^{n}$ using $O(k\log n)$ space and $O(k\log n)$ worst-
case time per character.

Our algorithm is very similar to the pattern-matching algorithm of Theorem
4.3. We use the same sequence $\mathcal{P}=(P_{j})_{j=1}^{t}$ of prefixes, now
defined for $P=T$. Again, we set $\ell_{j}=|P_{j}|$ for $j\in[1.\,.t]$.
Instead of Section 4.2, we use Section 3.2 to argue that our filtering
procedure is correct.

##### Processing $\mathcal{P}$.

We build $\mathcal{P}$ in an online fashion so that the prefix $P_{j}$ is
constructed while scanning $T(\ell_{j}.\,.\lceil 3\ell_{j}/2\rceil]$. If
$P_{j}$ is $k$-mismatch periodic, then we also identify $P_{j+1}$ and build
$\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$.

For subsequent indices $j\in[0.\,.\lfloor{\log_{3/2}n}\rfloor]$, we add the
prefix $R_{j}$ to $\mathcal{P}$ as soon as it has been read. Then, we launch
an offline procedure that applies Corollary 4.2 to test whether $R_{j}$ is
$k$-mismatch periodic and, if so, retrieves the period $Q$. If $R_{j}$ is
$k$-mismatch periodic, we build $\mathsf{MI}(R_{j},Q^{\infty})$ and extend
$R_{j}$ while maintaining the mismatch information with the appropriate prefix
of $Q^{\infty}$. We proceed until we reach length $|R_{j+1}|$ or $2k+1$
mismatches, whichever comes first. We add the obtained extension
$R_{j}^{\prime}$ to $\mathcal{P}$ and store the mismatch information
$\mathsf{MI}(R_{j}^{\prime},Q^{\infty})$. If
$\mathsf{hd}(R_{j}^{\prime},Q^{\infty})\leq 2k$, then $R_{j}^{\prime}=R_{j+1}$
is $k$-mismatch periodic with the same period $Q$. Otherwise, by 2, neither
$R_{j}^{\prime}$ nor $R_{j+1}$ are $k$-mismatch periodic. Processing each $j$
takes $O(|R_{j+1}|k)$ time and $O(k)$ space, and this computation needs to be
completed while the algorithm reads $T(|R_{j}|.\,.|R_{j+1}|]$. This gives
$O(k)$ time per position since
$\lfloor\frac{3}{2}|R_{j}|\rfloor\leq|R_{j+1}|\leq\lceil\frac{3}{2}|R_{j}|\rceil$.

Across all indices $j\in[0.\,.\lfloor{\log_{3/2}n}\rfloor]$, the preprocessing
algorithm takes $O(k)$ space and time per character (since no two indices are
processed simultaneously).

##### Computing the distances.

For each level $j\in[1.\,.t]$, we implement a subroutine responsible for even
positions $i\in[2\ell_{j}.\,.2\ell_{j+1})$; this procedure is active as we
read $T[\ell_{j}.\,.2\ell_{j+1})$. As described above, the pattern $P_{j}$ is
identified while the algorithm reads $T(\ell_{j}.\,.\lceil 3\ell_{j}/2\rceil]$
and, if $P_{j}$ is $k$-mismatch periodic, the period $Q_{j}$ and the mismatch
information $\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$ are also computed at that
time. While reading $T[\lceil 3\ell_{j}/2\rceil.\,.2\ell_{j})$, we launch the
pattern-matching algorithm of Theorem 4.3 to report the $k$-mismatch
occurrences of $P_{j}$ in $T_{j}=T[.\,.\ell_{j}+\ell_{j+1})$ and feed this
algorithm with the pattern $P_{j}$ and the prefix $T[.\,.2\ell_{j})$ of the
text $T_{j}$. The total number of characters provided is $3\ell_{j}\leq
6\cdot\frac{1}{2}\ell_{j}$, so can feed the pattern-matching algorithm with
$O(1)$ character for every scanned character of $T$. Then, while reading
$T[2\ell_{j}.\,.\ell_{j}+\ell_{j+1})$, we feed the pattern-matching algorithm
subsequent text characters. For every
$i^{\prime}\in[2\ell_{j}.\,.\ell_{j}+\ell_{j+1})$, we learn whether
$i^{\prime}$ is a $k$-mismatch occurrence of $P_{j}$ and, if so, we obtain the
mismatch information
$\mathsf{MI}(P_{j},T(i^{\prime}-\ell_{j}.\,.i^{\prime}])$. How we utilise this
output depends on whether $P_{j}$ is $k$-mismatch periodic or not: if $P_{j}$
is not $k$-mismatch periodic, then $T_{j}$ contains $O(k)$ $k$-mismatch
occurrences of $P_{j}$ and storing them explicitly requires little space. When
$P_{j}$ is $k$-mismatch periodic, $T_{j}$ must exhibit similar periodicity,
which we can use to avoid storing all occurrences explicitly.

#####  $P_{j}$ is not $k$-mismatch periodic.

In this case, for every received $k$-mismatch occurrence $i^{\prime}$ of
$P_{j}$, we store the mismatch information
$\mathsf{MI}(T(i^{\prime}-\ell_{j}.\,.i^{\prime}],P_{j})$ and, as the
algorithm receives subsequent characters $T[i]$ for
$i\in(i^{\prime}.\,.2(i^{\prime}-\ell_{j})]$, we maintain
$\mathsf{MI}(T(i^{\prime}-\ell_{j}.\,.i],T[.\,.\ell_{j}+i-i^{\prime}])$ as
long as there are at most $k$ mismatches. If this is still the case for
$i=2(i^{\prime}-\ell_{j})$, we report that $T[.\,.i]$ is a $k$-mismatch
square, with
$\mathsf{hd}(T[.\,.i],\textsc{SQ})=\mathsf{hd}(T(i^{\prime}-\ell_{j}.\,.i],T[.\,.\ell_{j}+i-i^{\prime}])=\mathsf{hd}(T(i/2.\,.i],T[.\,.i/2])$.
By Section 3.2, no $k$-mismatch square $T[.\,.i]$ is missed. Moreover, 3
guarantees that there are $O(k)$ $k$-mismatch occurrences of $P_{j}$, and thus
we use $O(k)$ space and $O(k)$ time per character to process all of them.

#####  $P_{j}$ is $k$-mismatch periodic with period $Q_{j}$.

In this case, we wait for the leftmost $k$-mismatch occurrence
$p\in[2\ell_{j}.\,.\ell_{j}+\ell_{j+1})$ of $P_{j}$ and ignore all the
subsequent occurrences of $P_{j}$. We use the received mismatch information
$\mathsf{MI}(T(p-\ell_{j}.\,.p],P_{j})$ and the preprocessed mismatch
information $\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$ to construct
$\mathsf{MI}(T(p-\ell_{j}.\,.p],Q_{j}^{\infty})$; by the triangle inequality,
the size of this set is guaranteed to be at most $3k$. As the algorithm
receives subsequent characters of $T[i]$ for $i\in(p.\,.2\ell_{j+1})$, we
maintain $\mathsf{MI}(T(p-\ell_{j}.\,.i],Q_{j}^{\infty})$ as long as the
number of mismatches does not exceed $6k+1$. Whenever $i/2\geq p-\ell_{j}$ and
$i/2\equiv p-\ell_{j}\pmod{|Q_{j}|}$, we extract
$\mathsf{MI}(T(i/2.\,.i],Q_{j}^{\infty})$ from
$\mathsf{MI}(T(p-\ell_{j}.\,.i],Q_{j}^{\infty})$ and use the precomputed
mismatch information $\mathsf{MI}(P_{j+1},Q_{j}^{\infty})$ to construct
$\mathsf{MI}(T[.\,.i/2],Q_{j}^{\infty})$ first, and then derive
$\mathsf{MI}(T[.\,.i/2],T(i/2.\,.i])$. If the latter is of size at most $k$,
we report $T[.\,.i]$ as a $k$-mismatch square.

As for the correctness, we argue that we miss no $k$-mismatch square
$T[.\,.i]$ with $i\in(2\ell_{j}.\,.2\ell_{j+1}]$. Since
$\mathsf{hd}(T(i/2.\,.i],T[.\,.i/2])\leq k$ and
$\mathsf{hd}(P_{j+1},Q_{j}^{\infty})\leq 2k+1$, as a corollary we obtain
$\mathsf{hd}(T(i/2.\,.i],Q_{j}^{\infty})\leq 3k+1$. Moreover, by Section 3.2,
$i/2+\ell_{j}$ is a $k$-mismatch occurrence of $P_{j}$. 3 further implies that
$i/2+\ell_{j}\equiv p\pmod{|Q_{j}|}$ and
$\mathsf{hd}(T(p-\ell_{j}.\,.i/2],Q_{j}^{\infty})\leq 3k$. Consequently,
$\mathsf{hd}(T(p-\ell_{j}.\,.i],Q_{j}^{\infty})\leq 6k+1$, and thus we compute
$\mathsf{MI}(T[.\,.i/2],T(i/2.\,.i])$ and report $T[1.\,.i]$ as a $k$-mismatch
square.

We conclude with the complexity analysis: the working space is $O(k)$,
dominated by the maintained mismatch information. Moreover, whenever we
compute $\mathsf{MI}(T[.\,.i/2],T(i/2.\,.i])$, the size of this set is, by the
triangle inequality, at most $6k+1+2k+1\leq 8k+2$, and it can be computed in
$O(k)$ time.

##### Summary.

Overall, each level takes $O(k\log n)$ space and $O(k\log n)$ time per
character, dominated by the pattern-matching algorithm of Theorem 4.3.
However, since constantly many levels are processed at any given time, the
entire algorithm still uses $O(k\log n)$ space and $O(k\log n)$ time per
character.

##  5 Language Edit Distance problems

The _edit distance_ between two strings $U$ and $V$, denoted by
$\mathsf{ed}(U,V)$, is the minimum number of character insertions, deletions,
and substitutions required to transform $U$ into $V$. Similar to the Hamming
distance, the edit distance from a string $U$ to PAL and SQ can be expressed
in terms of self-similarity of $U$. This allows us to use similar approaches
as for the Language Hamming distance problems, with tools for the Hamming
distance replaced with appropriate tools for the edit distance.

By replacing the Hamming distance sketch [12] with the edit distance sketch of
Bhattacharya and Koucký [7].

######  Theorem 5.1.

There is a randomised streaming algorithm that solves the $k$-LED-PAL problem
for a string of length $n$ using $\tilde{O}(k^{2})$ bits of space and
$\tilde{O}(k^{2})$ time per character.

Furthermore, the results of Bhattacharya and Koucký [7] show a reduction from
the edit distance to the Hamming distance via locally consistent string
decompositions, which allows reducing the $k$-LED-SQ problem to $k$-LHD-SQ,
solved via Proposition 3.9:

######  Theorem 5.2.

There is a randomised streaming algorithm that solves the $k$-LED-SQ problem
for a string of length $n$ using $\tilde{O}(k^{2})$ bits of space and
$\tilde{O}(k^{2})$ time per character.

Finally, by replacing the online read-only algorithm for finding the
$k$-mismatch occurrences of a pattern in a text with an online read-only
algorithm for finding $k$-error occurrences and the structural results for the
Hamming distance with the structural results for the edit distance, we obtain
algorithms for $k$-LED-PAL and $k$-LED-SQ:

######  Theorem 5.3.

There is a deterministic online read-only algorithm that solves the $k$-LED-
PAL problem for a string of length $n$ using $\tilde{O}(k^{4})$ bits of space
and $\tilde{O}(k^{4})$ time per character.

######  Theorem 5.4.

There is a deterministic online read-only algorithm that solves the $k$-LED-SQ
problem for a string of length $n$ using $\tilde{O}(k^{4})$ bits of space and
$\tilde{O}(k^{4})$ amortised time per character.

## References

  * [1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams.  If the Current Clique Algorithms Are Optimal, so Is Valiant’s Parser.  SIAM Journal on Computing, 47(6):2527–2555, 2018.  doi:10.1137/16M1061771.
  * [2] Alfred V. Aho and Thomas G. Peterson.  A minimum distance error-correcting parser for context-free languages.  SIAM Journal on Computing, 1(4):305–312, 1972.  doi:10.1137/0201022.
  * [3] Amihood Amir and Benny Porat.  Approximate on-line palindrome recognition, and applications.  In Proc. of CPM 2014, volume 8486 of LNCS, pages 21–29. Springer, 2014.  doi:10.1007/978-3-319-07566-2_3.
  * [4] Arturs Backurs and Krzysztof Onak.  Fast algorithms for parsing sequences of parentheses with few errors.  In Proc. of PODS 2016, pages 477–488. ACM, 2016.  doi:10.1145/2902251.2902304.
  * [5] Djamal Belazzougui and Mathieu Raffinot.  Approximate regular expression matching with multi-strings.  Journal of Discrete Algorithms, 18:14–21, 2013.  doi:10.1016/j.jda.2012.07.008.
  * [6] Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, and Erfan Sadeqi Azer.  Palindrome recognition in the streaming model.  In Proc. of STACS, volume 25, pages 149–161, 2014.  doi:10.4230/LIPIcs.STACS.2014.149.
  * [7] Sudatta Bhattacharya and Michal Koucký.  Locally consistent decomposition of strings with applications to edit distance sketching.  In Proc. of 55th STOC, pages 219–232. ACM, 2023.  doi:10.1145/3564246.3585239.
  * [8] Sudatta Bhattacharya and Michal Koucký.  Streaming k-Edit Approximate Pattern Matching via String Decomposition.  In Proc. of 50th ICALP, volume 261 of LIPIcs, pages 22:1–22:14, 2023.  URL: https://drops.dagstuhl.de/opus/volltexte/2023/18074, doi:10.4230/LIPIcs.ICALP.2023.22.
  * [9] Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams.  Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product.  SIAM Journal on Computing, 48(2):481–512, 2019.  doi:10.1137/17M112720X.
  * [10] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz.  Faster approximate pattern matching: A unified approach.  In Proc. of 61st FOCS, pages 978–989. IEEE, 2020.  doi:10.1109/FOCS46700.2020.00095.
  * [11] Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang.  Faster min-plus product for monotone instances.  In Proc. of 54th STOC, pages 1529–1542. ACM, 2022.  doi:10.1145/3519935.3520057.
  * [12] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat.  The streaming $k$-mismatch problem.  In Proc. of SODA 2019, pages 1106–1125. SIAM, 2019.  doi:10.1137/1.9781611975482.68.
  * [13] Debarati Das, Tomasz Kociumaka, and Barna Saha.  Improved approximation algorithms for Dyck edit distance and RNA folding.  In Proc. of ICALP 2022, volume 229 of LIPIcs, pages 49:1–49:20, 2022.  doi:10.4230/LIPIcs.ICALP.2022.49.
  * [14] Anita Dürr.  Improved bounds for rectangular monotone Min-Plus Product and applications.  Information Processing Letters, 181:106358, 2023.  doi:https://doi.org/10.1016/j.ipl.2023.106358.
  * [15] Nathan J. Fine and Herbert S. Wilf.  Uniqueness theorems for periodic functions.  Proceedings of the American Mathematical Society, 16(1):109–114, 1965.  doi:10.1090/S0002-9939-1965-0174934-9.
  * [16] Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, and Tatiana Starikovskaya.  An improved algorithm for the $k$-Dyck edit distance problem.  In Proc. of SODA 2022, pages 3650–3669. SIAM, 2022.  doi:10.1137/1.9781611977073.144.
  * [17] Zvi Galil.  Real-time algorithms for string-matching and palindrome recognition.  In Proc. of STOC, pages 161–173. ACM, 1976.  doi:10.1145/800113.803644.
  * [18] Zvi Galil and Raffaele Giancarlo.  Improved string matching with $k$ mismatches.  ACM SIGACT News, 17(4):52–54, 1986.  doi:10.1145/8307.8309.
  * [19] Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, and Barna Saha.  How compression and approximation affect efficiency in string distance measures.  In Proc. of SODA 2022, pages 2867–2919. SIAM, 2022.  doi:10.1137/1.9781611977073.112.
  * [20] Pawel Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemyslaw Uznanski.  Tight tradeoffs for real-time approximation of longest palindromes in streams.  Algorithmica, 81(9):3630–3654, 2019.  doi:10.1007/s00453-019-00591-8.
  * [21] Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu.  The communication complexity of the Hamming distance problem.  Information Processing Letters, 99(4):149–153, 2006.
  * [22] Tomasz Kociumaka, Ely Porat, and Tatiana Starikovskaya.  Small-space and streaming pattern matching with $k$ edits.  In Proc. of FOCS 2021, pages 885–896. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00090.
  * [23] Roman Kolpakov and Gregory Kucherov.  Finding approximate repetitions under Hamming distance.  Theoretical Computer Science, 303(1):135–156, 2003.  Logic and Complexity in Computer Science.  doi:https://doi.org/10.1016/S0304-3975(02)00448-6.
  * [24] Michal Koucký and Michael E. Saks.  Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.  In Proc. of SODA 2023, pages 5203–5219. SIAM, 2023.  doi:10.1137/1.9781611977554.ch188.
  * [25] Andreas Krebs, Nutan Limaye, and Srikanth Srinivasan.  Streaming algorithms for recognizing nearly well-parenthesized expressions.  In Proc. of MFCS 2011, volume 6907 of LNCS, pages 412–423. Springer, 2011.  doi:10.1007/978-3-642-22993-0_38.
  * [26] Gad M. Landau and Jeanette P. Schmidt.  An algorithm for approximate tandem repeats.  In Proc. of CPM, pages 120–133, 1993.  doi:10.1007/BFb0029801.
  * [27] Gad M. Landau and Uzi Vishkin.  Fast string matching with $k$ differences.  Journal of Computer and System Sciences, 37(1):63–78, 1988.  doi:10.1016/0022-0000(88)90045-1.
  * [28] Lillian Lee.  Fast context-free grammar parsing requires fast Boolean matrix multiplication.  Journal of the ACM, 49(1):1–15, January 2002.  doi:10.1145/505241.505242.
  * [29] Oleg Merkurev and Arseny M. Shur.  Computing the maximum exponent in a stream.  Algorithmica, 84(3):742–756, 2022.  doi:10.1007/s00453-021-00883-y.
  * [30] Gene Myers.  Approximately matching context-free languages.  Information Processing Letters, 54(2):85–92, 1995.  doi:10.1016/0020-0190(95)00007-y.
  * [31] Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Fully dynamic data structure for LCE queries in compressed space.  In Proc. of MFCS 2016, volume 58 of LIPIcs, pages 72:1–72:15, 2016.  doi:10.4230/LIPIcs.MFCS.2016.72.
  * [32] Alexandre H. L. Porto and Valmir Carneiro Barbosa.  Finding approximate palindromes in strings.  Pattern Recognit., 35(11):2581–2591, 2002.  doi:10.1016/S0031-3203(01)00179-0.
  * [33] Walter L. Ruzzo.  On the complexity of general context-free language parsing and recognition.  In Proc. of ICALP 1979, volume 71 of LNCS, pages 489–497. Springer, 1979.  doi:10.1007/3-540-09510-1_39.
  * [34] Wojciech Rytter.  On maximal suffixes and constant-space linear-time versions of KMP algorithm.  Theoretical Computer Science, 299(1-3):763–774, 2003.  doi:10.1016/S0304-3975(02)00590-X.
  * [35] Barna Saha.  The Dyck language edit distance problem in near-linear time.  In Proc. of FOCS 2014, pages 611–620. IEEE Computer Society, 2014.  doi:10.1109/FOCS.2014.71.
  * [36] Barna Saha.  Language edit distance and maximum likelihood parsing of stochastic grammars: Faster algorithms and connection to fundamental graph problems.  In Proc. of FOCS 2015, pages 118–135. IEEE Computer Society, 2015.  doi:10.1109/FOCS.2015.17.
  * [37] Barna Saha.  Fast space-efficient approximations of language edit distance and RNA folding: An amnesic dynamic programming approach.  In Proc. of FOCS 2017, pages 295–306. IEEE Computer Society, 2017.  doi:10.1109/FOCS.2017.35.
  * [38] Giorgio Satta.  Tree-adjoining grammar parsing and boolean matrix multiplication.  Comput. Linguistics, 20(2):173–191, 1994.  URL: https://aclanthology.org/J94-2002.
  * [39] Dina Sokol, Gary Benson, and Justin Tojeira.  Tandem repeats over the edit distance.  Bioinformatics, 23(2):e30–e35, 01 2007.  doi:10.1093/bioinformatics/btl309.
  * [40] Dina Sokol and Justin Tojeira.  Speeding up the detection of tandem repeats over the edit distance.  Theoretical Computer Science, 525:103–110, 2014.  Advances in Stringology.  doi:https://doi.org/10.1016/j.tcs.2013.04.021.
  * [41] Esko Ukkonen.  On approximate string matching.  In Proc. of FCT 1983, volume 158 of LNCS, pages 487–495. Springer, 1983.  doi:10.1007/3-540-12689-9_129.

##  Appendix A Edit distance, palindromes, and squares

The _edit distance_ between two strings $U$ and $V$, denoted by
$\mathsf{ed}(U,V)$, is the minimum number of character insertions, deletions,
and substitutions required to transform $U$ into $V$. For a formal definition,
we first rely on the notion of an _alignment_ between fragments of strings.

######  Definition A.1 ([22]).

A sequence $\mathcal{A}=(u_{t},v_{t})_{i=0}^{m}$ is an _alignment_ of $U$ onto
$V$ if $(u_{0},v_{0})=(0,0)$,
$(u_{t},v_{t})\in\\{(u_{t-1}+1,v_{t-1}+1),(u_{t-1}+1,v_{t-1}),(u_{t-1},v_{t-1}+1)\\}$
for $i\in[1.\,.m]$, and $(u_{m},v_{m})=(|U|,|V|)$.

  * •

If $(u_{t},v_{t})=(u_{t-1}+1,v_{t-1})$, we say that $\mathcal{A}$ _deletes_
$U[u_{t}]$,

  * •

If $(u_{t},v_{t})=(u_{t-1},v_{t-1}+1)$, we say that $\mathcal{A}$ _inserts_
$V[v_{t}]$,

  * •

If $(u_{t},v_{t})=(u_{t-1}+1,v_{t-1}+1)$, we say that $\mathcal{A}$ _aligns_
$U[u_{t}]$ and $V[v_{t}]$. If additionally $U[u_{t}]=V[v_{t}]$, we say that
$\mathcal{A}$ _matches_ $U[u_{t}]$ and $V[v_{t}]$; otherwise, $\mathcal{A}$
_substitutes_ $V[v_{t}]$ for $U[u_{t}]$.

The _cost_ of an alignment $\mathcal{A}$ of $U$ onto $V$, is the total number
of characters that $\mathcal{A}$ inserts, deletes, or substitutes. Now, we
define the edit distance $\mathsf{ed}(U,V)$ as the minimum cost of an
alignment of $U$ onto $V$. An alignment of $U$ onto $V$ is _optimal_ if its
cost is equal to $\mathsf{ed}(U,V)$.

A sequence of edits that an alignment $\mathcal{A}$ uses to transform $U$ into
$V$ (specifying the involved positions and characters) is called an _edit
sequence_ (of the alignment).

######  Example A.2.

A string $U=\mathtt{ababc}$ can be transformed onto $V=\mathtt{bbac}$ by
substituting $U[1]=\mathtt{a}$ for $V[1]=\mathtt{b}$ and deleting
$U[4]=\mathtt{b}$. The corresponding alignment is $(0,0)$, $(1,1)$, $(2,2)$,
$(3,3)$, $(4,3)$, $(5,4)$.

For an integer $k$, we denote

$\mathsf{ed}_{\leq k}(X,Y)=\begin{cases}\mathsf{ed}(X,Y)&\text{if
}\mathsf{ed}(X,Y)\leq k,\\\ \infty&\text{otherwise.}\end{cases}$

For strings $P,T\in\Sigma^{\ast}$, we say that a position $i$ is a $k$-error
occurrence of $P$ in $T$ if $\mathsf{ed}(T(j.\,.i],P)\leq k$ for some
$j\in[1.\,.i]$.

Similarly to the Hamming distance, we can measure the edit distance from a
string $U$ to PAL and SQ in terms of the self-similarity of $U$.

######  Property A.3.

For any string $U\in\Sigma^{*}$, we have

$\mathsf{ed}(U,\textsc{PAL})=\min_{i}\\{\min\\{\mathsf{ed}(U[.\,.i],U[i+1.\,.]^{R}),\mathsf{ed}(U[.\,.i],U[i+2.\,.]^{R})\\}\\}=\tfrac{1}{2}\mathsf{ed}(U,U^{R}).$

######  Proof A.4.

First, consider an optimum alignment $(u_{t},u^{\prime}_{t})_{t=0}^{m}$ of $U$
onto $U^{R}$. For every $t\in[0.\,.m]$, the alignment maps $U[.\,.u_{t}]$ onto
$U^{R}[.\,.u^{\prime}_{t}]$ and $U(u_{t}.\,.]$ onto
$U^{R}(u^{\prime}_{t}.\,.]$. In particular,

$\mathsf{ed}(U,U^{R})=\mathsf{ed}(U[.\,.u_{t}],U^{R}[.\,.u^{\prime}_{t}])+\mathsf{ed}(U(u_{t}.\,.],U^{R}(u^{\prime}_{t}.\,.]).$

Suppose that there exists an index $t\in[0.\,.m]$ such that
$u_{t}+u^{\prime}_{t}=|U|$. In this case,
$U^{R}[.\,.u^{\prime}_{t}]=U(u_{t}.\,.]^{R}$ and
$U^{R}(u^{\prime}_{t}.\,.]=U[.\,.u_{t}]^{R}$. Consequently,

$\displaystyle\mathsf{ed}(U,U^{R})$
$\displaystyle=\mathsf{ed}(U[.\,.u_{t}],U^{R}[ddu^{\prime}_{t}])+\mathsf{ed}(U(u_{t}.\,.],U^{R}(u^{\prime}_{t}.\,.])$
$\displaystyle=\mathsf{ed}(U[.\,.u_{t}],U(u_{t}.\,.]^{R})+\mathsf{ed}(U(u_{t}.\,.],U[.\,.u_{t}]^{R})$
$\displaystyle=2\cdot\mathsf{ed}(U[.\,.u_{t}],U(u_{t}.\,.]^{R}),$

that is, $\mathsf{ed}(U,U^{R})=\mathsf{ed}(U[.\,.i],U[i+1.\,.]^{R})$ holds for
$i=u_{t}$.

Otherwise, as the sequence $(u_{t}+u^{\prime}_{t})_{t=0}^{m}$ increases from
$0$ to $2|U|$, there exists $t\in[1.\,.m]$ such that
$u_{t-1}+u^{\prime}_{t-1}<|U|<u_{t}+u^{\prime}_{t}$. In particular,
$(u_{t},u^{\prime}_{t})=(u_{t-1}+1,u^{\prime}_{t-1}+1)$, so
$U^{R}[.\,.u^{\prime}_{t-1}]=U(u_{t}.\,.]^{R}$,
$U^{R}(u^{\prime}_{t-1}.\,.u^{\prime}_{t}]=U(u_{t-1}.\,.u_{t}]$, and
$U^{R}(u^{\prime}_{t}.\,.]=U[.\,.u_{t-1}]$. Consequently,

$\displaystyle\mathsf{ed}(U,U^{R})$
$\displaystyle=\mathsf{ed}(U[.\,.u_{t-1}],U^{R}[.\,.u^{\prime}_{t-1}])+\mathsf{ed}(U(u_{t-1}.\,.u_{t}],U^{R}(u^{\prime}_{t-1}.\,.u^{\prime}_{t}])+\mathsf{ed}(U(u_{t}.\,.],U^{R}(u^{\prime}_{t}.\,.])$
$\displaystyle=\mathsf{ed}(U[.\,.u_{t-1}],U(u_{t}.\,.]^{R})+\mathsf{ed}(U(u_{t-1}.\,.u_{t}],U(u_{t-1}.\,.u_{t}]^{R})+\mathsf{ed}(U(u_{t}.\,.],U[.\,.u_{t-1}]^{R})$
$\displaystyle=2\cdot\mathsf{ed}(U[.\,.u_{t-1}],U(u_{t}.\,.]^{R}),$

that is, $\mathsf{ed}(U,U^{R})=\mathsf{ed}(U[.\,.i],U[i+2.\,.]^{R})$ holds for
$i=u_{t-1}=u_{t}-1$.

This completes the proof that

$2\min_{i}\\{\min\\{\mathsf{ed}(U[.\,.i],U[i+1.\,.]^{R}),\mathsf{ed}(U[.\,.i],U[i+2.\,.]^{R})\\}\\}\leq\mathsf{ed}(U,U^{R}).$
(1)

Next, consider a palindrome $V$ such that
$\mathsf{ed}(U,\textsc{PAL})=\mathsf{ed}(U,V)$. The triangle inequality
implies

$\mathsf{ed}(U,U^{R})\leq\mathsf{ed}(U,V)+\mathsf{ed}(V,U^{R})=\mathsf{ed}(U,V)+\mathsf{ed}(V^{R},U^{R})=2\mathsf{ed}(U,V)=2\mathsf{ed}(U,\textsc{PAL}).$
(2)

Finally, consider an index $i\in[0.\,.|U|]$ and note that

$\mathsf{ed}(U,\textsc{PAL})\leq\mathsf{ed}(U,U[i+1.\,.]^{R}\cdot
U[i+1.\,.])\leq\mathsf{ed}(U[i+1.\,.]^{R},U[.\,.i]).$

Similarly, if $i\in[0.\,.|U|)$, then

$\mathsf{ed}(U,\textsc{PAL})\leq\mathsf{ed}(U,U[i+2.\,.]^{R}\cdot U[i+1]\cdot
U[i+2.\,.])\leq\mathsf{ed}(U[i+2.\,.]^{R},U[.\,.i]).$

Consequently,

$\mathsf{ed}(U,\textsc{PAL})\leq\min_{i}\\{\min\\{\mathsf{ed}(U[.\,.i],U[i+1.\,.]^{R}),\mathsf{ed}(U[.\,.i],U[i+2.\,.]^{R})\\}\\}.$
(3)

Combining (1), (2), and (3) yields the result.

######  Corollary A.5.

Let $U$ be a string of length $n$ and $m=\lfloor{n/2\rfloor}$. We have

$\mathsf{ed}_{\leq
k}(U,\textsc{PAL})=\min_{i\in[m-k.\,.m+k]}\\{\min\\{\mathsf{ed}_{\leq
k}(U[.\,.i],U[i+1.\,.]^{R}),\mathsf{ed}_{\leq k}(U[.\,.i],U[i+2.\,.]^{R})\\}$

######  Proof A.6.

The edit distance between two strings is at least the difference of their
lengths, hence we only need to consider strings that differ by at most $k$ in
length.

######  Property A.7.

Let $U\in\Sigma^{n}$. We have
$\mathsf{ed}(U,\textsc{SQ})=\min_{i}\\{\mathsf{ed}(U[.\,.i],U[i+1.\,.])\\}$.

######  Proof A.8.

First, for any $i\in[1.\,.n]$, we have
$\mathsf{ed}(U,\textsc{SQ})\leq\mathsf{ed}(U[.\,.i],U[i+1.\,.])$, as editing
the substring of $U$ equal to $U[.\,.i]$ into $U[i+1.\,.]$ yields the string
$U[i+1.\,.]U[i+1.\,.]$, which is a square. Now, let $V^{2}$ be a square such
that $\mathsf{ed}(U,\textsc{SQ})=\mathsf{ed}(U,V^{2})$. Let $r$ be the
position of the rightmost character of $U$ that was not deleted, and whose
position in $V^{2}$ (after applying the edits) is at most $|V|$. If it is not
defined, we put $r=0$. We then have
$\mathsf{ed}(U,V^{2})=\mathsf{ed}(U[.\,.r],V)+\mathsf{ed}(U[r+1.\,.],V)$.
Applying the triangle inequality, we obtain
$\mathsf{ed}(U,\textsc{SQ})=\mathsf{ed}(U,V^{2})\geq\mathsf{ed}(U[.\,.r],U[r+1.\,.])$,
hence
$\mathsf{ed}(U,\textsc{SQ})\geq\min_{i\in[1.\,.n]}\\{\mathsf{ed}(U[.\,.i],U[i+1.\,.])\\}$.

######  Corollary A.9.

If $U\in\Sigma^{n}$, then

$\mathsf{ed}_{\leq k}(U,\textsc{SQ})=\min_{i\in[\lfloor
n/2\rfloor-k.\,.\lfloor n/2\rfloor+k]}\min\mathsf{ed}_{\leq
k}(U[.\,.i],U(i.\,.]).$

##  Appendix B Streaming algorithms for the LED problems

In this section, we present streaming algorithms for $k$-LED-PAL and $k$-LED-
SQ.

###  B.1 Locally consistent decompositions and sketches

Our algorithms use locally consistent string decompositions and edit distance
sketches of Bhattacharya and Koucký [7, 8].

##### Locally consistent string decompositions.

The randomised decomposition algorithm of Bhattacharya and Koucký [7] receives
two integers $k,n$ as input and starts by selecting two families of hash
functions of size $\lambda=O(\log n)$.333In [7], $\lambda$ is denoted by $L$,
$\tau$ by $T$, and $\mu$ by $M$. We changed the notation to avoid collisions.
Then, when it receives a string $U$ of length at most $n$ as input, the
algorithm outputs a sequence $\mathbf{G}(U)$ of context-free grammars
$\mathbf{G}(U)=G_{1}^{U}\cdots G_{s}^{U}$ with certain properties, called run-
length straight-line programs or RLSLP for short (the exact definition of an
RLSLP is not important for this work; an interested reader can refer to [31]).
We denote the length of the sequence $s$ by $|\mathbf{G}(U)|$ and extend the
notations for indexing and concatenating strings (e.g., sequences of
characters) to sequences of grammars in a natural way. Each grammar
$\mathbf{G}(U)[i]$ output by the algorithm represents a _unique_ string,
denoted by $\mathsf{eval}(\mathbf{G}(U)[i])$. We extend $\mathsf{eval}$ into a
morphism over grammar sequences: for grammars $G_{1},\ldots,G_{s}$ let
$\mathsf{eval}(G_{1}\cdots G_{s})=\mathsf{eval}(G)\cdots\mathsf{eval}(G_{s})$.

The decomposition satisfies the following properties:

######  Fact 6 ([7, Theorem 3.1]).

Let $U,V$ be a pair of strings of length at most $n$ such that
$\mathsf{ed}(U,V)\leq k$. Let $\mathbf{G}(U)$ and $\mathbf{G}(V)$ be the
sequences of grammars output by the decomposition algorithm on inputs $U$ and
$V$ respectively using the same choice of random hash functions. The following
is true for $n$ large enough:

  1. (a)

With probability at least $1-2/n$, $U=\mathsf{eval}(\mathbf{G}(U))$ and
$V=\mathsf{eval}(\mathbf{G}(V))$ ;

  2. (b)

With probability at least $1-2/\sqrt{n}$, for all $i,j$ the grammars
$\mathbf{G}(U)[i]$ and $\mathbf{G}(V)[j]$ have size $\tilde{O}(k)$;

  3. (c)

With probability at least $0.9$, $|\mathbf{G}(U)|=|\mathbf{G}(V)|$,
$\mathbf{G}(V)[i]=\mathbf{G}(V)[i]$ for every $1\leq i\leq\mathbf{G}(U)$
except at most $k$ of them, and
$\mathsf{ed}(U,V)=\sum_{i=1}^{s}\mathsf{ed}(\mathsf{eval}(\mathbf{G}(V)[i]),\mathsf{eval}(\mathbf{G}(U)[i]))$.

The decomposition can be updated efficiently upon appending or prepending a
character to a string. Let $\tau=O(\log n\log^{*}n)$ be a parameter defined as
in [7]. (See Footnote 3). While it may happen that $\mathbf{G}(UV)$ is shorter
than $\mathbf{G}(U)$, these decompositions are related as follows:

######  Corollary B.1 (Of [7, Lemmas 4.1, 4.2]).

Consider $U,V\in\Sigma^{*}$ such that $|U|+|V|\leq n$. Let $G=\mathbf{G}(U)$,
$G^{\prime}=\mathbf{G}(UV)$, $G^{\prime\prime}=\mathbf{G}(VU)$, and $s=|G|$,
$s^{\prime}=|G^{\prime}|$, $s^{\prime\prime}=|G^{\prime\prime}|$. We have:

  1. 1.

$G[.\,.s-\tau]=G^{\prime}[.\,.s-\tau]$ and
$G(\tau.\,.]=G^{\prime}(s^{\prime}-s+\tau.\,.)$,

  2. 2.

$|U|\leq|\mathsf{eval}(G^{\prime}[.\,.\min\\{s+\tau,s^{\prime}\\}])|$ and
$|U|\leq|\mathsf{eval}(G^{\prime\prime}(\max\\{s^{\prime\prime}-s-\tau,0\\}.\,.])|$.

In particular, this result implies that if the index of a grammar in
$\mathbf{G}(U)$ is less than $|\mathbf{G}(U)|-\tau$ (resp. more than $\tau$),
then appending (resp. prepending) characters to $U$ will not change that
grammar. Extending the terminology [7], we call a grammar that remains
unchanged when appending (resp. prepending) any string a right-committed
grammar (resp. left-committed grammar), while the others are right-active
(resp. left-active) grammars. When a grammar is both left- and right-
committed, we simply say that it is _committed_. In what follows, we use
$\alpha_{r}(\mathbf{G}(U))$ (resp. $\alpha_{l}(\mathbf{G}(U))$) to denote the
number of right-active (resp. left-active) grammars in $\mathbf{G}(U)$.
Corollary B.1 implies that
$\alpha_{l}(\mathbf{G}(U)),\alpha_{r}(\mathbf{G}(U))\leq\tau$.

Theorem 5.1 in [7] presents an algorithm only for the case of appending a
character, essentially the same can be used to prepend one:

######  Corollary B.2 (Of [7, Theorem 5.1]).

Let $U\in\Sigma^{\leq n-1}$, $G=\mathbf{G}(U)$, and $s=|G|$. There are two
algorithms AppendCharacter and PrependCharacter that run in $\tilde{O}(k)$
time and:

  1. 1.

Given a character $a\in\Sigma$ and $G[\max(1,s-\tau).\,.s]$, the algorithm
AppendCharacter outputs $G^{\prime}$ such that
$\mathbf{G}(Ua)=G[1.\,.\max(1,s-\tau))G^{\prime}$ and $|G^{\prime}|\leq
4\tau\lambda$.

  2. 2.

Given a character $a\in\Sigma$ and $G[1.\,.\min\\{\tau+1,s\\}]$, the algorithm
PrependCharacter outputs $G^{\prime}$ such that
$\mathbf{G}(aU)=G^{\prime}\cdot G(\min\\{\tau+1,s\\}.\,.s]$ and
$|G^{\prime}|\leq 4\tau\lambda$.

It follows from the above two results that, by storing the last
$\alpha_{r}(\mathbf{G}(U))+\tau$ (resp. first
$\alpha_{l}(\mathbf{G}(U))+\tau$) grammars of $\mathbf{G}(U)$, we can compute
the last $\alpha_{r}(\mathbf{G}(UV))+\tau$ grammars of $\mathbf{G}(UV)$ (resp.
first $\alpha_{l}(\mathbf{G}(VU))+\tau$ grammars of $\mathbf{G}(VU)$) by
applying the algorithm of Corollary B.2 $|V|$ times. These grammars include
the right-active grammars of $\mathbf{G}(UV)$ (resp. left-active grammars of
$\mathbf{G}(VU)$).

##### Edit distance sketches.

Our algorithms exploit an extension of the edit distance sketches of
Bhattacharya and Koucký [7].

######  Fact 7 ([7, Lemma 3.13]).

Let $\mu=\tilde{O}(k)$ be a parameter. (See Footnote 3). There is a mapping
$\mathsf{enc}$ from the set of grammars output by the decomposition algorithm
to the set of strings of length $\mu$ on a polynomial size that guarantees
that the following is satisfied:

  1. 1.

An grammar can be encoded and decoded in $O(\mu)$ time;

  2. 2.

Encodings of two equal grammars are equal;

  3. 3.

Encodings of two distinct grammars output by the decomposition algorithm
differ in all $\mu$ characters with probability at least $1-2\mu/n$.

We extend this encoding to a sequence of grammars: $\mathsf{enc}(G_{1}\cdots
G_{s})=\mathsf{enc}(G_{1})\cdots\mathsf{enc}(G_{s})$.

######  Lemma B.3.

There is an edit distance sketch $\mathsf{sk}^{\mathsf{ed}}_{k}$ that uses
$\tilde{O}(k^{2})$ bits of space, and supports the following operations
assuming that all involved strings have length at most $n$:

  1. (a)

Append: given $\mathsf{sk}^{\mathsf{ed}}_{k}(U)$ and a character $a\in\Sigma$,
compute $\mathsf{sk}^{\mathsf{ed}}_{k}(Ua)$,

  2. (b)

Prepend: given $\mathsf{sk}^{\mathsf{ed}}_{k}(U)$ and a character
$a\in\Sigma$, compute $\mathsf{sk}^{\mathsf{ed}}_{k}(aU)$,

  3. (c)

Distance: given $\mathsf{sk}^{\mathsf{ed}}_{k}(U)$ and
$\mathsf{sk}^{\mathsf{ed}}_{k}(V)$, compute $\mathsf{ed}_{\leq k}(U,V)$.

All three operations take $\tilde{O}(k^{2})$ time and space and errs with
probability inverse polynomial in $n$.

######  Proof B.4.

Let $\mathbf{G}(U)$ be the locally consistent decomposition of a string $U$.
In what follows, we denote $\alpha_{r}=\alpha_{r}(\mathbf{G}(U))$ and
$\alpha_{l}=\alpha_{l}(\mathbf{G}(U))$. If $s=|\mathbf{G}(U)|\leq 4\tau$,
$\mathsf{sk}^{\mathsf{ed}}_{k}(U)=\mathsf{enc}(\mathbf{G}(U))$ and takes
$\tilde{O}(k)$ space. Otherwise, $\mathsf{sk}^{\mathsf{ed}}_{k}(U)$ is defined
as a tuple

$(\mathbf{G}_{l},\mathcal{S},\mathbf{G}_{r})=\left(\mathbf{G}(U)[1.\,.s_{l}],\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(\mathbf{G}(U)(s_{l}.\,.s-s_{r}])),\mathbf{G}(U)(s-s_{r}.\,.s]\right),$

where $s_{l}$ and $s_{r}$ are integers satisfying the invariant

$2\tau\geq s_{l}\geq\alpha_{l}+\tau\text{ and }2\tau\geq
s_{r}\geq\alpha_{r}+\tau.$ (4)

Note that this definition does not define $\mathsf{sk}^{\mathsf{ed}}_{k}(U)$
uniquely (as there are multiple possible choices of $s_{l}$ and $s_{r}$), but
the invariant of Equation 4 ensures that we can always perform updates and
distance operations using the sketch. Initially (i.e., the first time $s$
becomes larger than $4\tau$), we set $s_{l}=s_{r}=2\tau$, which satisfy the
invariant of Equation 4 by Corollary B.1.

Update operations. Let $(\mathbf{G}_{r},\mathcal{S},\mathbf{G}_{r})$ be the
sketch of $U$, $s_{l}=|\mathbf{G}_{l}|$ and $s_{r}=|\mathbf{G}_{r}|$. Given a
character $a\in\Sigma$, we obtain the sketch of $Ua$ feeding
$(\mathbf{G}_{r}[s_{r}-\tau.\,.s_{r}],a)$ into the algorithm AppendCharacter
(Corollary B.2). Let $G_{out}$ be the sequence of grammars output by this
algorithm and let $G^{\prime}=\mathbf{G}_{r}[.\,.s_{r}-\tau)G_{out}$ be the
sequence of grammars obtained by replacing
$\mathbf{G}_{r}[s_{r}-\tau.\,.s_{r}]$ with $G_{out}$ in $\mathbf{G}_{r}$. If
$|G^{\prime}|\leq 2\tau$, we output $(\mathbf{G}_{l},\mathcal{S},G^{\prime})$
for the sketch of $Ua$. Otherwise, we only store explicitly the last $2\tau$
grammars of $G^{\prime}$, and add the others at the end of the Hamming sketch
$\mathcal{S}$. More formally, we construct the Hamming distance sketch
$\mathcal{S}^{\prime}$ by concatenating $\mathcal{S}$ and
$\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(G^{\prime}[.\,.|G^{\prime}|-2\tau]))$.
We then output
$\mathsf{sk}^{\mathsf{ed}}_{k}(Ua)=(\mathbf{G}_{l},\mathcal{S}^{\prime},G^{\prime}(|G^{\prime}|-2\tau.\,.])$.
By Corollary B.2, $|G^{\prime}|\leq 4\tau\lambda+\tau=\tilde{O}(1)$, hence we
can build $\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}())$ in time
$\tilde{O}(k^{2})$ using Section 3, and the subsequent sketch concatenation
also takes $\tilde{O}(k^{2})$ time. In both cases, Corollary B.1 ensures that
the invariant of Equation 4 is satisfied.

Prepending a character works similarly using $\mathbf{G}_{l}$ and the
PrependCharacter algorithm of Corollary B.2.

Distance operation. Let $U,V$ be strings satisfying the conditions of 6, and
consider the sketches
$\mathsf{sk}^{\mathsf{ed}}_{k}(U)=(\mathbf{G}_{l},\mathcal{S},\mathbf{G}_{r})$
and
$\mathsf{sk}^{\mathsf{ed}}_{k}(V)=(\mathbf{G}_{l}^{\prime},\mathcal{S}^{\prime},\mathbf{G}_{r}^{\prime})$
obtained from decompositions such that the properties of 6 hold. By 6(c), at
most $k$ grammars of the decompositions of $U$ and $V$ differ: we can recover
them from the Hamming sketches of $\mathbf{G}(U)$ and $\mathbf{G}(V)$. We can
obtain $\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(\mathbf{G}(U)))$
sketches by concatenating
$\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(\mathbf{G}_{l}))$,
$\mathcal{S}$ and
$\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(\mathbf{G}_{r}))$, which
takes $\tilde{O}(k^{2})$ time (and similarly to obtain
$\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(\mathbf{G}(V)))$). Notice
that the above operation results in
$\mathsf{sk}^{\mathsf{hd}}_{k\cdot\mu}(\mathsf{enc}(\mathbf{G}(U)))$
regardless of the length of $|\mathbf{G}_{l}|$ and $|\mathbf{G}_{r}|$: this
normalization helps us avoid issues related to the definition of the sketches.
Using these sketches, we can recover $\mathsf{enc}(G_{i})$ for every $i$ such
that $\mathbf{G}(U)[i]\neq\mathbf{G}(V)[i]$. We can then compute the edit
distance between $U$ and $V$ using 6(c):

$\displaystyle\mathsf{ed}(U,V)$ $\displaystyle=$
$\displaystyle=\sum_{i=1}^{s}\mathsf{ed}(\mathsf{eval}(\mathbf{G}(U)[i]),\mathsf{eval}(\mathbf{G}(V)[i]))$
$\displaystyle=\sum_{i:\mathbf{G}(U)[i]\neq\mathbf{G}(V)[i]}\mathsf{ed}(\mathsf{eval}(\mathbf{G}(U)[i]),\mathsf{eval}(\mathbf{G}(V)[i]))$

Given two RLSLPs $G,G^{\prime}$ of size at most $m$ and
$d=\mathsf{ed}(\mathsf{eval}(G),\mathsf{eval}(G^{\prime}))$, one can compute
$\min\\{d,k+1\\}$ in time $\tilde{O}(m+k^{2})$ using the algorithm of Ganesh
et al. [19]. Using binary search over $k$, we can reduce this running time to
$\tilde{O}(m+d^{2})$ when $d\leq k$. Therefore, we can compute the sum above
in time $\tilde{O}(k^{2})$: there are $k$ RLSLPs of size $\tilde{O}(k)$, and
we can stop the computation as soon as the sum of
$d_{i}=\mathsf{ed}(\mathsf{eval}(\mathbf{G}(U)[i]),\mathsf{eval}(\mathbf{G}(V)[i]))$
exceeds $k$. In total, this costs
$\tilde{O}(\mu+k^{2}+\sum_{i}\mu+d_{i}^{2}\leq
k\mu+\left(\sum_{i}d_{i}\right)^{2})=\tilde{O}(k^{2})$ time. The space
complexity can be upper-bounded (up to polylog factors) by the time
complexity.

Probability of success. The results of 6 hold with constant probability, which
can be boosted in a standard way by repeating the scheme a logarithmic number
of times.

###  B.2 A streaming algorithm for $k$-LED-PAL

See 5.1

Our algorithm maintains two sketches $x,x^{\prime}$ initialised to sketches of
the empty string $\mathsf{sk}^{\mathsf{ed}}_{2k}(\varepsilon)$. Upon receiving
$T[i]$, we append it to $x$ and prepend it to $x^{\prime}$. After performing
this update, we have $x=\mathsf{sk}^{\mathsf{ed}}_{2k}(T[.\,.i])$, and
$x^{\prime}=\mathsf{sk}^{\mathsf{ed}}_{2k}(T[.\,.i]^{R})$. We then use them to
compute $\mathsf{ed}_{\leq 2k+1}(T[.\,.i],T[.\,.i]^{R})$, which gives us
$\mathsf{ed}_{\leq k}(T[.\,.i],\textsc{PAL})$ from Property A.3. By Lemma B.3,
updating the sketches and using them to compute the edit distance takes
$\tilde{O}(k^{2})$ time per character and $\tilde{O}(k^{2})$ bits of space.

###  B.3 A streaming algorithm for $k$-LED-SQ

See 5.2

Let $U=T[.\,.i]$ be such that $\mathsf{ed}(U,\textsc{SQ})\leq k$. By Property
A.7, there exist strings $V,W$ such that $U=VW$ and $\mathsf{ed}(V,W)\leq k$.
Let $G=\mathbf{G}(V)$ and $G^{\prime}=\mathbf{G}(W)$. Under the assumptions of
Fact 6, we have $|G|=|G^{\prime}|=s$ and $G$ and $G^{\prime}$ differ at at
most $k$ indices, hence the Hamming distance between
$\mathsf{enc}(G)\mathsf{enc}(G^{\prime})$ and SQ is at most
$k\mu=\tilde{O}(k^{2})$. Therefore, our idea is to use the algorithm of
Theorem 3.2 with parameter $K=k\mu$ to detect approximate squares in the
stream of encoded grammars, and use this information to find positions in $i$
in the text where $\mathsf{ed}(T[.\,.i],\textsc{SQ})\leq k$. We first discuss
the reduction to $k$-LHD-SQ, and then describe how to use it to solve $k$-LED-
SQ.

##### Reduction to $k$-LHD-SQ.

Two issues arise for the reduction to $k$-LHD-SQ: the grammar decomposition of
$U$ is not necessarily equal to the concatenation of $G$ and $G^{\prime}$, and
adding a character to the text may reduce the size of the decomposition, hence
the conversion of the stream of characters to a stream of grammars is not
trivial.

Let $G^{\prime\prime}=\mathbf{G}(U)$ and $q=|G^{\prime\prime}|$. We assume
w.l.o.g. that $q\geq 8\tau$ (which implies $s\geq 2\tau$); otherwise, we store
all the grammars in $G^{\prime\prime}$ explicitly (taking
$O(\tau\mu)=\tilde{O}(k)$ bits of space), and do not use the following
reduction to $k$-LHD-SQ to find all the differing grammars, but use exhaustive
pairwise comparison.

While $G^{\prime\prime}$ is not necessarily equal to $GG^{\prime}$, it follows
from Corollary B.1 that $G^{\prime\prime}[1.\,.s-\tau]=G[1.\,.{s-\tau}]$,
$G^{\prime\prime}(q-s-\tau.\,.q]=G^{\prime}({\tau}.\,.s]$ and $2s\leq
q+2\tau$. In other words, $G^{\prime\prime}$ is equal to $GG^{\prime}$ with at
most $4\tau=\tilde{O}(1)$ modified, inserted or deleted grammars. Furthermore,
while appending a character to the text may reduce the number of grammars in
its decomposition, right-committed grammars will not change when appending a
letter. Therefore, we can build a monotone stream of grammars by including
only right-committed grammars, i.e., grammars whose index has been at $\tau$
positions away from the end of the decomposition at some point.

We decompose $G^{\prime\prime}$ as follows (see Figure 2 for an illustration):

$\displaystyle A$ $\displaystyle=G^{\prime\prime}[1.\,.\tau]$ $\displaystyle
D$ $\displaystyle=G^{\prime\prime}(q-s+\tau.\,.q-\tau]$ $\displaystyle B$
$\displaystyle=G^{\prime\prime}(\tau.\,.s-\tau]$ $\displaystyle E$
$\displaystyle=G^{\prime\prime}(q-\tau.\,.q]$ $\displaystyle C$
$\displaystyle=G^{\prime\prime}(s-\tau.\,.q-s+\tau]$

$V$$G[1.\,.\tau]$ $G(\tau.\,.s-\tau]$ $G(s-\tau.\,.s]$
$W$$G^{\prime}[1.\,.\tau]$ $G^{\prime}(\tau.\,.s-\tau]$
$G^{\prime}(s-\tau.\,.s]$ $U=VW$$G^{\prime\prime}[1.\,.\tau]$
$G^{\prime\prime}(\tau.\,.s-\tau]$ $G^{\prime\prime}(s-\tau.\,.q-s+\tau]$
$G^{\prime\prime}(q-s+\tau.\,.q-\tau]$ $G^{\prime\prime}(q-\tau.\,.q]$
$A$$B$$C$$D$$E$ Figure 2: Decomposition of $U=VW$.

By Corollary B.1, $A=G[1.\,.\tau]$, $B=G(\tau.\,.s-\tau]$,
$D=G^{\prime}(\tau.\,.s-\tau]$, and $E=G^{\prime}(s-\tau.\,.s]$. Furthermore,
by 6, $\mathsf{hd}(B,D)\leq k$, where the Hamming distance between two equal-
length sequences of grammars is defined as the number of positions where they
differ. $A$ and $E$ are stored explicitly, which takes
$O(\tau\cdot\mu)=\tilde{O}(k)$ space.

Further, for $c\in[1.\,.4\tau]$, define $\hat{A_{c}}$ as follows:

$\hat{A_{c}}=\begin{cases}A(\tau-c.\,.],&\text{ if }c\leq\tau,\\\
\\#^{c-\tau}A,&\text{ otherwise,}\end{cases}$

where $\\#$ denotes the dummy (empty) grammar.

######  Claim 8.

If $\mathsf{ed}(U,\textsc{SQ})\leq k$, then there exists $c\leq 4\tau$ such
that $\mathsf{hd}(\hat{A_{c}}B,CD)\leq k+\tau$.

######  Proof B.5.

For $c=|C|\leq 4\tau$, we have $|\hat{A_{c}}|=c$, and
$\mathsf{hd}(\hat{A_{c}}B,CD)=\mathsf{hd}(\hat{A_{c}},C)+\mathsf{hd}(B,D)\leq\tau+k$.

For each $c\in[1.\,.4\tau]$, we create a stream $T_{c}=\hat{A_{c}}BCD$ from a
stream of $ABCD$ (by either dropping the first $\tau-c+1$ values if
$c\leq\tau$, or by inserting $c-\tau$ dummy grammars at the start otherwise)
and apply the algorithm for $k$-LHD-SQ (Theorem 3.2) with parameter
$K=(k+\tau)\mu=\tilde{O}(k^{2})$ to it, which returns every position where
$\mathsf{hd}(\hat{A_{c}}B,CD)\leq k+\tau$. We use this information as a filter
before testing whether $\mathsf{ed}(U,\textsc{SQ})\leq k$.

Finally, notice that $E$ contains $\tau$ grammars, which may be more than just
the right-active grammars, as the size of the decomposition may shrink after
appending a character. We only want grammars up to index $q-\tau$ to be in the
stream of right-committed RLSLPs, i.e., we need to remove grammars from the
stream when the size of the decomposition is reduced. To circumvent this
issue, we simply store the grammars output by the algorithm for each of the
$\tau$ latest updates. When the grammar decomposition shrinks, we simply go
back to the corresponding grammars output and proceed from there. This takes
$\tau\cdot\tilde{O}(k^{2})=\tilde{O}(k^{2})$ bits of space.

##### Computing the edit distance between $V$ and $W$.

Using Proposition 3.9 and 7, we can also retrieve from the algorithm for
$k$-LHD-SQ the list of mismatches between $\mathsf{enc}(\hat{A_{c}}BCD)$ and
the closest square, from which we can extract the mismatching grammars in
${\hat{A_{c}}B}$ and ${CD}$. As we store $A$ explicitly, we can assume to know
every grammar of $C$.

We would like to compute $d=\mathsf{ed}_{\leq k}(V,W)$. Under the assumption
of 6, we have

$\displaystyle\mathsf{ed}(V,W)$ $\displaystyle=$
$\displaystyle=\sum_{i=1}^{s}\mathsf{ed}(\mathsf{eval}(G[i]),\mathsf{eval}(G^{\prime}[i]))$
$\displaystyle=\mathsf{ed}(\mathsf{eval}(G[.\,.\tau]),\mathsf{eval}(G^{\prime}[.\,.\tau]))$
$\displaystyle=\sum_{j:B[j]\neq
D[j]}\mathsf{ed}(\mathsf{eval}(B[j]),\mathsf{eval}(D[j]))+\mathsf{ed}(\mathsf{eval}(G(s-\tau.\,.]),\mathsf{eval}(G^{\prime}(s-\tau.\,.])).$

As for any strings $X,X^{\prime},Y,Y^{\prime}$ we have
$\mathsf{ed}(XY,X^{\prime}Y^{\prime})\leq\mathsf{ed}(X,X^{\prime})+\mathsf{ed}(Y,Y^{\prime})$,
we can combine any two terms of the above sum by concatenating the
corresponding grammars in the $\mathsf{eval}$ function. Therefore,

$\mathsf{ed}(V,W)=\mathsf{ed}(\mathsf{eval}(EA),\mathsf{eval}(G(s-\tau.\,.s]G^{\prime}[1.\,.\tau]))+\sum_{j:B[j]\neq
D[j]}\mathsf{ed}(\mathsf{eval}(B[j]),\mathsf{eval}(D[j])).$

Finally, note that
$\mathsf{eval}(G[s-\tau+1.\,.s]G^{\prime}[1.\,.\tau])=\mathsf{eval}(C)$ (see
Figure 2), and therefore
$\mathsf{ed}(V,W)=\mathsf{ed}(\mathsf{eval}(EA),\mathsf{eval}(C))+\sum_{j:B[j]\neq
D[j]}\mathsf{ed}(\mathsf{eval}(B[j]),\mathsf{eval}(D[j]))$.

Both $\mathsf{eval}(EA)$ and $\mathsf{eval}(C)$ can be represented by an RLSLP
of size $\tilde{O}(k)$ obtained by concatenating the RLSLPs
$G[s-\tau+1],\ldots,G[s],G^{\prime}[1],\ldots,G[\tau]$ and the RLSLPs in $C$
respectively. We can now apply the algorithm of Ganesh et al. [19] to compute
each of the terms in the sum above in $\tilde{O}(k^{2})$ time and space.

##### Summary.

Our algorithm runs $\tilde{O}(1)$ copies of the algorithm of Theorem 3.2 in
parallel, with distance parameter $K=\tilde{O}(k^{2})$: this uses
$\tilde{O}(k^{2})$ bits of space. Upon receiving the $i$th character of the
text, we use the algorithm of Corollary B.2 to update the decomposition of the
text, which takes time $\tilde{O}(k)$. We add all but the last $\tau$ grammars
to the stream of right-committed grammars. The algorithm of Corollary B.2 may
add up to $4\tau\lambda=\tilde{O}(1)$ grammars to the decomposition of the
text, hence we commit at most $\tilde{O}(1)$ grammars per character of the
text. Note that we only need to know whether the stream of right-committed
grammars is close to a square after pushing all symbols in the encoding of the
grammars, and do not need the intermediate results. Therefore, we can use the
algorithm of Proposition 3.9 to push the at most
$4\tau\lambda\mu=\tilde{O}(k)$ symbols in the encoding of the grammars into
the $k$-LHD-SQ subroutines using $\tilde{O}(k\sqrt{K}+K)=\tilde{O}(k^{2})$
time. After adding all the new right-committed grammars, if any copy of the
$k$-LHD-SQ algorithm signals that the current stream of grammars is within
distance $K$ of SQ, we run the above algorithm to compute the distance between
$T[.\,.i]$ and SQ, which costs $\tilde{O}(k^{2})$ time and space.

Finally, the algorithm explicitly stores the RLSLPs in $A$, the last $\tau$
grammars and the last $\tau$ output of each $k$-LHD-SQ subroutine, which uses
$\tau\mu+\tau\mu+2\tau\mu+\tau\tilde{O}(k^{2})=\tilde{O}(k^{2})$ bits of space
in total.

Overall, our algorithm uses $\tilde{O}(k^{2})$ time per character and
$\tilde{O}(k^{2})$ bits of space.

##  Appendix C Read-only algorithms for the LED problems

In this section, we present read-only algorithms for $k$-LED-PAL and $k$-LED-
SQ.

###  C.1 Structure of $k$-error occurrences

##### Approximate periodicity.

######  Definition C.1 ([10]).

A string $U$ is $d$-error periodic if there exists a primitive string $Q$ such
that $|Q|\leq|U|/128d$ and $\mathsf{ed}(U,Q^{\infty})\leq 2d$. Such a string
$Q$ is called the _$d$ -error period_ of $U$.444The original definition of
[10] considered the distance between $U$ and a substring of $Q^{\infty}$.
Changing it does not break the structure of $k$-error occurrences, but is
important for the read-only algorithms for $k$-LED-PAL and $k$-LED-SQ.

Similarly to the Hamming distance, the condition $|Q|\leq|U|/128d$ implies
that if $U$ is $d$-error periodic with $d$-error period $Q$, then $Q$ is equal
to some substring of $U$. Furthermore, we exploit the following properties:

######  Fact 9 ([22]).

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

######  Lemma C.2.

Given random access to a string $U$, testing whether it is $d$-error periodic,
and in the relevant case computing its $d$-error period, can be done using
$O(|U|d^{2})$ time and $O(d)$ space.

######  Proof C.3.

Consider a partition of $U$ into $4d$ substrings $S_{1},\ldots,S_{4d}$ of
equal length $|U|/{4d}$. At most $2d$ of them can contain an edit operation,
hence the others must be equal to a substring of $Q^{\infty}$, and as
$|Q|\leq|U|/128d=|S_{i}|/32$, these $S_{i}$ are (exactly) periodic.

This observation leads to the following algorithm: For $i\in[1.\,.4d]$, we
test whether $S_{i}$ is (exactly) periodic: if it is, we compute its period
$Q_{i}^{\prime}$; otherwise, we go to the next $i$. Let $p_{i}$ denote the
ending position of $S_{i}$ in $U$. Otherwise, we construct the string
$S_{i}^{\prime}$ by extending $S_{i}$ to the left with copies of
$Q_{i}^{\prime}$, and test whether there exists an index $j$ such that the
edit distance between $U[.\,.p_{i}]$ and $S_{i}^{\prime}[j.\,.]$ is at most
$2d$. Let $Q_{i}$ be the forward cyclic rotation of $Q_{i}^{\prime}$ by
$j\mod|Q_{i}^{\prime}|$ positions: it is a candidate for the $d$-error period
of $U$. We then test whether the edit distance between $U$ and
$(Q_{i}^{\prime})^{\infty}$ is at most $2d$: in the affirmative case, $Q_{i}$
is a $d$-error period of $U$; otherwise, we go to the next $i$. If $U$ is
$d$-error periodic, at least one of the first $2d+1$ tests must return the
$d$-error period.

Computing the exact period of a string $R$ can be done in linear time and
logarithmic space, using the algorithm of Rytter [34] to find the first
occurrence of $R$ in $R[2.\,.]R$. Computing the index that minimizes the edit
distance upper bounded by $d$ can be done in $O(|U|d)$ time and $O(d)$ space
using the classical dynamic programming algorithm for the edit distance [41].
We process $O(d)$ substrings $S_{i}$ sequentially, hence our algorithm takes
$O(|U|d^{2})$ time and $O(d)$ space.

##### Structure of approximate occurrences.

######  Definition C.4 (Chain of $k$-error occurrences).

A sequence $\mathcal{C}=p_{1}<\cdots<p_{\ell}$ of $k$-error occurrences of $P$
in $T$ forms a chain if the following two conditions are satisfied:

  1. 1.

There exists an integer $q$ such that $p_{1},\ldots,p_{\ell}$ is an arithmetic
progression with difference $q$;

  2. 2.

There exists an integer $k^{\prime}\leq k$ such that for every $p_{i}$,
$\min_{j\leq p_{i}}$ we have $\mathsf{ed}(P,T[j.\,.p_{i}])=k^{\prime}$.

######  Fact 10 (From [10, Theorem 5.1, Claim 5.16, Claim 5.17], see also [22,
Corollary III.5]).

Let $P,T$ be two strings such that $|T|\leq 3/2|P|$ and $T$ starts and ends
with a $k$-error occurrence of $P$. Then one of the following holds:

  1. 1.

Either there are $O(k^{2})$ $k$-error occurrences of $P$ in $T$, or

  2. 2.

There is a primitive string $Q$ such that $P$ is $2k$-error periodic with
$2k$-error period $Q$, $\mathsf{ed}(T,Q^{\infty})\leq 6k$, and the occurrences
of $P$ in $T$ can be decomposed into $O(k^{3})$ chains. For each chain, its
difference equals $|Q|$ and the first position in it is within distance $10k$
from a multiple of $|Q|$.

###  C.2 Online deterministic read-only algorithm for finding $k$-error
occurrences

######  Fact 11 ([27]).

Given two strings $U,V$. There is a data structure that can be built using
$O(k^{2})$ LCP queries and occupies $O(k^{2})$ space and allows retrieving,
for any two prefixes $U^{\prime},V^{\prime}$ of $U,V$ respectively,
$\mathsf{ed}_{\leq k}(U^{\prime},V^{\prime})$ in $O(k)$ time.

To be able to utilise this fact, we show how to answer LCP queries in
$k$-error periodic strings:

######  Lemma C.5.

Consider two strings $U,V,Q\in\Sigma^{*}$. Assume that $Q$ is a primitive
string and that there exist $O(k)$-length edit sequences
$\mathsf{ES}_{U},\mathsf{ES}_{V}$ between $U$ and $Q^{\infty}[1.\,.|U|]$ and
$V$ and $Q^{\infty}[1.\,.|V|]$, respectively. There is a read-only algorithm
that receives as an input $U,V$ and $\mathsf{ES}_{U},\mathsf{ES}_{V}$ and
computes $\textsf{LCP}(U[i.\,.],V[j.\,.])$ in time $O(k|Q|)$ and space
$\tilde{O}(1)$.

######  Proof C.6.

We consider two cases: (1) Both $U[i]$ and $V[j]$ are unedited by the edit
sequences; (2) Either $U[i]$ is edited by $\mathsf{ES}_{U}$ or $V[j]$ is
edited by $\mathsf{ES}_{V}$.

In the first case, let $i^{\prime}$ (resp., $j^{\prime}$) be the length of
$U[1.\,.i]$ (resp., $V[1.\,.j]$) after we apply $\mathsf{ES}_{U}$ (resp.,
$\mathsf{ES}_{V}$) to it. We perform an LCP query on
$Q^{\infty}[i^{\prime}.\,.]$ and $Q^{\infty}[j^{\prime}.\,.]$. If
$i^{\prime}=j^{\prime}\pmod{|Q|}$, the answer is $+\infty$. Otherwise, we
compute the answer in a naive way, comparing $Q^{\infty}[i^{\prime}.\,.]$ and
$Q^{\infty}[j^{\prime}.\,.]$ character-by-character. As $Q$ is primitive, we
will find a mismatch after performing $O(|Q|)$ comparisons. Let
$\ell=\textsf{LCP}(Q^{\infty}[i^{\prime}.\,.],Q^{\infty}[j^{\prime}.\,.])$. If
$U[i.\,.\min\\{i+\ell-1,|U|\\}]$ and $V[j.\,.\min\\{j+\ell-1,|V|\\}]$ are
unedited by $\mathsf{ES}_{U}$ and $\mathsf{ES}_{V}$, then
$\textsf{LCP}(U[i.\,.],V[j.\,.])=\min\\{\ell,|U|-i+1,|V|-j+1\\}$. Otherwise,
if $t_{U}$ and $t_{V}$ are the leftmost edited characters in the two strings
and $t=\min\\{t_{U},t_{V}\\}$, we output
$t-1+\textsf{LCP}(U[i+t.\,.],V[j+t.\,.])$.

Consider now the second case. Assume first that $U[i]$ is deleted or
substituted. If $U[i]=V[j]$, we output
$1+\textsf{LCP}(U[i+1.\,.],V[j+1.\,.])$, and otherwise $0$. The subcase when
$V[j]$ is deleted or substituted is symmetrical. As the parameters $i$ and $j$
are increasing, this case can occur $O(k)$ times.

An LCP query in $Q^{\infty}$ (the first case) is either the last step of the
algorithm or is followed by a call to the first case of the algorithm. As the
first case happens $O(k)$ times, the algorithm takes $O(k|Q|)$ time.

######  Lemma C.7.

There is a deterministic online read-only algorithm that finds all $k$-error
occurrences of a length-$m$ pattern $P$ in a text $T$ using $\tilde{O}(k^{4})$
bits of space and $\tilde{O}(k^{4})$ amortised time per character.

######  Proof C.8.

We prove that, for every $d\in\mathbb{Z}_{\geq 0}$, there is an algorithm
reporting the $k$-error occurrences with a delay exactly $d$.

If $d\geq\frac{m}{4}$, then we partition the text into disjoint blocks of
$b=\lfloor{\frac{m}{4}}\rfloor$ characters. Consider a block $T(r-b.\,.r]$.
Having processed $T[r+d-b]$, we use the offline algorithm [10, Main Theorem 9]
to retrieve the $k$-error occurrences of $P$ ending within the block
$T(r-b.\,.r]$, reported as $O(k^{3})$ chains. This costs $\tilde{O}(bk^{4})$
time and uses $\tilde{O}(k^{4})$ space. For every $i\in(r-b.\,.r]$, while
processing $T[i+d]$, we check if any of the chains contain an occurrence
ending at position $i$ and, if so, report the underlying distance
$\min_{j}\mathsf{ed}_{\leq k}(P,T(j.\,.i])$.

Now, suppose that $k\leq d<\frac{m}{4}$. We partition $P$ into a prefix
$L=P[1.\,.m-4d]$ and a suffix $R=P(m-4d.\,.m]$. We recursively report the
occurrences of $L$ with a delay of $5d-k\geq 4d$ and store them in a buffer of
size $2k+1$. In particular, while the algorithm processes $T[i+d]$, we have
access to $\min_{j}\mathsf{ed}_{\leq k}(L,T(j.\,.i^{\prime}])$ for all
$i^{\prime}\in[i-4d-k.\,.i-4d+k]$. We also partition the text into disjoint
blocks of $d$ characters. Consider a block $T(r-d.\,.r]$. Having received the
entire block, we use the offline algorithm [10, Main Theorem 9] to retrieve
the $k$-error occurrences of $R$ ending within the block $T(r-d.\,.r]$,
reported as $O(k^{3})$ chains. This costs $\tilde{O}(dk^{4})$ time and uses
$\tilde{O}(k^{4})$ space. If $R$ is far from periodic, it has $O(k^{2})$
occurrences. Otherwise, $R$ has a $2k$-error period $Q$ and, if $p$ and
$p^{\prime}$ are the leftmost and rightmost positions in $T(r-d.\,.r]$ where
the reported occurrences end, then $T(p-4d-k.\,.p^{\prime}]$ is at edit
distance $O(k)$ from a substring of $Q^{\infty}$. In that case, we retrieve
the underlying edits as well as the $O(k)$ edits between $R$ and a substring
of $Q^{\infty}$. In either case, while processing $T[i+d]$, if a $k$-edit
occurrence of $R$ ends at position $i$, we compute $\mathsf{ed}_{\leq
k}(R,T(i^{\prime}.\,.i])$ for all $i^{\prime}\in[i-4d-k.\,.i-4d+k]$ using 11.
In the non-periodic case, we use the naive $O(d)$-time implementation of LCP
queries. This costs $O(dk^{2})$ time per occurrence and $O(k^{4})$ amortised
per position. Otherwise, we use the $O(|Q|\cdot k)$-time implementation of LCP
queries; see Lemma C.5. This costs $O(|Q|\cdot k^{3})$ time per occurrence
and, since there are $O(k)$ occurrences among every $|Q|$ positions, also
$O(k^{4})$ amortised time per position. We can combine $\mathsf{ed}_{\leq
k}(R,T(i^{\prime}.\,.i])$ with $\min_{j}\mathsf{ed}_{\leq
k}(L,T(j.\,.i^{\prime}])$ (minimizing over $i^{\prime}\in[i-4d-k.\,.i-4d+k]$)
to obtain $\min_{j}\mathsf{ed}_{\leq k}(P,T(j.\,.i])$.

Finally, if $d<k$, we partition $P$ into a prefix $L=P[1.\,.m-4k]$ and a
suffix $R=P(m-4k.\,.m]$. We recursively report the occurrences of $L$ with a
delay of $d+3k>4d$ and store them in a buffer of size $2k+1$. In particular,
while the algorithm processes $T[i+d]$, we have access to
$\min_{j}\mathsf{ed}_{\leq k}(L,T(j.\,.i^{\prime}])$ for all
$i^{\prime}\in[i-5k.\,.i-3k]$. While processing $T[i+d]$, we compute
$\mathsf{ed}_{\leq k}(R,T(i^{\prime}.\,.i])$ for all
$i^{\prime}\in[i-5k.\,.i-3k]$ using 11 and the naive $O(k)$-time
implementation of LCP queries. This costs $O(k^{3})$ time per position. We can
combine $\mathsf{ed}_{\leq k}(R,T(i^{\prime}.\,.i])$ with
$\min_{j}\mathsf{ed}_{\leq k}(L,T(j.\,.i^{\prime}])$ (minimizing over
$i^{\prime}\in[i-4d-k.\,.i-4d+k]$) to obtain $\min_{j}\mathsf{ed}_{\leq
k}(P,T(j.\,.i])$.

At each level of the recursive algorithm, we use $\tilde{O}(k^{4})$ space and
amortised time per character. The recursive calls decrease the pattern length
and increase the delay at least $4$ times, so the depth of the recursion is
$O(\log m)$.

###  C.3 Read-only algorithm for $k$-LED-PAL

See 5.3

Consider a family
$\mathcal{P}=\\{P_{j}:P_{j}=T[.\,.2^{j}],j\in[1.\,.\lfloor\log n\rfloor]\\}$
of prefixes of the text. For each $j$, define $\ell_{j}=|P_{j}|$,
$T_{j}=T[.\,.\ell_{j+1})$, and $\mathsf{Occ}_{j}$ to be the set of $2k$-error
occurrences of $P_{j}^{R}$ in $T_{j}$ larger or equal to $\ell_{j}$. Using
Lemma C.2, we can decide whether $P_{j}$ is $2k$-error periodic and if it is,
compute its $2k$-error period $Q_{j}$ in $O(|P_{j}|k^{2})$ time and $O(k)$
space. Using Ukkonen’s algorithm [41], we can also compute a $O(k)$-length
edit sequence $\mathsf{ES}_{j}$ from $P_{j}$ to $(Q_{j})^{\infty}$ in $O(k)$
amortised time per character and $\tilde{O}(k^{2})$ space.

######  Claim 12.

If $\mathsf{ed}(T[.\,.i],\textsc{PAL})\leq k$, then $i\in\mathsf{Occ}_{j^{*}}$
for $j^{*}=\max\\{j:\ell_{j}\leq i\\}$.

######  Proof C.9.

By Corollary A.5, $\mathsf{ed}(T[.\,.i],T[.\,.i]^{R})\leq 2k$. We also have
$\ell_{j}\leq i\leq 2\ell_{j}-1$. Hence, $i\in\mathsf{Occ}_{j}$.

Define $i^{\prime}=\lfloor i/2\rfloor$. By Corollary A.5, to decide the edit
distance between $T[.\,.i]$ and PAL, it suffices to compute
$e=\min_{j\in[i^{\prime}-k.\,.i^{\prime}+k]}\\{\min\\{\mathsf{ed}_{\leq
k}(T[.\,.j],T[j+1.\,.]^{R}),\mathsf{ed}_{\leq
k}(T[.\,.j],T[j+2.\,.]^{R})\\}\\}$. We will only compute this value if
$i\in\mathsf{Occ}^{\prime}_{j^{*}}\supseteq\mathsf{Occ}_{j^{*}}$ (the set
$\mathsf{Occ}^{\prime}_{j^{*}}$ to be defined below), and otherwise we will
output $k+1$.

For each $j$, we run the online algorithm of Lemma C.7 that uses
$\tilde{O}(k^{4})$ amortised time per character and $\tilde{O}(k^{4})$ space
to find the set $\mathsf{Occ}_{j}$ of $k$-error occurrences of $P_{j}^{R}$ in
$T_{j}$. We start it immediately after receiving $T[\ell_{j}]$ and catch up by
processing the first $\ell_{j}$ characters of $T_{j}$ at once to be online. If
$P_{j}$ is not $2k$-error periodic, then by 10, $|\mathsf{Occ}_{j}|=O(k^{2})$
and we define $\mathsf{Occ}_{j}^{\prime}=\mathsf{Occ}_{j}$. If $P_{j}$ is
$2k$-error periodic, let $p_{j}$ be the leftmost position in
$\mathsf{Occ}_{j}$, and $r_{j}$ the largest integer such that
$\mathsf{ed}(T[p_{j}.\,.p_{j}+r_{j}\cdot|Q_{j}|],(Q_{j}^{R})^{\infty})\leq
12k$. Define $\mathsf{Occ}_{j}^{\prime}=\\{p_{j}+m\cdot|Q_{j}|+\Delta:0\leq
m\leq r_{j},|\Delta|\leq 10k\\}$. By Fact 10,
$\mathsf{Occ}_{j}^{\prime}\supseteq\mathsf{Occ}_{j}$. The integer $r_{j}$ can
be computed by running an instance of Ukkonen’s online algorithm [41] for
$T[p_{j}+1.\,.]$ and $(Q_{j}^{R})^{\infty}$, which takes $O(k)$ amortised time
per character and $\tilde{O}(k^{2})$ space. If $i\leq p_{j}+r_{j}\cdot|Q_{j}|$
is the current position, the algorithm also allows extracting an $O(k)$-length
edit sequence $\mathsf{ES}_{j}^{\prime}$ between $T[p_{j}.\,.i]$ and
$(Q_{j}^{R})^{\infty}$ in $O(k)$ time.

##### Computing the distances.

Let $i$ be the current position and $j^{*}=\max\\{j:\ell_{j}\leq i\\}$. Assume
that $i\in\mathsf{Occ}_{j}^{\prime}$. If $P_{j}$ is not $2k$-error periodic,
we compute $e$ using $k$ instances of Ukkonen’s online algorithm [41], which
takes $O(k^{2})$ amortised time per character in total and $\tilde{O}(k^{2})$
space. Otherwise, the value $e$ is computed as follows. First, if $i=p_{j}$,
we run another instance of Ukkonen’s online algorithm [41] to compute an
$O(k)$-length edit sequence $\mathsf{ES}_{j}^{\prime\prime}$ between
$T(p_{j}-\ell_{j}-k.\,.p_{j}]$ and $(Q_{j}^{R})^{\infty})$, which must exist
as $p_{j}$ is a $2k$-error occurrence of $P_{j}^{R}$ and $P_{j}$ is $k$-error
periodic with period $Q_{j}$. This takes $O(k)$ amortised time and
$\tilde{O}(k^{2})$ space. Now, to compute the value $e$, we extract
$O(k)$-length edit sequences between $T[1.\,.\ell_{j}+k]$ and $Q_{j}^{\infty}$
and between $T(i-\ell_{j}-k.\,.i]$ and $(Q_{j}^{R})^{\infty}$ in $O(k)$ time
from $\mathsf{ES}_{j}$, $\mathsf{ES}_{j}^{\prime}$, and
$\mathsf{ES}_{j}^{\prime\prime}$, and then apply 11 and Lemma C.5 to compute
$e$ in $O(k^{3}|Q_{j}|)$ time and $\tilde{O}(k^{2})$ space.

##### Summary.

The algorithm of Lemma C.7 uses $\tilde{O}(k^{4})$ amortised time per
character and $\tilde{O}(k^{4})$ space. Processing aperiodic prefixes costs
$\tilde{O}(k^{2})$ amortised time per character and $\tilde{O}(k^{2})$ space.
To upper bound the complexity of processing periodic prefixes, note that we
test $O(k)$ positions out of $|Q_{j}|$, and therefore use $O(k^{4})$ amortised
time per character and $\tilde{O}(k^{2})$ space.

###  C.4 Read-only algorithm for $k$-LED-SQ

See 5.4

We first define a filtering family of prefixes $\mathcal{P}$ of the text.
Start by considering the prefixes $R_{j}=T[.\,.\lfloor(3/2)^{j}\rfloor]$,
$j\in[1.\,.\lfloor\log_{3/2}n\rfloor]$. If $R_{j}$ is $k$-error periodic but
$R_{j+1}$ is not, add to $\mathcal{P}$ the shortest extension of $R_{j}$ that
is not $k$-error periodic. Hereafter, let $\mathcal{P}=\\{P_{j}\\}$ denote the
resulting family of prefixes, sorted in order of increasing lengths. For each
$j$, let $\ell_{j}=|P_{j}|$, $T_{j}=T[1.\,.\ell_{j+1}+\ell_{j}]$, and
$\mathsf{Occ}_{j}$ the set of $3k$-error occurrences of $P_{j}$ in $T_{j}$. We
build $\mathcal{P}$ as we read $T$. When $T[\ell_{j}]$ arrives, we add $R_{j}$
to $P_{j}$ and launch an instance of the patter-matching algorithm for $T_{j}$
to compute $\mathsf{Occ}_{j}$ (we process the first $\ell_{j}$ characters of
$T_{j}$ at once to be online). Finally, we apply Lemma C.2 to test $R_{j}$ for
$3k$-error periodicity, which requires $O(k^{2})$ amortised time and
$\tilde{O}(k)$ space. If $R_{j}$ is $3k$-periodic, the lemma also allows to
compute the period $Q_{j}$ of $R_{j}$. We finish by computing the longest
$3k$-error periodic extension $R^{\prime}_{j}$ of $R_{j}$: by 9, the
$3k$-error period of $R^{\prime}_{j}$ equals $Q_{j}$ and therefore we can
compute $R^{\prime}_{j}$ by running Ukkonen’s algorithm on $T$ and $Q_{j}$,
which requires $O(k)$ amortised time and $\tilde{O}(k^{2})$ space. The
algorithm also outputs $O(k)$-length edit sequence $\mathsf{ES}_{j}$ between
$R^{\prime}_{j}$ and $Q_{j}^{\infty}[1.\,.|R^{\prime}_{j}|]$.

######  Claim 13.

If $\mathsf{ed}(T[.\,.i],\textsc{SQ})\leq k$, then
$i^{\prime}+\ell_{j^{*}}\in\mathsf{Occ}_{j^{*}}$, where $i^{\prime}=\lfloor
i/2\rfloor$ and $j^{*}=\max\\{j:\ell_{j}+\lceil{k/2\rceil}\leq i^{\prime}\\}$.
Furthermore, if $P_{j^{*}}$ is $3k$-periodic, then
$\mathsf{ed}(T(i^{\prime}+\ell_{j^{*}}.\,.i],Q_{j^{*}}^{\infty})\leq 10k+1$.

######  Proof C.10.

By Corollary A.9, we have
$\mathsf{ed}(T[.\,.i^{\prime}+t],T[i^{\prime}+t+1.\,.i])\leq k$ for some $t$,
$|t|\leq\lceil k/2\rceil$. As $P_{j^{*}}$ is a prefix of
$T[.\,.i^{\prime}+t]$, we have
$\mathsf{ed}(P_{j^{*}},T[i^{\prime}+t+1.\,.i^{\prime}+t+\ell_{j^{*}}+\Delta])\leq
k$ for some $-k\leq\Delta\leq k$ and therefore by the triangle inequality
$\mathsf{ed}(P_{j^{*}},T[i^{\prime}+t+1.\,.i^{\prime}+\ell_{j^{*}}])\leq 3k$.
It follows that
$\ell_{j^{*}}<i^{\prime}+\ell_{j^{*}}\leq\ell_{j^{*}+1}+\ell_{j^{*}}$ is a
$3k$-error occurrence of $P_{j^{*}}$ and hence
$i^{\prime}+\ell_{j^{*}}\in\mathsf{Occ}_{j^{*}}$. To show the second part of
the claim, note that $i^{\prime}+t\leq\ell_{j^{*}+1}+k$. Additionally, by the
construction of $\mathcal{P}$ and 9 we have
$\mathsf{ed}(P_{j^{*}},(Q_{j^{*}})^{\infty})\leq 7k+1$. Applying the triangle
inequality one more time, we obtain that
$\mathsf{ed}(T[i^{\prime}+t+1.\,.i],(Q_{j^{*}})^{\infty})\leq 10k+1$, as
cutting equal-length suffixes of both strings cannot increase the edit
distance.

By Corollary A.9, to get the edit distance between $T[.\,.i]$ and SQ, it
suffices to compute the value
$e=\min_{j\in[i^{\prime}-k.\,.i^{\prime}+k]}\mathsf{ed}_{\leq
k}(T[.\,.j],T(j.\,.])$. We will only compute this value if
$i^{\prime}+\ell_{j^{*}}\in\mathsf{Occ}_{j^{*}}^{\prime}\supseteq\mathsf{Occ}_{j^{*}}$
to be defined below, and otherwise we output $\infty$. The set
$\mathsf{Occ}_{j^{*}}^{\prime}$ is defined differently depending on whether
$P_{j}$ is $3k$-error periodic.

If $P_{j}$ is not $3k$-error periodic,
$\mathsf{Occ}_{j^{*}}^{\prime}=\mathsf{Occ}_{j^{*}}$ and by 10, occupies
$\tilde{O}(k^{2})$ space. Using Lemma C.7, $\mathsf{Occ}_{j^{*}}^{\prime}$ can
be computed in $\tilde{O}(k^{4})$ amortised time per character and
$\tilde{O}(k^{4})$ space. If $P_{j}$ is $3k$-error periodic with a period
$|Q_{j}|$, $\mathsf{Occ}_{j^{*}}^{\prime}$ is defined to be
$\\{p_{j^{*}}+t\cdot|Q_{j^{*}}|+\Delta:0\leq t\leq r_{j^{*}},|\Delta|\leq
10k\\}$, where $p_{j^{*}}$ is the leftmost position in $\mathsf{Occ}_{j^{*}}$
and $r_{j^{*}}$ is the largest integer such that
$\mathsf{ed}(T[p_{j}.\,.p_{j}+r_{j}\cdot|Q_{j}|],(Q_{j}^{R})^{\infty})\leq
2\cdot(10k+1)$. By 10 and 13,
$\mathsf{Occ}_{j^{*}}^{\prime}\supseteq\mathsf{Occ}_{j^{*}}$. The set
$\mathsf{Occ}_{j^{*}}^{\prime}$ is computed as follows in this case: First, we
identify $p_{j}$ using Lemma C.7. Then, we launch Ukkonen’s online algorithm
[41] to compute $r_{j}$, which takes $O(k^{2})$ amortised time per character
and $O(k^{2})$ space.

##### Computing the distances.

Consider the moment when $T[i]$ arrives. Let $i^{\prime}=\lfloor i/2\rfloor$
and $j^{*}=\max\\{j:\ell_{j}+\lceil{k/2\rceil}\leq i^{\prime}\\}$. If
$i^{\prime}+\ell_{j^{*}}\notin\mathsf{Occ}^{\prime}_{j^{*}}$, the algorithm
outputs $k+1$. Below we assume
$i^{\prime}+\ell_{j^{*}}\in\mathsf{Occ}^{\prime}_{j^{*}}$.

If $P_{j^{*}}$ is not $3k$-error periodic, we compute
$e=\min_{j\in[i^{\prime}-k.\,.i^{\prime}+k]}\mathsf{ed}_{\leq
k}(T[.\,.j],T(j.\,.])$ by running $k$ instances of Ukkonen’s algorithm [41].
As $|\mathsf{Occ}^{\prime}_{j^{*}}|=O(k^{2})$, testing all positions in
$\mathsf{Occ}^{\prime}_{j^{*}}$ requires $\tilde{O}(k)$ space and $O(k^{4})$
amortised time per character in total.

Otherwise, we compute $e$ as follows. If $i^{\prime}+\ell_{j^{*}}=p_{j^{*}}$,
we use one instance of Ukkonen’s algorithm [41] to compute an $O(k)$-length
edit sequence $\mathsf{ES}^{\prime\prime}_{j^{*}}$ between
$T[i^{\prime}.\,.i^{\prime}+\ell_{j^{*}}]^{R}$ and
$Q_{j}^{\infty}[1.\,.\ell_{j^{*}}]$. For each
$j\in[i^{\prime}-k.\,.i^{\prime}+k]$, we first extract $O(k)$-edit sequences
between $T[1.\,.j]$ and $(Q_{j^{*}})^{\infty}[1.\,.j]$ and between $T(j.\,.i]$
and $(Q_{j^{*}})^{\infty}[1.\,.j-i]$ from $\mathsf{ES}_{j^{*}}$,
$\mathsf{ES}^{\prime}_{j^{*}}$, and $\mathsf{ES}^{\prime\prime}_{j^{*}}$ in
$O(k)$ time, and then apply Fact 11 and Lemma C.5 to compute
$\mathsf{ed}_{\leq k}(T[.\,.j],T(j.\,.])$ using $O(|Q_{j^{*}}|k^{3})$ time and
$O(k^{2})$ space.

##### Summary.

Computing $\mathcal{P}$ takes $\tilde{O}(k)$ amortised time per character and
$\tilde{O}(k^{2})$ space. The pattern-matching algorithm of Lemma C.7 takes
$\tilde{O}(k^{4})$ amortised time per character and $\tilde{O}(k^{4})$ space.
Processing aperiodic prefixes requires $O(k^{4})$ amortised time per character
and $\tilde{O}(k)$ space. Processing periodic prefixes takes $O(k^{4})$ time
and $O(k^{2})$ space as by the definition of $\mathsf{Occ}_{j}$ we test $O(k)$
positions out of $|Q_{j}|$.