# Dynamic data structures for parameterized string problems††thanks: This work
is a part of projects BOBR (MP), TIPEA (KW), and CUTACOMBS (AZ-P) that have
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreements no.
948057, 850979 and 714704, respectively).

Jędrzej Olkowski111Faculty of Mathematics, Informatics, and Mechanics,
University of Warsaw, Poland<EMAIL_ADDRESS>Michał
Pilipczuk222Institute of Informatics, University of Warsaw, Poland,
<EMAIL_ADDRESS>Mateusz Rychlicki333Faculty of Mathematics,
Informatics, and Mechanics, University of Warsaw, Poland,
<EMAIL_ADDRESS>Karol Węgrzycki444Saarland University and
Max Planck Institute for Informatics, Saarbrücken, Germany<EMAIL_ADDRESS>saarland.de Anna Zych-Pawlewicz555Institute of Informatics, University of
Warsaw, Poland<EMAIL_ADDRESS>
We revisit classic string problems considered in the area of parameterized
complexity, and study them through the lens of dynamic data structures. That
is, instead of asking for a static algorithm that solves the given instance
efficiently, our goal is to design a data structure that efficiently maintains
a solution, or reports a lack thereof, upon updates in the instance.

We first consider the Closest String problem, for which we design randomized
dynamic data structures with amortized update times $d^{\mathcal{O}(d)}$ and
$|\Sigma|^{\mathcal{O}(d)}$, respectively, where $\Sigma$ is the alphabet and
$d$ is the assumed bound on the maximum distance. These are obtained by
combining known static approaches to Closest String with color-coding.

Next, we note that from a result of Frandsen et al. [J. ACM’97] one can easily
infer a meta-theorem that provides dynamic data structures for parameterized
string problems with worst-case update time of the form
$\mathcal{O}_{k}(\log\log n)$, where $k$ is the parameter in question and $n$
is the length of the string. We showcase the utility of this meta-theorem by
giving such data structures for problems Disjoint Factors and Edit Distance.
We also give explicit data structures for these problems, with worst-case
update times $\mathcal{O}(k2^{k}\log\log n)$ and $\mathcal{O}(k^{2}\log\log
n)$, respectively. Finally, we discuss how a lower bound methodology
introduced by Amarilli et al. [ICALP’21] can be used to show that obtaining
update time $\mathcal{O}(f(k))$ for Disjoint Factors and Edit Distance is
unlikely already for a constant value of the parameter $k$.

##  1 Introduction

The field of parameterized complexity is based on the principle of
parameterization: measuring the usage of resources not only in terms of the
total input size, but also in terms of auxiliary complexity measures called
parameters. Traditionally, the principle is applied to static algorithms and
their running times, but the idea can be — and has been — used within
essentially every algorithmic paradigm. Among these, a recent line of research
has identified the area of dynamic data structures as one where the
application of the parameterized approach leads to new and interesting
results, see e.g. [3, 16, 18, 19, 24, 31]. In this work we continue this
promising direction by investigating classic string problems considered in
parameterized complexity.

Arguably, the most widely known parameterized string problem is Closest
String.

Closest String Input: Integer $d$ and words
$s_{1},s_{2},\ldots,s_{n}\in\Sigma^{L}$ over an alphabet $\Sigma$, each of
length $L$ Task: Decide whether there exists a word $c\in\Sigma^{L}$ such that
for every $i\in\\{1,\ldots,n\\}$, the Hamming distance between $s_{i}$ and $c$
is at most $d$.

Closest String has several natural parameters: $n$, $d$, $L$, $|\Sigma|$. For
the parameterization by $d$ and $\Sigma$, Gramm et al. [23] gave a
$d^{\mathcal{O}(d)}\cdot(nL)^{\mathcal{O}(1)}$-time algorithm, while Ma and
Sun [30] gave a $|\Sigma|^{\mathcal{O}(d)}\cdot(nL)^{\mathcal{O}(1)}$-time
algorithm. By now, these are literally textbook examples of the technique of
branching [17, Theorem 3.14 and Exercise 3.25], and their running times are
known to be asymptotically optimal under the Exponential Time Hypothesis (ETH)
[29]. For the parameterization by $n$, the classic algorithm of Gramm et al.
[23] solves the problem in time $2^{n^{\mathcal{O}(n)}}\cdot
L^{\mathcal{O}(1)}$ by a reduction to integer programming in dimension
$n^{\mathcal{O}(n)}$. Recently, Koutecký et al. [27] improved this running
time to $n^{\mathcal{O}(n^{2})}\cdot L^{\mathcal{O}(1)}$ using exciting
developments in parameterized algorithms for block-structured integer
programs. Kernelization algorithms for Closest String were studied in [8].

We study the dynamic variant of Closest String, which is to design a dynamic
data structure supporting the following operations:

  * •

Initialize the data structure for a given instance of Closest String.

  * •

Update the data structure upon modification of a single symbol in a single
string $s_{i}$.

  * •

Query whether the current instance is a yes-instance of Closest String.

Note that parameters $n$, $d$, $L$, and $\Sigma$ are fixed on the
initialization and do not change over the life of the data structure; only the
strings $s_{1},\ldots,s_{n}$ can be modified, and by one symbol at the time.
Also, we assume that upon query, the data structure is only required to answer
yes or no, and does not need to provide the solution $c$.

For this variant we give randomized dynamic data structures whose update time
match the parametric factors in the runtimes of the algorithms of Gramm et al.
[23] and of Ma and Sun [30].

######  Theorem 1.1.

The dynamic variant of Closest String admits a randomized data structure with
initialization time $2^{\mathcal{O}(d)}\cdot nL|\Sigma|^{1+o(1)}$, amortized
update time $2^{\mathcal{O}(d)}$, and worst-case query time
$d^{\mathcal{O}(d)}$ or $|\Sigma|^{\mathcal{O}(d)}$, whichever is smaller. The
answer to each query may result with a false positive with probability at most
$2^{-\Omega(d)}$; there are no false negatives.

In the proof of Theorem 1.1 we combine the classic approach to Closest String,
originating in [23, 30], with an interesting application of color-coding. The
randomization comes from the color-coding; we can dispose of it using standard
derandomization techniques (see [17, Section 5.6]), but at the cost of
introducing an additional $\mathcal{O}(\log(nL))$ factor in the update time.
Also, note that by the results of [29], under ETH one cannot expect to improve
the query time to $d^{o(d)}$ or $|\Sigma|^{o(d)}$, even in the amortized
sense.

Next, we turn attention to other problems. First, we note that combining a
result of Frandsen et al. [20] on dynamic word problem for aperiodic
semigroups with the classic Schützenberger-McNaughton-Papert Theorem [33, 38]
yields the following meta-theorem.

######  Theorem 1.2.

Suppose $\Sigma$ is a finite alphabet and $L\subseteq\Sigma^{\star}$ is a
language definable in logic $\mathsf{FO}[\Sigma,<]$. Then there exists a data
structure that for a given word $w\in\Sigma^{\star}$, which can be updated
over time by replacing single symbols, maintains whether $w\in L$. The data
structure can be initialized on a given word $w$ in time $\mathcal{O}(n)$
where $n=|w|$, and then every update takes worst-case time
$\mathcal{O}(\log\log n)$.

Theorem 1.2 follows immediately from the combination explained above, so we
consider it an essentially known result (though we could not find this precise
formulation in the literature). What is new is the observation that this
result is a very convenient tool for obtaining dynamic data structures in the
parameterized setting. We showcase this by considering the following two
problems.

Disjoint Factors Input: A word $w\in\\{1,\ldots,k\\}^{\star}$, where $k$ is an
integer Task: Decide whether there exists pairwise disjoint subwords
$w_{1},w_{2},\dots,w_{k}$ of $w$ such that for each $i\in\\{1,\ldots,k\\}$,
$w_{i}$ has length at least $2$ and begins and ends with symbol $i$.

Edit Distance Input: Integer $k$ and two words $u,v\in\Sigma^{\star}$, where
$\Sigma$ is an alphabet Task: Decide whether $\mathsf{ed}(u,v)\leqslant k$,
that is, whether $v$ can be obtained from $u$ by a sequence of at most $k$
edits, each consisting of a deletion, insertion, or substitution of a single
symbol.

Disjoint Factors has been introduced in [11] as a stepping stone for
kernelization hardness of the Disjoint Cycles and Disjoint Paths problems. We
choose to use it in this work as an example, because its simple combinatorial
structure makes many basic ideas clearly visible. On the other hand, Edit
Distance is a problem of immense importance with multiple applications. It can
be solved in time $\mathcal{O}(n^{2})$ by standard dynamic programming (where
$n$ is the total length of the words). The best currently known algorithm for
Edit Distance runs in $\mathcal{O}(n^{2}/\log(n)^{2})$ time [32] and under the
Strong ETH, there is no strongly subquadratic algorithm [7, 1, 14, 2]. Here,
we focus on parameterization by the size of the solution $k$. In terms of this
parametrization Edit Distance can be solved in $\mathcal{O}(n+k^{2})$ by the
celebrated Landau and Vishkin algorithm [28] and even in sublinear time when
approximation is allowed [9, 6, 22].

We observe that both for Disjoint Factors and for Edit Distance, the language
of yes-instances can be defined in $\mathsf{FO}[\Sigma,<]$ using a sentence of
length bounded in terms of the parameters. Therefore, by simply applying
Theorem 1.2, we obtain data structures for the dynamic variants of Disjoint
Factors and Edit Distance (defined similarly as for Closest String) with
worst-case update times $\mathcal{O}_{k}(\log\log n)$. As usual with meta-
theorems, the parametric dependence in these complexity guarantees is not
explicit. For this reason, we also design explicit data structures for both
problems.

######  Theorem 1.3.

The dynamic variant of Disjoint Factors admits a data structure with
initialization time $\mathcal{O}(k2^{k}+kn)$, worst-case query time
$\mathcal{O}(1)$, and worst-case update time $\mathcal{O}(k2^{k}\log\log n)$.

######  Theorem 1.4.

The dynamic variant of Edit Distance admits a data structure with
initialization time $\mathcal{O}(kn)$, worst-case query time $\mathcal{O}(1)$,
and worst-case update time $\mathcal{O}(k^{2}\log\log n)$

Theorems 1.3 and 1.4 are based on Lemmas 5.1 and 5.3 and the static algorithms
shown under these lemmas. Our key component are van Emde Boas trees [41]. This
is not surprising, as van Emde Boas trees are also the main tool underlying
the proof of Theorem 1.2 (see [20]). In both cases, we heavily build upon
known static algorithms [28, 11]. We point out that these results serve mainly
as a demonstration that one can improve the dependence on the parameter
guaranteed by Theorem 1.2 for concrete problems. We are not aware of any
previous works on Disjoint Factors in exactly this dynamic setting. Edit
Distance was considered in the dynamic setting for unbounded values of $k$ and
only polynomial in $n$ updates are known [26, 15, 5].

Finally, we observe that we can use the hardness methodology proposed by
Amarilli et al. [4] to establish conditional lower bounds against improving
the update time in Theorems 1.3 and 1.4. More precisely, we prove that already
for constant values of the parameters, the problems Disjoint Factors and Edit
Distance are prefix-$U_{1}$ hard, which means that finding a data structure
for them is at least as hard as designing a data structure for the following
problem: for a dynamic word $w$ over $\\{0,1\\}^{\star}$, support queries of
the form “given $i$, is the first symbol $1$ in $w$ at position $\leqslant
i$”. Amarilli et al. [4] conjectured that no data structure for this problem
achieves update time $\mathcal{O}(1)$, and our reduction carry this hardness
over to the dynamic variants of Disjoint Factors and Edit Distance. Let us
point out that the two discussed problems are just examples, and the obtained
hardness methodology can be applied to a multitude of other dynamic string
problems.

#### Organization

In the Section 2 we give a short preliminaries. Next, in Section 3 we present
a proof of Theorem 1.1 and in Section 4 we prove Theorem 1.2. Subsequently, in
Section 5 we give dynamic data structures for Disjoint Factors and Edit
Distance and in Section 6 we show lower bounds for them. Appendix A contains
omitted proofs.

##  2 Preliminaries

For a parameter $\ell$, we write $\mathcal{O}_{\ell}(\cdot)$ to hide factors
depending only on $\ell$. The $\mathrm{poly}(n_{1},n_{2})$ denotes
$(n_{1}n_{2})^{\mathcal{O}(1)}$. We use a shorthand notation
$[n]\coloneqq\\{1,\ldots,n\\}$. For two sets $X,Y$, $X\triangle Y$ denotes
their symmetric difference $(X\setminus Y)\cup(Y\setminus X)$. For two words
$u,v\in\Sigma^{L}$, by $\mathrm{dist}(u,v)$ we denote the Hamming distance
between $u$ and $v$. For a word $u\in\Sigma^{L}$ and a set $X\subseteq[L]$, we
write $a[X]\in\Sigma^{|X|}$ for the word obtained from $u$ by removing all
positions outside of $X$. For $1\leqslant i\leqslant j\leqslant m$, we write
$u[i:j]\in\Sigma^{j-i+1}$ for $u[\\{i,\ldots,j\\}]$.

#### Computation Model

In this paper we work in the standard word-RAM model. In all our results the
$\mathcal{O}(\log\log n)$ factors come exclusively from application of van
Emde Boas trees that solve Predecessor problem, where one needs to maintain a
set $S$ of $n$ $w$-bit integers. In update one can insert/delete integers
to/from set $S$. During query, for a given integer $x$ one should returns the
largest integer $y\in S$ such that $x\geqslant y$. Predecessor problem is a
well-studied problem both in terms of lower and upper bounds (see the recent
survey [35]). In word-RAM the complexity of Predecessor operations is well
understood to be

$\Theta\left(\max\left[1,\min\left\\{\log_{w}(n),\frac{\log\frac{w}{\log{w}}}{\log\left(\log\frac{w}{\log{w}}/\log\frac{\log
n}{\log w}\right)},\log\frac{\log(2^{w}-n)}{\log w}\right\\}\right]\right)$
(1)

The upper and lower bounds were given by Pătraşcu and Thorup [36], see also
[10, 21]. This means that strictly speaking $\mathcal{O}(\log\log n)$ factors
in our paper, could be replaced with Equation 1 in word-RAM model depending on
word size. We are using the worse $\mathcal{O}(\log\log n)$ bound in order to
keep the results transparent. Note that the $\mathcal{O}(\log\log n)$ bound
for Predecessor is tight in more restricted computation models (see, e.g.,
[34]).

##  3 Closest String

In this section, we show the first half of Theorem 1.1 by proving the
following theorem.

######  Theorem 3.1.

The dynamic variant of Closest String admits a randomized data structure with
initialization time $2^{\mathcal{O}(d)}nL$, amortized update time
$2^{\mathcal{O}(d)}$, and worst-case query time $d^{\mathcal{O}(d)}$. The
answer to each query may result with a false positive with probability at most
$2^{-\Omega(d)}$; there are no false negatives.

Throughout this section we fix the parameter $d\in\mathbb{N}$ and denote
$\mathcal{S}\coloneqq\\{s_{1},\ldots,s_{n}\\}$ for brevity, and call it a
dictionary. Then updates on such a dictionary consist of replacing one symbol
in one word with another symbol. Our data structure is based on the static
algorithm for Closest String due to Gramm et al. [23].

###  3.1 Branching for Closest String

1

Algorithm  _ClosestString(_$\mathcal{S},d$_)_

2 if  _there exist $s_{i},s_{j}\in\mathcal{S}$ such that
$\mathrm{dist}(s_{i},s_{j})>2d$ _ then

3 return False

4 Set $q$ to be any word from $S$

5 return $\mathtt{ClosestStringRec}$($\mathcal{S},q,d$)

6

Procedure  _ClosestStringRec(_$\mathcal{S},q,x$_)_

7 if  _$x <0$_ then

8 return False

9 if  _there exists $s\in\mathcal{S}$ such that $\mathrm{dist}(s,q)>d$ _ then

10 Find $P\coloneqq\\{i\in[L]\text{ such that }s[i]\neq q[i]\\}$

11 // Observe that $|P|\leqslant 3d$

12 for  _$i\in P$_ do

13 Set $q^{\prime}[j]\coloneqq\begin{cases}s[i]&\text{if }i=j,\\\
q[j]&\text{otherwise}.\\\ \end{cases}$

14 if  _$\mathtt{ClosestString}(\mathcal{S},q^{\prime},x-1)$_ then

15 return True

16 return False

17 return True

Algorithm 1 Pseudocode of static $\mathcal{O}((3d)^{d}\mathrm{poly}(n,L))$
time algorithm for Closest String. To get a dynamic data structure, use Lemma
3.2 to perform manipulations on $q$.

Algorithm 1 presents a pseudocode for an $(3d)^{d}\mathrm{poly}(n,L)$ time
algorithm for Closest String loosely based on [23]. We first check if every
pair of words of $\mathcal{S}$ are at distance at most more than $2d$ from
each other; otherwise, by triangle inequality, we can safely terminate and
return that there is no solution. Following this, we run a recursive search
that maintains a candidate $q$ for a solution, together with an upper bound
$x$ on how far from $q$, in terms of Hamming distance, we allow the sought
solution to be. These are initially set to be any word in $\mathcal{S}$ and
$d$. Within the search, we first verify whether $q$ is already a solution. If
yes, then we can terminate, this time yielding a positive answer. Otherwise,
there is some $s\in\mathcal{S}$ at distance more than $d$ from $q$. Observe
that due to the initial check and the fact that during recursion we modify $q$
at most $d$ times, it will be always the case that $s$ and $q$ differ on at
most $3d$ positions. Hence, we can branch over one of at most $3d$
possibilities of modifying $q$ by a single letter so that $q$ gets closer to
$s$. The nontrivial observation is that if there exists a solution, one of the
modifications will take us closer to it in terms of the Hamming distance.

For the running time, observe that in each call we can make at most
$|P|\leqslant 3d$ guesses. Moreover, through the execution of the algorithm we
can only modify at most $d$ letters in $q$. This means that the total size of
the recursion tree is $\mathcal{O}((3d)^{d})$.666With clever optimizations,
one can decrease the running time to be
$\mathcal{O}((d+1)^{d}\mathrm{poly}(n,L))$ [17].

Let us take a closer look at the polynomial factors of the algorithm presented
above and discuss problems with dynamization. In line 1 we need to check if
there exist words $s_{i},s_{j}\in\mathcal{S}$ with
$\mathrm{dist}(s_{i},s_{j})>2d$. Naively, one needs to iterate over every pair
of words in $\mathcal{S}$ and compute the distance exactly which already
requires $n^{2}$ iterations, where $n=|\mathcal{S}|$. Even if somehow, this
number could be decreased, observe that in order to compute a distance between
a fixed pair of words one needs to at least read them in $\mathcal{O}(L)$
time, which is too slow. Later, manipulations on the candidate word $q$ also
require $\mathcal{O}(nL)$ time in each call of the recursive procedure
$\mathtt{ClosestStringRec}$(), as $q$ is checked against all words in
$\mathcal{S}$.

We remedy these problems by introducing a data structure that maintains a
dictionary $\mathcal{S}$ and provides access to all operations needed in the
algorithm presented above, including efficient manipulation of the candidate
$q$. This data structure is described in the following lemma.

######  Lemma 3.2 (Far word data structure).

There exists a randomized data structure that maintains dictionary
$\mathcal{S}$ of words in $\Sigma^{L}$ with amortized $2^{\mathcal{O}(d)}$
time updates; the initialization time is $2^{\mathcal{O}(d)}nL|\Sigma|$. The
data structure provides the following method:

  * •

$\mathtt{QueryFarPair}()$: Decide if there exist $s,s^{\prime}\in\mathcal{S}$
with $\mathrm{dist}(s,s^{\prime})>2d$. The query may also return a positive
answer in case there are no $s,s^{\prime}$ as above, but then it is guaranteed
that the answer to the instance $(\mathcal{S},d)$ is negative.

Further, the data structure provides access to a special word $q\in\Sigma^{L}$
through the following methods:

  * •

$\mathtt{Reset}()$: Reset $q$ to the first word in $\mathcal{S}$.

  * •

$\mathtt{UpdateCandidate}(i,a)$: Change the $i$th position of $q$ to symbol
$a$.

  * •

$\mathtt{QueryFarWord}()$: Query if there exists $s\in\mathcal{S}$ with
$\mathrm{dist}(s,q)>d$, and if so, return the pointer to $s$ and the set of
positions where $s$ and $q$ differ.

Usage of the above requires the following promises:

  * •

Usage of $\mathtt{Reset}()$ must be preceded by obtaining a negative answer to
$\mathtt{QueryFarPair}()$.

  * •

Following resetting $q$ to $s\in\mathcal{S}$ through usage of
$\mathtt{Reset}()$, the user has to guarantee that the assertion
$\mathrm{dist}(q,s)\leqslant d$ will hold at all times till the next usage of
$\mathtt{Reset}()$.

  * •

Every update to any word in $\mathcal{S}$ resets $q$ to be undefined, so that
$\mathtt{Reset}()$ needs to be invoked again to enable operations on $q$.

Methods $\mathtt{QueryFarPair}()$, $\mathtt{Reset}()$,
$\mathtt{UpdateCandidate}()$, $\mathtt{QueryFarWord}()$ work in worst-case
time $2^{\mathcal{O}(d)}$. Queries $\mathtt{QueryFarPair}()$ and
$\mathtt{QueryFarWord}()$ return a false negative with probability
$2^{-\Omega(d)}$; there are no false positives.

A few remarks are in place regarding the use of randomness in the data
structure of Lemma 3.2. Namely, random bits are used solely in the
initialization of the data structure, and the correctness of subsequent uses
of query methods depends on those initial random bits. As a result, the events
that queries return correct answers are not independent, meaning that the
error probability cannot be improved in the standard way by repeating each
query many times. Instead, one can improve the error probability by setting up
multiple independent copies of the data structure of Lemma 3.2.

With Lemma 3.2 stated, we can show how to derive Theorem 3.1 from it.

###### Proof of Theorem 3.1 assuming Lemma 3.2.

We initialize and maintain $\alpha\log d$ independent copies of the data
structure provided by Lemma 3.2 for some large enough constant $\alpha$, to be
determined later. Each update and each query is accordingly relayed to all
these data structures; the output of a query is the disjunction of outputs
provided by the individual data structures. In this way, we may assume that we
have one instance of the data structure of Lemma 3.2 where the probability of
a false negative is reduced to $(2^{-\Omega(d)})^{\alpha\log
d}=(d^{-\Omega(d)})^{\alpha}$. The cost for this is that the running times of
all methods are increased by a multiplicative factor of $\mathcal{O}(\log d)$;
this will be immaterial in the forthcoming complexity analysis.

It remains to implement the query: we look for a word $c$ that is at Hamming
distance at most $d$ from all the words in $\mathcal{S}$. The idea is to run
Algorithm 1 with all operations replaced by suitable invocations of methods of
the data structure of Lemma 3.2. Lines 1 and 1 are replaced by invocations of
methods $\mathtt{QueryFarPair}()$ and $\mathtt{Reset}()$, respectively. In
line 1, we invoke method $\mathtt{QueryFarWord}()$. Finally, in line 1 we use
one $\mathtt{UpdateCandidate}()$ operation before recursing, and we roll-back
this update (using the $\mathtt{UpdateCandidate}()$ method again) when
returning from the recursion. The running time and the correctness (assuming
no false negatives from the data structure of Lemma 3.2) follow from the
correctness of the original static algorithm and Lemma 3.2. It is also easy to
verify that the promises required by the data structure of Lemma 3.2 are kept.

It remains to bound the probability of a false positive. Clearly, a false
positive might arise only if some invocation of a method of the data structure
of Lemma 3.2 returns a false negative. Since the recursion tree of procedure
$\mathtt{ClosestString}$() has depth at most $d$ and branching at most $3d$,
it has at most $2(3d)^{d}$ nodes, hence in total there are at most
$1+2(3d)^{d}$ invocations of methods of the data structure of Lemma 3.2. By
setting $\alpha$ large enough, we have
$(1+2(3d)^{d})\cdot(d^{-\Omega(d)})^{\alpha}\leqslant 2^{-\Omega(d)}$. So by
the union bound, the probability of an error is bounded by $2^{-\Omega(d)}$. ∎

Now, we discuss the technical ideas behind the proof of Lemma 3.2. The key
idea is that we can efficiently maintain an approximate solution, as explained
in the lemma below.

######  Lemma 3.3 (Approximate Closest String).

There exists a data structure that maintains a dictionary $\mathcal{S}$ of
words in $\Sigma^{L}$ with amortized update time $\mathcal{O}(|\Sigma|)$, as
well as a word $o\in\Sigma^{L}$ with the following guarantee: if the answer to
the Closest String instance $(\mathcal{S},d)$ is positive, then
$\mathrm{dist}(o,s)\leqslant 4|\Sigma|\cdot d$ for every $s\in\mathcal{S}$.
Data structure can be initialized in $\mathcal{O}(nL)$ time.

Moreover, the data structure also maintains the set
$\Delta(o,s)\coloneqq\\{i\in[L]\;|\;o[i]\neq s[i]\\}$ for every
$s\in\mathcal{S}$ and, upon request, can return $\Delta(o,s)$ in time
$\mathcal{O}(|\Delta(o,s)|)$. Finally, the data structure can check whether
$\mathrm{dist}(o,s)\leqslant 4|\Sigma|\cdot d$ for all $s\in\mathcal{S}$ in
time $\mathcal{O}(1)$.

In Section 3.2 we prove Lemma 3.3. Next, in Section 3.3 we use an approach
based on color coding to leverage Lemma 3.3 to a data structure achieving the
first part of Lemma 3.2: maintaining a dictionary $\mathcal{S}$ and
implementing query $\mathtt{QueryFarPair}()$. Adding the functionality
concerning the candidate word $q$ uses similar arguments and is presented in
Section 3.4. Looking at the statement of Lemma 3.3, the reader might be at
this point worried that this plan involves complexities dependent also on
$|\Sigma|$. However, in Section 3.3 we will show how to reduce $|\Sigma|$ to
$\mathcal{O}(d)$ using color coding.

###  3.2 Approximate Closest String

In this section we prove Lemma 3.3. The main idea is to define
$o\in\Sigma^{L}$ through an approximate majority vote for every position,
maintained in a lazy fashion. We formalize this through the following
definition.

######  Definition 3.4 (Origin Word).

An _origin word_ for a dictionary $\mathcal{S}$ of words in $\Sigma^{L}$ is a
word $o\in\Sigma^{L}$ such that

$|\left\\{s\in\mathcal{S}\;|\;s[i]=o[i]\right\\}|\geqslant\frac{|\mathcal{S}|}{2|\Sigma|}\text{
for every }i\in[L].$

We say that the origin word $o$ is _good_ if $\mathrm{dist}(o,s)\leqslant
4|\Sigma|\cdot d$ for every $s\in\mathcal{S}$.

By definition, if an origin word is good, then it is a solution for the
Closest String instance $(\mathcal{S},4|\Sigma|d)$. We now show a reverse
“soundness” implication: if some origin word is not good, then for sure there
is no solution for $(\mathcal{S},d)$.

######  Lemma 3.5.

If for an instance $(\mathcal{S},d)$ there exists an origin word that is not
good, then the answer to $(\mathcal{S},d)$ is negative.

###### Proof.

For the sake of contradiction, let us assume that there exists
$c\in\Sigma^{L}$ such that $\mathrm{dist}(c,s)\leqslant d$ for every
$s\in\mathcal{S}$. Moreover, there exists some origin word $o\in\Sigma^{L}$
and a witness $w\in\mathcal{S}$ such that $\mathrm{dist}(o,w)>4d|\Sigma|$.

Let $C_{o,w}$ be the total count of matches between $o$ and all words in
$\mathcal{S}$ at the positions where $o$ and $w$ differ. That is,

$C_{o,w}\coloneqq|\\{(i,s)\in[L]\times\mathcal{S}\;\text{ such that
}\;w[i]\neq o[i]\text{ and }s[i]=o[i]\\}|.$

Let us show a lower bound on $C_{o,w}$. Observe that for a witness
$w\in\mathcal{S}$ there are at least $\mathrm{dist}(o,w)$ positions $i$ that
are taken into account when computing $C_{o,w}$. Moreover, by the definition
of origin word $o$, for every position $i\in[L]$ at least
$|\mathcal{S}|/(2|\Sigma|)$ words match $o$ on position $i$. Therefore,

$\frac{|\mathcal{S}|\cdot\mathrm{dist}(o,w)}{2|\Sigma|}\leqslant C_{o,w}.$ (2)

On the other hand, we assumed that there exists $c\in\Sigma^{L}$ such that
$\mathrm{dist}(c,s)\leqslant d$ for every $s\in\mathcal{S}$. Since
$w\in\mathcal{S}$, by triangle inequality we have $\mathrm{dist}(s,w)\leqslant
2d$ for every $s\in\mathcal{S}$. Hence

$C_{o,w}\leqslant 2d\cdot|\mathcal{S}|.$ (3)

By combining (2) and (3) we conclude that $\mathrm{dist}(o,w)\leqslant
4|\Sigma|d$, a contradiction. ∎

Next, we argue that in $\mathcal{O}(|\Sigma|)$ time we can maintain some
origin word for a given dictionary.

######  Lemma 3.6.

In $\mathcal{O}(nL)$ time we can initialize a data structure that for a given
dictionary $\mathcal{S}$ of words in $\Sigma^{L}$ maintains some origin word
$o\in\Sigma^{L}$ with amortized update time $\mathcal{O}(|\Sigma|)$. The data
structure also maintains the set $\Delta(o,s)\coloneqq\\{i\in[L]\;|\;s[i]\neq
o[i]\\}$ for every $s\in\mathcal{S}$ and upon request, can return each set
$\Delta(o,s)$ in time $\mathcal{O}(|\Delta(o,s)|)$. Finally, the data
structure can check whether $o$ is good in time $\mathcal{O}(1)$.

###### Proof.

Upon initialization, we set $o\in\Sigma^{L}$ so that for every position
$i\in[L]$, $o[i]$ is a symbol that occurs the most often among $s[i]$ for
$s\in\mathcal{S}$. Clearly, $o$ constructed in this way is an origin word. We
also compute the relevant sets $\Delta(o,s)$.

The data structure stores the following additional data. For every position
$i\in[L]$ and every symbol $\alpha\in\Sigma$, we maintain a counter indicating
the number of words $s\in\mathcal{S}$ such that $s[i]=\alpha$. Each set
$\Delta(o,s)$ is stored as a linked list (with no assumption on the order),
plus there is an array of length $L$ whose $i$th entry is either null if
$i\notin\Delta(o,s)$, or contains a pointer to the relevant object on the
linked list representing $\Delta(o,s)$. Additionally, with each set
$\Delta(o,s)$ we maintain its size. Additionally, we store a single counter
indicating the number of words $s\in\mathcal{S}$ such that
$|\Delta(o,s)|\geqslant 4|\Sigma|d$. This counter can be used to answer
queries about the goodness of $o$ in time $\mathcal{O}(1)$. Upon
initialization, all of the above can be computed in time $\mathcal{O}(nL)$ in
a straightforward way.

We now explain how the data structure behaves upon an update. Suppose position
$s_{j}[i]$ is modified. We update the relevant counters for position $i$ and
update $\Delta(o,s_{j})$ accordingly. Next, we check whether the counter for
the symbol $o[i]$ at position $i$ did not drop below
$|\mathcal{S}|/(2|\Sigma|)$. If not, then $o$ remains an origin word and there
is no need to change $o$. Otherwise, we modify $o[i]$ as follows.

By iterating through all words in $\mathcal{S}$, we compute the most frequent
symbol among $s[i]$ for $s\in\mathcal{S}$, and we set $o[i]$ to be this
symbol. Moreover, we iterate over all $s\in\mathcal{S}$ and update
$\Delta(o,s)$ accordingly, by adding or removing the position $i$ if needed.
These operations require total time $\mathcal{O}(|\mathcal{S}|)$.

We now argue that the amortized update time is $\mathcal{O}(|\Sigma|)$. By the
pigeon-hole principle, when symbol $o[i]$ gets modified, it is replaced by a
symbol that occurs at least $|\mathcal{S}|/|\Sigma|$ times on position $i$ in
words from $\mathcal{S}$. Also, this is true for the symbol placed as $o[i]$
upon initialization. Therefore, before every update when $o[i]$ gets modified,
there are at least $|\mathcal{S}|/(2|\Sigma|)$ updates on position $i$ where
$o[i]$ was modified. We can charge the running time
$\mathcal{O}(|\mathcal{S}|)$ used when modifying $o[i]$ to those previous
updates, thus obtaining amortized update time $\mathcal{O}(|\Sigma|)$. ∎

Now Lemma 3.3 follows by combining Lemmas 3.6 and 3.5.

###  3.3 Detecting dissimilar words

In this section we prove the first part of Lemma 3.2: we present a data
structure that maintains the dictionary and implements the method
$\mathtt{QueryFarPair}()$, and for now we ignore the methods for handling $q$.

In the data structure, we will maintain hashes of all words in $\mathcal{S}$
to the binary alphabet. More precisely, upon initialization of the data
structure, we uniformly at random sample a function
$h\colon[L]\times\Sigma\rightarrow\\{0,1\\}$ that assigns a label $0$ or $1$
to every position and symbol in the alphabet. This function is fixed for the
whole life of the data structure and stored in it. In notation, we shall use a
natural lift of $h\colon\Sigma^{L}\rightarrow\\{0,1\\}^{L}$ that applies $h$
position-wise. In the data structure we store, together with $\mathcal{S}$,
the hashed dictionary $\widetilde{\mathcal{S}}\coloneqq\\{h(s)\colon
s\in\mathcal{S}\\}$. Observe that upon every update to $\mathcal{S}$ we can
also update $\widetilde{\mathcal{S}}$ in constant time.

We also maintain an approximate solution $o\in\\{0,1\\}^{L}$ for the
dictionary $\widetilde{\mathcal{S}}$ using the data structure of Lemma 3.3.
Recall that we can query the data structure of Lemma 3.3 about whether
$\mathrm{dist}(o,\tilde{s})\leqslant 8d$ for all
$\tilde{s}\in\widetilde{\mathcal{S}}$ and if this is not the case, then we
know for sure that the instance $(\widetilde{\mathcal{S}},d)$ of Closest
String has a negative answer. Note that this conclusion implies that the
original instance $(\mathcal{S},d)$ also has a negative answer.

In addition to the approximate solution $o$, the data structure of Lemma 3.3
provides an access to the sets $\Delta(o,\tilde{s})$ of positions where $o$
and $\tilde{s}$ differ, for all $\tilde{s}\in\widetilde{\mathcal{S}}$.

Finally, we also hash positions as follows. Upon initialization, we sample
uniformly at random a function $\pi\colon[L]\rightarrow[16d]$ which maps
positions to a set of $16d$ colors (numbers from $1$ to $16d$). Again, this
function is fixed for the whole life of the data structure and stored in it.
For a word $\tilde{s}\in\widetilde{\mathcal{S}}$, let
$\mathsf{colors}_{o,\pi}(s)=\\{\pi(i)\;|\;i\in[L]\textrm{ and }s[i]\neq
o[i]\\}$ be the set of colors assigned to the symbols in $\tilde{s}$ that are
on positions where $\tilde{s}$ does not match the origin word
$o\in\\{0,1\\}^{L}$.

In the data structure we maintain, for every $C\subseteq[16d]$, the set
$\Phi(C)$ defined as follows:

$\Phi(C)=\\{\tilde{s}\in\widetilde{\mathcal{S}}\;|\;\mathsf{colors}_{o,\pi}(\tilde{s})=C\\}.$

In other words, $\Phi(C)$ is the set of words from $\widetilde{\mathcal{S}}$
that get assigned color set $C$. The next statement shows that sets $\Phi(C)$
can be maintained in $2^{\mathcal{O}(d)}$ time per update.

######  Lemma 3.7.

We can initialize in $2^{\mathcal{O}(d)}\cdot nL$ time a data structure that
for every $C\subseteq[16d]$ maintains the set $\Phi(C)$ in amortized
$2^{\mathcal{O}(d)}$ time per update to $\mathcal{S}$. When queried about any
$C\subseteq[16d]$, the data structure in $\mathcal{O}(1)$ time either returns
any element from $\Phi(C)$, or asserts that $\Phi(C)$ is empty.

The proof of Lemma 3.7 is deferred to Appendix A. It is rather technical and
builds on the data structure of Lemma 3.3 by additionally storing sets
$\Phi(C)$ as doubly-linked lists. Every modification to
$\widetilde{\mathcal{S}}$ and $o$ triggers a number of modifications to lists
representing $\Phi(C)$, consisting of moving some elements from one list to
another. The same amortization argument as the one used in the proof of Lemma
3.3 shows that the amortized update time is $2^{\mathcal{O}(d)}$.

Method : $\mathtt{QueryFarPair}()$

1

2if  _it is not the case that $\mathrm{dist}(o,\tilde{s})\leqslant 8d$ for all
$\tilde{s}\in\widetilde{\mathcal{S}}$_ then

3 return Answer to $(\mathcal{S},d)$ is negative.

4for  _every $X,Y\subseteq[16d]$ with $|X\triangle Y|>2d$ _ do

5 if  _$\Phi(X)$ and $\Phi(Y)$ are both nonempty_ then

6 return There are words $s,s^{\prime}\in\mathcal{S}$ with
$\mathrm{dist}(s,s^{\prime})>2d$.

return It holds that $\mathrm{dist}(s,s^{\prime})\leqslant 2d$ for all
$s,s^{\prime}\in\mathcal{S}$.

Algorithm 2 Pseudocode for the method $\mathtt{QueryFarPair}()$.

We now present implementation of the query operation; see Algorithm 2 for a
pseudocode. We first check whether $\mathrm{dist}(o,\tilde{s})\leqslant 8d$
for all $\tilde{s}\in\widetilde{\mathcal{S}}$. As argued in Lemma 3.5, if this
is not the case, then we can safely conclude that the answer to the instance
$(\mathcal{S},d)$ is negative. Otherwise, we iterate over every pair of sets
$X,Y\subseteq[16d]$ with $|X\triangle Y|=|(X\setminus Y)\cup(Y\setminus
X)|>2d$. Then, we check whether both $\Phi(X)$ and $\Phi(Y)$ are nonempty. If
that is the case, then (as we will argue) any pair
$(\tilde{s},\tilde{s}^{\prime})\in\Phi(X)\times\Phi(Y)$ satisfies
$\mathrm{dist}(\tilde{s},\tilde{s}^{\prime})>2d$, implying that the original
words $s,s^{\prime}\in\mathcal{S}$ also satisfy
$\mathrm{dist}(s,s^{\prime})>2d$. Otherwise, if for every such $X$ and $Y$ at
least one of $\Phi(X)$ or $\Phi(Y)$ is empty, we conclude that there is no
pair $s,s^{\prime}\in\mathcal{S}$ with $\mathrm{dist}(s,s^{\prime})>2d$.

Because the number of pairs $X,Y\subseteq[16d]$ is $2^{\mathcal{O}(d)}$, the
query algorithm runs in $2^{\mathcal{O}(d)}$ time in total. The next lemma
shows that if the algorithm finds some pair of words and reports that they are
at distance larger than $2d$, then this answer is correct.

######  Lemma 3.8.

Suppose Algorithm 2 finds a pair $X,Y\subseteq[16d]$ with $|X\triangle Y|>2d$
and $\Phi(X)\neq\emptyset$ and $\Phi(Y)\neq\emptyset$. Then there are
$s,s^{\prime}\in\mathcal{S}$ such that $\mathrm{dist}(s,s^{\prime})>2d$.

###### Proof.

Consider any pair $(\tilde{s},\tilde{s}^{\prime})\in\Phi(X)\times\Phi(Y)$.
Observe that for every color $r\in X\setminus Y$, there is a position $i$ with
$\pi(i)=r$ such that $\tilde{s}[i]\neq o[i]$ (due to $r\in X$), and we have
$o[i]=\tilde{s}^{\prime}[i]$ (due to $r\notin Y$). So
$\tilde{s}[i]\neq\tilde{s}^{\prime}[i]$, implying $s[i]\neq s^{\prime}[i]$.
Similarly for every $r\in Y\setminus X$. Positions $i$ as above have to be
pairwise different due to receiving different colors in $\pi$, so we conclude
that $s$ and $s^{\prime}$ differ on more than $2d$ positions. ∎

To finish the proof, it remains to analyze the success probability of
Algorithm 2.

######  Lemma 3.9.

If there exists a pair $a,b\in\mathcal{S}$ with $\mathrm{dist}(a,b)>2d$, then
Algorithm 2 detects such a pair with the probability at least
$2^{-\mathcal{O}(d)}$, or concludes that the answer to the instance
$(\mathcal{S},d)$ is negative.

Note that in Lemma 3.2 we promised error probability bounded by
$2^{-\Omega(d)}$, while Lemma 3.9 provides a bound of $1-2^{-\mathcal{O}(d)}$
on the error probability. This can be easily remedied by maintaining
$2^{\Theta(d)}$ independent copies of the data structure. This increases the
time of update and initialization by a $2^{\mathcal{O}(d)}$ factor.

###### Proof of Lemma 3.9.

First, we argue that after hashing the alphabet, we still have
$\mathrm{dist}(h(a),h(b))>2d$ with sufficiently high probability. Let
$P\subseteq\\{i\in[L]\;|\;a[i]\neq b[i]\\}$ be any set of size exactly $2d+1$
consisting of positions where $a$ and $b$ differ.

Let $\tilde{a}=h(a)$ and $\tilde{b}=h(b)$. First, we claim that with
probability at least $2^{-\mathcal{O}(d)}$ it holds that
$\mathrm{dist}(\tilde{a},\tilde{b})>2d$. Observe that for a fixed position
$i\in P$, the probability that $h$ assigns different symbols to $a[i]$ and to
$b[i]$ is $1/2$. Since $h$ is sampled on each position $i\in[L]$
independently, the probability that this happens for all positions in $P$ is
$2^{-|P|}=2^{-\mathcal{O}(d)}$.

From now on, let us assume that $\mathrm{dist}(\tilde{a},\tilde{b})>2d$.
Moreover, by Line 2 we may assume that $\mathrm{dist}(o,\tilde{s})\leqslant
8d$ for every $\tilde{s}\in\widetilde{\mathcal{S}}$. Consider the set

$\Delta_{o}(\tilde{a},\tilde{b})\coloneqq\\{i\in[L]~{}|~{}\tilde{a}[i]\neq
o[i]\text{ or }\tilde{b}[i]\neq o[i]\\}.$

Observe that since $\mathrm{dist}(o,\tilde{a})\leqslant 8d$ and
$\mathrm{dist}(o,\tilde{b})\leqslant 8d$, we have
$k\coloneqq|\Delta_{o}(\tilde{a},\tilde{b})|\in[2d+1,16d]$. Now, we claim that
with probability $2^{-\mathcal{O}(d)}$ the function $\pi$ assigns different
colors to all positions in $\Delta_{o}(\tilde{a},\tilde{b})$. There are
$(16d)^{k}$ different colorings on $\Delta_{o}(\tilde{a},\tilde{b})$. However,
only $\binom{16d}{k}k!$ of them assign different colors to
$\Delta_{o}(\tilde{a},\tilde{b})$. Therefore the probability that $\pi$
assigns different colors on $\Delta_{o}(\tilde{a},\tilde{b})$ is:

$\Pr\left[|\\{\pi(i)\;|\;i\in\Delta_{o}(\tilde{a},\tilde{b})\\}|=k\right]=\frac{\binom{16d}{k}k!}{(16d)^{k}}=\frac{(16d)}{(16d)}\cdots\frac{(16d-k+1)}{(16d)}>\frac{(16d)!}{(16d)^{16d}}>e^{-16d}$

where the last inequality follows from the well-known bound $n!>(n/e)^{n}$.
Hence, the probability that $\pi$ assigns different colors to all positions in
$\Delta_{o}(\tilde{a},\tilde{b})$ is $2^{-\mathcal{O}(d)}$. Now, we claim that
if that indeed happens, then Algorithm 2 detects a suitable pair.

Let $X$ and $Y$ be sets of colors such that $\tilde{a}\in\Phi(X)$ and
$\tilde{b}\in\Phi(Y)$. It suffices to show that $|X\triangle Y|>2d$. Observe
that every position where $\tilde{a}$ and $\tilde{b}$ differ belongs to
$\Delta_{o}(\tilde{a},\tilde{b})$, hence these (more than $2d$) positions
receive different colors in $\pi$. Further, for every position where
$\tilde{a}$ and $\tilde{b}$ differ, the color of this position belongs to
$X\triangle Y$, for outside of positions of $\Delta_{o}(\tilde{a},\tilde{b})$
the words $o,\tilde{a},\tilde{b}$ all agree. It follows that $|X\triangle
Y|>2d$. ∎

###  3.4 Maintaining a candidate solution

In this section we finish the proof of Lemma 3.2 by implementing the
operations on the candidate word $q$. This proof builds upon the construction
from Section 3.3 using the same ideas, so we only briefly discuss the
additional elements that need to be maintained.

Observe that $q$ is always reset to the first word $s_{1}\in\mathcal{S}$ and
operations on $q$ are performed under the promise that
$\mathrm{dist}(q,s_{1})\leqslant d$ at all times. Therefore, we maintain $q$
implicitly by remembering only at most $d$ positions on which $s_{1}$ and $q$
differ, and what are the symbols of $q$ on those positions. This allows us to
implement the reset and update operations for $q$ in time
$2^{\mathcal{O}(d)}$. (Recall here that in Section 3.3 we in fact maintained
$2^{\mathcal{O}(d)}$ independent copies of the data structure in order to
boost the error probability.) Also, we maintain the hashed version
$\tilde{q}\coloneqq h(q)$.

The method $\mathtt{QueryFarWord}()$ is implemented using a similar mechanism
as was used in Section 3.3. For technical reasons, we extend the palette of
colors used by $\pi$ from $[16d]$ to $[17d]$. Then we maintain the sets
$\Phi(C)\subseteq\widetilde{\mathcal{S}}$ for $C\subseteq[17d]$ as before.
However, instead of iterating over all pairs $X,Y\subseteq[17d]$ with
$|X\triangle Y|>2d$, we first compute
$Q\coloneqq\mathsf{colors}_{o,\pi}(\tilde{q})$ and then iterate over all
$X\subseteq[17d]$ such that $|X\triangle Q|>d$ and check whether $\Phi(X)$ is
nonempty. The same reasoning as in Section 3.3 shows that if there exists
$s\in\mathcal{S}$ with $\mathrm{dist}(q,s)>d$, then with high enough
probability we will find such an $s$ as any element of $\Phi(X)$.

Note that in the description above we did not specify how the set
$\mathsf{colors}_{o,\pi}(\tilde{q})$ is computed. This can be done by first
obtaining the set $\Delta(o,\tilde{s}_{1})$ from the data structure of Lemma
3.3, and then inspecting all the positions of
$\Delta(o,\tilde{s}_{1})\cup\Delta(s_{1},q)$, where $\Delta(s_{1},q)$ are the
at most $d$ positions where $s_{1}$ and $q$ differ. Note here that we may
assume that $|\Delta(o,\tilde{s}_{1})|\leqslant 8d$, for otherwise the data
structure presented in Section 3.3 must have returned that the answer to
$(\mathcal{S},d)$ is negative when resetting $q$. Further, this reasoning
shows that $|\Delta(o,\tilde{q})|\leqslant 9d$ at all times. Note that in the
correctness argument presented in Section 3.3 we used the assumption that
$\mathrm{dist}(o,\tilde{a})\leqslant 8d$ and
$\mathrm{dist}(o,\tilde{b})\leqslant 8d$, and this is why we chose a palette
of colors of size $16d$. Now we have $\mathrm{dist}(o,\tilde{q})\leqslant 9d$
and $\mathrm{dist}(o,\tilde{s})\leqslant 8d$, so a palette of $17d$ colors
suffices.

It remains to argue that if $s$ with $\mathrm{dist}(q,s)>d$ is found, the set
$P$ of positions on which $q$ and $s$ differ can be reported in time
$\mathcal{O}(d)$. But again, $P$ can be constructed by inspecting all
positions of $\Delta(o,\tilde{s}_{1})\cup\Delta(q,s_{1})$, and this set has
size $\mathcal{O}(d)$ and can be obtained by a query to the data structure of
Lemma 3.3. This finishes the proof of Lemma 3.2.

###  3.5 Closest String for small alphabets

In this section we analyse the complexity of Closest String for small
alphabets and show that our techniques also apply in this setting. That is, we
prove the second half of Theorem 1.1, presented below.

######  Theorem 3.10.

The dynamic variant of Closest String admits a randomized data structure with
initialization time $2^{\mathcal{O}(d)}nL|\Sigma|^{1+o(1)}$, amortized update
time $2^{\mathcal{O}(d)}$, and worst-case query time
$(|\Sigma|-1)^{d}2^{\mathcal{O}(d)}$. The answer to each query may result with
a false negative with probability at most $2^{-\Omega(d)}$; there are no false
positives.

The strategy is exactly the same as in Section 3.1. First, we present a static
algorithm with running time $(|\Sigma|-1)^{d}\cdot
2^{\mathcal{O}(d)}\cdot(nL)^{\mathcal{O}(1)}$, which is essentially the
algorithm proposed by Ma and Sun [23]. Next, we show how to use Lemma 3.2 to
implement this static algorithm to the dynamic setting. The algorithm is
presented using pseudocode as Algorithm 3. We present it somewhat differently
than Ma and Sun in order to streamline the analysis of the dynamic variant.

Algorithm : $\mathtt{ClosestStringSmallAlphabet}$($\mathcal{S},d$)

1

2Set $F\coloneqq\emptyset$

3 Set $q$ to be the first word $s_{1}\in\mathcal{S}$

4 Set $b\coloneqq d$

5 while  _exists $s\in\mathcal{S}$ such that $\mathrm{dist}(s,q)>d$ _ do

6 Find $P\coloneqq\\{i\in[L]\text{ such that }s[i]\neq q[i]\\}\setminus F$

7 if  _$\mathrm{dist}(s,q) >2d$ or $P=\emptyset$_ then

8 return False

9 Guess $Q=\\{i\in P\text{ such that }c[i]\neq q[i]\\}$

10 // $c\in\Sigma^{L}$ denotes the sought solution

11 if  _$|Q| >b$ or $Q=\emptyset$_ then

12 return False

13 for  _$i\in Q$_ do

14 Guess $c[i]\in\Sigma\setminus\\{q[i]\\}$

15 Set $q[i]\coloneqq c[i]$

16 $F\coloneqq F\cup P$

17 $b\coloneqq\min(d-\mathrm{dist}(s,q),b-|Q|)$

18 if  _$b <0$_ then

19 return False

return True

Algorithm 3 Pseudocode of a $(|\Sigma|-1)^{d}\cdot
2^{\mathcal{O}(d)}\cdot(nL)^{\mathcal{O}(1)}$-time static algorithm for
Closest String. To get a dynamic data structure with query time
$(|\Sigma|-1)\cdot 2^{\mathcal{O}(d)}$, use Lemma 3.2 for operations on $q$.

The algorithm maintains three global values. The first one is a set
$F\subseteq[L]$ of _fixed indices_. The second one is a word $q\in\Sigma^{L}$
that is a candidate for the solution, which at the start is set to be any word
from $\mathcal{S}$. The third one is a budget $b\in\mathbb{N}$, initially set
to $d$.

We imagine the algorithm as a nondeterministic procedure that, having in mind
some solution $c\in\Sigma^{L}$, guesses parts of $c$ along the execution and
appropriately modifies $q$. The set $F$ is used to keep track of the positions
that are already assumed to be fixed as in $F$. As usual, nondeterministism is
determined by branching over all possibilities, and the total number of
branches determines the running time of the algorithm. At every point, even in
branches where guesses were inconsistent with $c$, the algorithm maintains the
following invariant:

  1. $(\diamondsuit)$

There is $s\in\mathcal{S}$ such that $s[\overline{F}]=q[\overline{F}]$ and
$b=d-\mathrm{dist}(q[F],s[F])$, where we denote $\overline{F}=[L]\setminus F$.

In this way, one may think of $b$ as of the budget that is left for changing
symbols positions in $q$ outside of $F$: at most $b$ of them can be still
changed, for otherwise the solution would be too far from $s$.

Every step of the algorithm works as follows. First, we find a word
$s\in\mathcal{S}$ with $\mathrm{dist}(s,q)>d$. If no such word exists, then
the current candidate $q$ is a solution and we can terminate the procedure
claiming a positive answer. Otherwise, we compute the set $P$ of positions
where $s$ and $q$ differ, and we remove from it all positions that were fixed
before.

Next, we check whether $\mathrm{dist}(s,q)>2d$, which translates to the
condition $\mathrm{dist}(s[F\cup P],q[F\cup P])>2d$. If this is the case, we
terminate and provide a negative answer: there is no way to obtain a word at
distance at most $d$ from $s$ by changing at most $d$ positions in $q$. If
$P=\emptyset$, we can also terminate and provide a negative answer: already on
fixed positions, our candidate $q$ and $s$ differ by more than $d$. Otherwise,
when $\mathrm{dist}(s,q)\leqslant 2d$ and $P\neq\emptyset$, we guess exactly
the symbols in $c$ at positions from $P$ and we modify $q$ to have
$q[P]=c[P]$. This is done through a two-stage process: first we guess the set
of positions $Q\subseteq P$ where $q$ needs to be modified, and then we guess
the symbols of $c$ at positions of $Q$; for each there are $|\Sigma|-1$
possibilities. Note that we may restrict attention to sets $Q$ that are
nonempty (for $\mathrm{dist}(s,q)>d$) and satisfy $|Q|\leqslant b$ (by
invariant $(\diamondsuit)$ ‣ 3.5). Finally, we add $P$ to the set $F$ of fixed
indices and update $b$ to the minimum of the two values:
$d-\mathrm{dist}(s,q)$ and $b-|Q|$. It is straightforward to verify that this
way invariant $(\diamondsuit)$ ‣ 3.5 is still maintained: either $s$ or the
previous witness for $(\diamondsuit)$ ‣ 3.5 may serve as the new witness for
$(\diamondsuit)$ ‣ 3.5. Clearly, if $b$ became negative, it is safe to
terminate the branch. Otherwise we continue the search until a candidate $q$
at distance at most $d$ from all strings in $\mathcal{S}$ is found.

This concludes the description of the algorithm. The correctness is clear from
the description as we return True only if our candidate is at the distance at
most $d$ from all input strings.

It is now straightforward to turn this algorithm into a dynamic data structure
just as we did in the proof of Theorem 3.1. Namely, we maintain the data
structure of Lemma 3.2, and use it to operate on the candidate word $q$. All
distance checks can be implemented in linear time by verifying the
$\mathcal{O}(d)$-sized difference sets provided by this data structure. We
will later show that the whole recursion tree of Algorithm 3 has total size at
most $(|\Sigma|-1)^{d}\cdot 2^{\mathcal{O}(d)}$. Hence, as the operations in
the data structure of Lemma 3.2 take amortized time $2^{\mathcal{O}(d)}$, the
complexity guarantees promised in Theorem 3.10 follow in the same way as it
was the case for Theorem 3.1. As for the error probability, we can maintain
$\alpha\cdot\log|\Sigma|$ independent copies of the data structure of Lemma
3.2 for some large constant $\alpha$, so that the probability that this
composite data structure returns a false negative is reduced to
$(|\Sigma|^{-\Omega(d)})^{\alpha}$. Then, just as in the proof of Theorem 3.1,
it follows from the union bound that the probability of a false negative in
Algorithm 3 is at most $2^{-\Omega(d)}$.

We are left with bounding the running time of Algorithm 3, or more precisely,
showing that the whole recursion tree has size at most $(|\Sigma|-1)^{d}\cdot
2^{\mathcal{O}(d)}$. The argument conceptually follows the reasoning of Ma and
Sun [23]; we present it for completeness.

#### Runtime

The key observation is the following lemma.

######  Lemma 3.11.

Consider $i$th iteration of the while loop in Algorithm 3 (with any guesses
made). Let $b_{i}$ be the value of $b$ before this iteration, and $b_{i+1}$ be
the value of $b$ after this iteration. Then $b_{i+1}\leqslant b_{i}/2$.

We first argue that the claimed runtime of Algorithm 3 follows from Lemma
3.11. Consider any root-to-leaf path in the recursion tree of the algorithm;
this corresponds to a single run of Algorithm 3 treated as a nondeterministic
procedure, with some guesses made along the way. For iterations
$i=1,2,\ldots,p$ of the while-loop, where $p$ is the total number of
iterations made, let $b_{i}$ be the value of $b$ at the beginning of the $i$th
iteration, and let $\ell_{i}$ be the size of the set $Q$ considered in the
$i$th iteration. Observe the following:

  * •

We have $b_{i}\leqslant d/2^{i-1}$ for all $i\in[p]$ (because $b_{1}=d$ and,
by Lemma 3.11, $b_{i+1}\leqslant b_{i}/2$ for all $i\in[p-1]$).

  * •

We have $1\leqslant\ell_{i}\leqslant b_{i}$ for all $i\in[p]$ (because in the
algorithm we consider only nonempty sets $Q$ satisfying $|Q|\leqslant b$).

  * •

We have $\sum_{i=1}^{p}\ell_{i}\leqslant d$ (because $b$ decreases by at least
$\ell_{i}$ in the $i$th iteration, and the procedure terminates once $b$
becomes negative).

Therefore, every root-to-leaf path in the recursion tree can be uniquely
described by specifying the following data:

  1. (A)

Positive integers $\ell_{1},\ldots,\ell_{p}$ satisfying
$\sum_{i=1}^{p}\ell_{i}\leqslant d$.

  2. (B)

For each $i\in[p]$, a choice of a subset $Q_{i}$ of size $\ell_{i}$ of the set
$P_{i}$, where $P_{i},Q_{i}$ are the sets $P,Q$ considered in the $i$th
iteration.

  3. (C)

For each $i\in[p]$, a choice of symbols guessed to be fixed at the positions
of $Q_{i}$.

For (A), it is well-known that the number of representations of $d$ as a sum
of numbers $\ell_{1},\ldots,\ell_{p}$ is bounded by $2^{\mathcal{O}(d)}$. For
(C), the total number of choices is bounded by

$\prod_{i=1}^{p}(|\Sigma|-1)^{\ell_{i}}\leqslant(|\Sigma|-1)^{d}.$

Finally, for (B) we shall use the following known bound.

######  Lemma 3.12 (cf. Lemma 124 in [37]).

If $m,k$ are nonnegative integers, then $\binom{m+k}{k}\leqslant
2^{2\sqrt{xy}}$.

Since we always have $|P_{i}|\leqslant 2d$, the number of choices for (B) is
bounded as follows:

$\prod_{i=1}^{p}\binom{2d}{\ell_{i}}\leqslant\prod_{i=1}^{p}2^{2\sqrt{2d\ell_{i}}}\leqslant\prod_{i=1}^{p}2^{2\sqrt{2d\cdot
d/2^{i-1}}}=2^{2\sqrt{2}\cdot
d\cdot\sum_{i=0}^{\infty}2^{-i/2}}=2^{\mathcal{O}(d)}.$

So all in all, the total number of root-to-leaf paths in the recursion tree is
bounded by

$2^{\mathcal{O}(d)}\cdot
2^{\mathcal{O}(d)}\cdot(|\Sigma|-1)^{d}=(|\Sigma|-1)^{d}\cdot
2^{\mathcal{O}(d)},$

as claimed.

It remains to prove the Lemma 3.11.

###### Proof of Lemma 3.11.

Let $q_{i}$ and $q_{i+1}$ be the candidate word respectively at the beginning
and at the end of the $i$th iteration, that is, after guessing is performed.

Recall that there is $s\in\mathcal{S}$ with $\mathrm{dist}(s,q_{i})>d$.
Further, recall that

$b_{i+1}=\min(d-\mathrm{dist}(s,q_{i+1}),b_{i}-|Q|).$

To prove that $b_{i+1}\leqslant b_{i}/2$, it suffices to show that

$(d-\mathrm{dist}(s,q_{i+1}))+(b_{i}-|Q|)\leqslant b_{i},$

or equivalently,

$d\leqslant\mathrm{dist}(s,q_{i+1})+|Q|.$ (4)

By triangle inequality we have

$d<\mathrm{dist}(s,q_{i})\leqslant\mathrm{dist}(s,q_{i+1})+\mathrm{dist}(q_{i},q_{i+1}),$

but we also have

$\mathrm{dist}(q_{i},q_{i+1})=|Q|.$

So this establishes (4) and finishes the proof. ∎

##  4 Applications of Meta-Theorems

In this section we first state a meta-theorem for string problems definable in
first-order logic $\mathsf{FO}$; this result follows easily from the work of
Frandsen et al. [20] using the classic Schützenberger-McNaughton-Papert
theorem [33, 38]. Then we explain how to use the meta-theorem for the
following toy problems: Disjoint Factors and Edit Distance. As usual with
meta-theorems, the parametric factor in the complexity guarantees of the
obtained data structures is not explicit, and typically is much higher than if
one constructs the data structure “by hand”. Therefore, we next show how to
derive concrete data structures with concrete complexity guarantees for
Disjoint Factors and Edit Distance. Finally, we discuss a methodology for
lower bounds introduced by Amarilli et al. [4], and we apply it to derive
lower bounds for those two problems.

###  4.1 A meta-theorem

We first need to recall basic knowledge on different equivalent views on
regular languages. This material is standard in the area of algebraic theory
of languages, so we refer an interested reader to the book of Bojańczyk [13]
for a broader introduction. In particular, we explain the contemporary
understanding of the material, and for appropriate references and historical
remarks, we refer to [13].

The first view is through the lens of logic. Fix a finite alphabet $\Sigma$.
We consider the logic $\mathsf{MSO}[\Sigma,<]$ operating on words. In this
logic there are variables for single positions (denoted with small letters)
and subsets of positions (denoted with capital letters). The atomic formulas
are of the following form:

  * •

equality test $x=y$;

  * •

test $x\in X$ checking that position $x$ belongs to position subset $X$;

  * •

for every $a\in\Sigma$, test $a(x)$ checking that at position $x$ there is
symbol $a$; and

  * •

test $x<y$ checking that position $x$ appears before position $y$.

Formulas of $\mathsf{MSO}[\Sigma,<]$ can be obtained from atomic formulas
using standard boolean connectives and quantification (both universal and
existential, and applicable to both types of variables).
$\mathsf{FO}[\Sigma,<]$ is a fragment of $\mathsf{MSO}[\Sigma,<]$ where we
disallow variables for subsets of positions.

A sentence is a formula without free variables. By $w\models\varphi$ we mean
that the sentence $\varphi$ is satisfied in the word $w$. For a sentence
$\varphi\in\mathsf{MSO}[\Sigma,<]$, the language defined by $\varphi$ consists
of all words $w$ in which $\varphi$ is satisfied. A language
$L\subseteq\Sigma^{\star}$ is $\mathsf{MSO}$-definable if $L$ is defined by
some $\varphi\in\mathsf{MSO}[\Sigma,<]$ as above, and $\mathsf{FO}$-definable
if it is defined by some $\varphi\in\mathsf{FO}[\Sigma,<]$. It appears that
regular languages exactly coincide with ones definable in $\mathsf{MSO}$.

######  Theorem 4.1.

A language of finite words over a finite alphabet is regular if and only if it
is $\mathsf{MSO}$-definable.

The next view is through semigroup homomorphisms. Consider a language
$L\subseteq\Sigma^{\star}$. By endowing $\Sigma^{\star}$ with the
concatenation operation we can regard it as a semigroup. For another semigroup
$S$ and a (semigroup) homomorphism $h\colon\Sigma^{\star}\to S$, we say that
$h$ recognizes $L$ if there exists $A\subseteq S$ such that $L=h^{-1}(A)$; in
other words, whether $w\in L$ can be recognized by looking at $h(w)$ and
determining whether it belongs to $A$. It turns out that regular languages are
also exactly those that are recognized by homomorphisms to finite semigroups.

######  Theorem 4.2.

A language of finite words over a finite alphabet is regular if and only if it
is recognized by a homomorphism to a finite semigroup.

Further, it is known that if $L$ is regular, then there exists a unique
minimal — in terms of cardinality — semigroup $S$ such that there is a
homomorphism from $\Sigma^{\star}$ to $S$ recognizing $L$. This semigroup is
called the syntactic semigroup for $S$.

It turns out that $\mathsf{FO}$-definable languages can be characterized in
terms of algebraic properties of their syntactic semigroups. Here, a semigroup
is aperiodic (or group-free) if it does not contain any non-trivial group.

######  Theorem 4.3 (Schützenberger-McNaughton-Papert Theorem, [33, 38]).

A regular language $L$ is $\mathsf{FO}$-definable if and only if its syntactic
semigroup is aperiodic.

With these standard tools recalled, we can proceed to the setting of dynamic
data structures.

Fix a finite alphabet $\Sigma$ and consider a language
$L\subseteq\Sigma^{\star}$. The word problem for $L$ is to design a data
structure that maintains a dynamic word $w\in\Sigma^{\star}$ and supports the
following operations:

  * •

$\mathsf{init}(w)$: Initialize the data structure with the given word $w$.

  * •

$\mathsf{update}(i,a)$: Update $w$ by replacing the symbol at position $i$ by
symbol $a\in\Sigma$.

  * •

$\mathsf{query}()$: Determine whether $w\in L$.

The complexity guarantees of such a data structure is typically measured in
terms of $n:=|w|$. Note that this value is fixed upon initialization and then
stays the same throughout the life of the data structure.

We can also consider the word problem for semigroups. Suppose $S$ is a
semigroup. Then the word problem for $S$ is defined as above for words over
$S$ (that is, words $w\in S^{\star}$), where query is redefined as follows:
Output the (left-to-right) product of all the symbols in $w$.

Observe that the word problem for a regular language
$L\subseteq\Sigma^{\star}$ easily reduces to the word problem for its
syntactic semigroup $S$. Indeed, if $h\colon\Sigma^{\star}\to S$ is the
homomorphism recognizing $L$, say $L=h^{-1}(A)$ for some $A\subseteq S$, then
in the reduction we can map symbols $a\in\Sigma$ to their images $h(a)\in S$,
and whether $w\in L$ can be deduced by checking whether $h(w)\in A$.

Frandsen et al. [20] proposed an efficient dynamic data structure for the word
problem in aperiodic semigroups.

######  Theorem 4.4 ([20]).

Let $S$ be a finite aperiodic semigroup. Then there is a data structure for
the word problem for $S$ with initialization time $\mathcal{O}(n)$, worst-case
update time $\mathcal{O}(\log\log n)$, and worst-case query time
$\mathcal{O}(1)$.

By combining Theorems 4.3 and 4.4 using the reduction presented above, we
obtain the following.

######  Theorem 4.5.

Let $\Sigma$ be a finite alphabet and suppose $L\subseteq\Sigma^{\star}$ is
$\mathsf{FO}$-definable. Then there is a data structure for the word problem
for $L$ with initialization time $\mathcal{O}(n)$, worst-case update time
$\mathcal{O}(\log\log n)$, and worst-case query time $\mathcal{O}(1)$.

A few remarks are in order. First, the proof of Theorem 4.4 relies on
induction on the Khron-Rhodes decomposition of the semigroup $S$, where in
each step of the induction one applies van Emde Boas trees [41]. The induction
has depth bounded by the size of $S$, so one can view this data structure as
$\mathcal{O}(|S|)$ van Emde Boas trees stacked “on top of each other”.
Consequently, the constants hidden in the $\mathcal{O}(\cdot)$ notation in
Theorem 4.4 depend on $S$, but not horribly: they are polynomial in $|S|$.
However, there is a much more significant complexity blow-up hidden in Theorem
4.2. Specifically, if a regular language $L$ is defined by an
$\mathsf{FO}[\Sigma,<]$ sentence $\varphi$, then the syntactic semigroup of
$L$ has size bounded by a function of $|\varphi|$, but this function is in
general non-elementary — it is basically a tower of height equal to the
quantifier rank of $\varphi$. This non-elementary dependence is known to be
unavoidable [39]. Therefore, whenever one applies Theorem 4.5 in order to
obtain data structures for a problem based on its description in
$\mathsf{FO}$, one should bear in mind that the constants hidden in the
$\mathcal{O}(\cdot)$ notation depend non-elementarily on the length of the
description.

Second, recently Amarilli et al. [4] gave a characterization of regular
languages for which data structures with guarantees as in Theorem 4.4 exist.
This characterization renders the tractability region to be a bit broader than
just $\mathsf{FO}$-definability, for instance the languages “on every even
position there is symbol $a$” or “in total there is an even number of symbols
$a$” are not $\mathsf{FO}$-definable, but admit data structures for the word
problem with constant update time. The characterization is expressed in
algebraic terms and we could not find natural examples of parameterized string
problems that would not be $\mathsf{FO}$-definable, but fall under the
characterization. So we refrain from giving more details and point an
interested reader to [4] instead.

We now explain how to use Theorem 4.5 in practice on two examples: Disjoint
Factors and Edit Distance. In each case, the task boils down to defining the
problem in $\mathsf{FO}[\Sigma,<]$ for an appropriate alphabet $\Sigma$. We
start with Disjoint Factors.

######  Lemma 4.6.

Let $k\in\mathbb{N}$ and $\Sigma_{k}=[k]$. There is a sentence
$\varphi_{k}\in\mathsf{FO}[\Sigma_{k},<]$, computable from $k$, such that for
every $w\in\Sigma_{k}^{\star}$, $w$ is a yes-instance of Disjoint Factors for
parameter $k$ if and only if $w\models\varphi_{k}$.

###### Proof.

In the sentence $\varphi_{k}$, we first make a disjunction over all
permutations $\pi\colon[k]\to[k]$. For each such $\pi$, we verify that there
exist positions $x_{1}<y_{1}<x_{2}<y_{2}<\ldots<x_{k}<y_{k}$ such that for
each $i\in[k]$, both at position $x_{i}$ and at $y_{i}$ there is symbol
$\pi(i)$. It is straightforward to express this condition using an
$\mathsf{FO}[\Sigma_{k},<]$ sentence. ∎

By applying Theorem 4.5 to the language defined by sentence $\varphi_{k}$
provided by Lemma 4.6, we obtain the following.

######  Corollary 4.7.

There is a data structure for the dynamic Disjoint Factors problem with
initialization time $\mathcal{O}_{k}(n)$, worst-case update time
$\mathcal{O}_{k}(\log\log n)$, and query time $\mathcal{O}(1)$.

Note here that the query time can be a constant independent of $k$, as we can
always recompute the answer to the query following every update.

For Edit Distance, the formula is more complicated. For two words
$u,v\in\Sigma^{\star}$, by $u\otimes v$ we denote the word over
$(\Sigma\cup\\{\bot\\})^{2}$, where $\bot$ is a symbol not present in
$\Sigma$, defined as follows:

  * •

The length of $u\otimes v$ is $\max(|u|,|v|)$.

  * •

For each $1\leqslant i\leqslant\min(|u|,|v|)$, we put $u\otimes
v[i]=(u[i],v[i])$.

  * •

For each $\min(|u|,|v|)<i\leqslant\max(|u|,|v|)$, we put $u\otimes
v[i]=(u[i],\bot)$ or $u\otimes v[i]=(\bot,v[i])$, depending on whether
$\max(|u|,|v|)=|u|$ or $\max(|u|,|v|)=|v|$.

######  Lemma 4.8.

Let $k\in\mathbb{N}$ and $\Sigma$ be a finite alphabet. There is a sentence
$\psi_{k,\Sigma}\in\mathsf{FO}[(\Sigma\cup\\{\bot\\})^{2},<]$, computable from
$k$ and $\Sigma$, such that for all $u,v\in\Sigma^{\star}$, we have
$\mathsf{ed}(u,v)\leqslant k$ if and only if $u\otimes
v\models\psi_{k,\Sigma}$.

###### Proof.

Denote $\Gamma=(\Sigma\cup\\{\bot\\})^{2}$ for brevity. Note that for two
words $u^{\prime},v^{\prime}\in\Sigma^{\star}$ we have
$\mathsf{ed}(u^{\prime},v^{\prime})\leqslant k$ if and only if there exist
integers $a,b,c\geqslant 0$ with $a+b+c\leqslant k$ such that one can remove
$a$ positions from $u^{\prime}$ and $b$ positions from $v^{\prime}$ so that
the resulting strings have equal length and differ on exactly $c$ positions.
In such case, we will call the pair $(u^{\prime},v^{\prime})$
$(a,b,c)$-editable.

For all $(a,b,c)\in\\{0,1,\ldots,k\\}^{3}$ with $a+b+c\leqslant k$ and
$s,t\in\\{-k,\ldots,k\\}$, we shall construct a formula
$\alpha_{s,t,a,b,c}(x,y)$ that satisfies the following: for two positions
$1\leqslant x\leqslant y\leqslant\max(|u|,|v|)$, we have

$u\otimes v\models\alpha_{s,t,a,b,c}(x,y)\qquad\textrm{if and only
if}\qquad(u[x:y],v[x+s:y+t])\textrm{ is }(a,b,c)\textrm{-editable.}$

Here, we use the convention that if the specified range $[x:y]$ or $[x+s:y+t]$
does not fit into the corresponding word, or makes no sense due to $x>y+1$ or
$x+s>y+t+1$, then $\alpha_{s,t,a,b,c}(x,y)$ should be false (this can be
easily recognized in $\mathsf{FO}[\Gamma,<]$). If we achieve the above, the
formula $\psi_{k,\Sigma}$ can be defined as the disjunction of all formulas
$\alpha_{0,t,a,b,c}(1,n_{u})$ for $a,b,c$ as above, where $1$ is the first
position, $n_{u}$ is the last position of $u$, and $t\in\\{-k,\ldots,k\\}$ is
such that $n_{u}+t$ is the last position of $v$ (all these are easily
definable from $u\otimes v$ in $\mathsf{FO}[\Gamma,<]$).

The construction is by induction on $a+b$. For the base case $a=b=0$, we may
define $\alpha_{s,t,0,0,c}(x,y)$ as follows: if $s\neq t$ then the formula is
always false, and otherwise it checks whether there are exactly $c$ different
positions $z$ such that $x\leqslant z\leqslant y$ and $u[z]\neq v[z+s]$. This
can be checked by comparing the first coordinate of $u\otimes v[z]$ with the
second coordinate of $u\otimes v[z+s]$. Since $|s|\leqslant k$ by assumption,
it is straightforward to formulate this assertion in $\mathsf{FO}[\Gamma,<]$.

We proceed to the induction step. So assume $a+b>0$, say $a>0$; the
construction in the case $b>0$ is analogous, so we omit it. The idea is that
we guess, by existential quantification, the first position in $u[x:y]$ that
gets removed, and use simpler formulas given by the induction assumption. More
precisely, $\alpha_{s,t,a,b,c}(x,y)$ can be defined as the conjunction of
formulas

$\exists z.\left(x\leqslant z\leqslant
y\wedge\alpha_{s,r,0,b_{1},c_{1}}(x,z-1)\wedge\alpha_{r-1,t,a-1,b_{2},c_{2}}(z+1,y)\right),$

for all integers $b_{1},b_{2}\geqslant 0$ with $b_{1}+b_{2}=b$,
$c_{1},c_{2}\geqslant 0$ with $c_{1}+c_{2}=c$, and $r\in\\{-k+1,\ldots,k\\}$.
Here, $z-1$ and $z+1$ are a syntactic sugar for the predecessor and the
successor of $z$, respectively, which are easily definable in
$\mathsf{FO}[\Gamma,<]$. It is straightforward to see that the construction of
$\alpha_{s,t,a,b,c}(x,y)$ as above satisfies the required properties. ∎

Similarly as before, by combining Theorem 4.5 with Lemma 4.8 we obtain the
following.

######  Corollary 4.9.

There is a data structure for the dynamic Edit Distance problem with
initialization time $\mathcal{O}_{k,\Sigma}(n)$, worst-case update time
$\mathcal{O}_{k,\Sigma}(\log\log n)$, and query time $\mathcal{O}(1)$.

##  5 Improved data structures

In the Section 4, we showed that powerful meta-theorem seamlessly guarantee
$\mathcal{O}_{k}(\log\log n)$ worst-case update time for dynamic versions of
Disjoint Factors and Edit Distance. Now, we illustrate that the dependence on
$k$ can be significantly improved by exploiting combinatorial structure of
this problems. In the Section 5.1 we give an improved dependence for Disjoint
Factors and in Section 5.2 we present a data structure for Edit Distance.

###  5.1 $k$-Disjoint Factors

######  Lemma 5.1.

There is a data structure for the dynamic Disjoint Factors problem with
initialization time $\mathcal{O}(kn)$, worst-case update time
$\mathcal{O}(\log\log n)$, and query time $\mathcal{O}(k2^{k}\log\log n)$.

As a by product we also present an improved $\mathcal{O}(k2^{k}+kn)$ time
algorithm for static version of Disjoint Factors problem. This improves an
$\mathcal{O}(k2^{k}n)$ time algorithm due to Bodlaender et al. [12].

######  Corollary 5.2.

Disjoint Factors can be statically solved in $\mathcal{O}(k2^{k}+kn)$ time.

We calculate the solution to the Disjoint Factors with dynamic programming.
The entries of the dynamic programming are parameterized by sets
$S\subseteq\Sigma$. For each entry, we store a minimal integer $\ell\in[n]$,
such that a word $w[1:\ell]$ can be represented as disjoint factors with
letters from $S$.

We compute the entries of the dynamic programming in the bottom-up fashion. In
the base case $S=\emptyset$ the answer is $\ell=1$. When $S$ is nonempty, we
guess a letter $s\in S$. Next, we determine the position of $\ell_{s}$ for set
$S\setminus\\{s\\}$. Then, we look for the first $s$-factor after position
$\ell_{s}$ in the word and return the position of its right-endpoint. We
summarize is as follows:

${\mathtt{DF}}[S]:=\begin{cases}\min_{s\in S}\left\\{\text{next
}s\text{-factor after }\mathtt{DF}[S\setminus\\{s\\}]\right\\}&\text{if
}S\neq\emptyset,\\\ 1&\text{otherwise}.\end{cases}$

For correctness, observe that every optimal solution to Disjoint Factor can be
represented as a permutation $\pi:[k]\rightarrow[k]$ that corresponds to the
order in which each factor appears in the word. Moreover, if the solution to
Disjoint Factor that is represented by permutation $\pi$ exists, then it can
be detected by greedily taking subsequent factors in the word (cf., [12]).

Now, we focus on the exact implementation of determining a next factor after
position $\ell$.

###### Proof of Corolary 5.2.

It remains to show that there exists a data-structure that can be initialized
in $\mathcal{O}(kn)$ time and can answer queries of the form
$(s,\ell)\in\Sigma\times[n]$. The query returns a position of the first right-
endpoint of $s$-factor in the word $w[\ell:n]$. To achieve this, we store the
table $\mathtt{next}[s,\ell]$ for every $s\in\Sigma_{k}$ and $\ell\in[n]$. It
stores the minimal position of a letter $s\in\Sigma_{k}$ in the word
$w[\ell:n]$. To compute $\mathtt{next}[s,\ell]$ for a fixed $s\in\Sigma_{k}$,
we fill it starting from $\ell$ equal to $n$ down to $1$. Initially
$\mathtt{next}[s,n]=\infty$ for every $s\in\Sigma_{k}$. If $w[\ell]=s$, then
we set $\mathtt{next}[s,\ell]=\ell$. Otherwise, we know that the next position
of a letter $s$ is after $\ell$ and we set the value of the table
$\mathtt{next}$ at $s$ and $\ell$ to $\mathtt{next}[s,\ell+1]$.

Therefore, to find the position of next $s$-factor after position $\ell$ we
lookup the value of $\ell^{\prime}:=\mathtt{next}[s,\ell]$. This means that
next $s$-factor starts at position $\ell^{\prime}$. We return the position of
$\mathtt{next}[s,\ell^{\prime}]$ as the right-endpoint of this $s$-factor.

Observe, that we can compute table $\mathtt{next}$ in time $\mathcal{O}(kn)$.
Moreover, each $\mathtt{next}$ query takes $\mathcal{O}(1)$ time. Hence, with
$\mathtt{DF}$ procedure we can solve Disjoint Factor in
$\mathcal{O}(k2^{k}+kn)$ time. ∎

###### Proof of Lemma 5.1.

In the dynamic setting, we need to show that for every $s\in\Sigma_{k}$ and
$\ell\in[n]$ the position of a next $s$-factor after position $\ell$ can be
found in $\mathcal{O}(\log\log n)$ time. To achieve that, for every letter
$s\in\Sigma_{k}$ we maintain a van Emde Boas tree $\mathcal{T}_{s}$. In the
data structure, $\mathcal{T}_{s}$ stores the positions of a letter $s$ in the
updated word. Note, that a single update to $\mathcal{T}_{s}$ can be done in
$\mathcal{O}(\log\log n)$ time. During query, for a given $s\in\Sigma_{k}$ and
$\ell\in[n]$ we can ask for the next position of a letter $s$ after $\ell$. A
single query to van Emde Boas tree takes $\mathcal{O}(\log\log n)$ times.

Similarly to the proof of Corollary 5.2, we can use $\mathcal{T}_{s}$ to find
a position of $s$-factor after a given position in $\mathcal{O}(\log\log n)$,
with two queries to $\mathcal{T}_{s}$. Observe, that during an update to
Disjoint Factor we need to update only two van Emde Boas trees. Hence update
takes $\mathcal{O}(\log\log n)$ time. Moreover, $\mathtt{DF}$ procedure can
answer queries to Disjoint Factor in $\mathcal{O}(k2^{k}\log\log n)$ time. ∎

###  5.2 Edit Distance

######  Lemma 5.3.

There is a data structure for the dynamic Edit Distance problem with
initialization time $\mathcal{O}(kn)$, worst-case update time
$\mathcal{O}(k\log\log n)$, and query time $\mathcal{O}(k^{2}\log\log n)$.

The data structure is based on the classical result of Landau and Vishkin [28]
who gave a static $\mathcal{O}(n+k^{2})$ time algorithm for $k$-Edit Distance
problem. Our simple observation is that $\mathsf{LCE}$-queries in their
algorithm can be efficiently maintained with van Emde Boas trees.

Before we proceed with the proof of Lemma 5.3 let us recall the definition of
_Longest Common Extension_ query. Let $x,y$ be two strings of length at most
$n$. We define $\mathsf{LCE}(i,j)$ as the largest integer $\ell\in[n]$, such
that $x[i:i+\ell]=y[j:j+\ell])$. We show, that with van Emde Boas data
structure, we can efficiently maintain an answer to the $\mathsf{LCE}$ queries
when $|i-j|$ is small.

######  Proposition 5.4 (Dynamic $\mathsf{LCE}$-queries).

For any $k\in\mathbb{N}$, there is a data structure that maintains words
$x,y\in\Sigma^{n}$ and supports the following operations:

  * •

$\mathsf{init}(x,y)$: Initialize the data structure with the given words
$x,y$,

  * •

$\mathsf{update}(w,i,s)$: Update a word $w\in\\{x,y\\}$ by replacing the
symbol at position $i$ with $s\in\Sigma$,

  * •

$\mathsf{query}(i,j)$: if $|i-j|\leqslant k$ return $\mathsf{LCE}(i,j)$ of
$x,y$.

The $\mathsf{init}$ operation requires $\mathcal{O}(kn)$ worst-case time.
Operations $\mathsf{update}$ and $\mathsf{query}$ can be executed in worst-
case time $\mathcal{O}(k\log\log n)$ and $\mathcal{O}(\log\log n)$,
respectively.

###### Proof.

For every fixed $p\in\\{-k,\ldots,k\\}$ we maintain the van Emde Boas data-
structure $\mathcal{T}_{p}$. Each $\mathcal{T}_{p}$ maintains a set
$S_{p}\subseteq[n]$ defined as:

$S_{p}:=\\{i\in[n]\text{ such that }x[i]\neq y[i+p]\\}.$

Observe, that sets $S_{p}$ can be efficiently maintained with van Emde Boas
data structures. During each update to word $x[i]$ we iterate over every
$p\in\\{-k,\ldots,k\\}$, check if $x[i]\neq y[i+p]$ and update
$\mathcal{T}_{p}$ accordingly. Single query to $\mathsf{LCE}$ can be done with
a single query to $\mathcal{T}_{p}$. ∎

With that data-structure to answer $\mathsf{LCE}$-queries under text updates
we can proceed with the description of the dynamic data structure for $k$-Edit
Distance with $\mathcal{O}(k\log\log n)$ worst-case update time.

###### Proof of Lemma 5.3.

When length of $x$ and $y$ differ by more than $k$ then the edit distance
between $x$ and $y$ must be greater than $k$ and we can conclude that the
answer is negative. Our algorithm is based on the static algorithm of Landau
and Vishkin [28]. They consider the dynamic programming table
$\mathtt{D}[i,j]:=\mathtt{ed}(x[1:i],y[1:j])$ for edit distance. They claim
that it suffices to touch only $\mathcal{O}(k^{2})$ entries of the table
$\mathtt{D}$ in order to retrieve $\mathtt{D}[|x|,|y|]$ (if its value is
$\mathcal{O}(k)$).

The main observation of the static $\mathcal{O}(n+k^{2})$ time algorithm of
Landau and Vishkin [28] is that
$\mathtt{D}[i+1,j+1]\in\\{\mathtt{D}[i,j],\mathtt{D}[i,j]+1\\}$. Therefore, it
is always beneficial to greedily take $\mathsf{LCE}$ to compute the next value
in the table $\mathtt{D}$. Because we assumed that the edit distance between
$x$ and $y$ is at most $k$, we need to perform at most $k$ queries to
$\mathsf{LCE}$. Note that we consider only values $\mathtt{D}[i,i+p]$ for
$p\in\\{-k,\ldots,k\\}$. Hence we need to touch at most $2k+1$ entries with
value exactly $\ell$ for every $\ell\in[k]$. In total number of entries in
table $\mathtt{D}$ touched by Landau and Vishkin algorithm is
$\mathcal{O}(k^{2})$.

It remains to augment this static algorithm into the dynamic setting. We keep
track of $\mathcal{O}(k)$ data structures from Proposition 5.4 to emulate
$\mathsf{LCE}$ queries (each data-structure corresponds to one diagonal
$p\in\\{-k,\ldots,k\\}$ of Landau-Vishkin algorithm). Single update may
require modification to $\mathcal{O}(k)$ of this data structures which result
in $\mathcal{O}(k\log\log(n))$ update time. Single query to Edit Distance
problem takes $\mathcal{O}(k^{2}\log\log n)$ time because we Vishkin and
Landau algorithm performs $\mathcal{O}(k^{2})$ queries to $\mathsf{LCE}$ (each
can be done in $\mathcal{O}(\log\log(n))$ time with a data structure from
Proposition 5.4). ∎

##  6 Lower bounds

In the prefix-$U_{1}$ problem the task is to maintain a subset $S$ of the
universe $\\{1,\ldots,n\\}$ under deletions and insertions, and support
_threshold queries_ : given $i\in[n]$, decide whether $S$ contains some
element that is $\leqslant i$. The prefix-$U_{1}$ problem can be solved in
deterministic $\mathcal{O}(\log\log(n))$ time with a predecessor search [41,
36] or in expected $\mathcal{O}(\sqrt{\log\log{n}})$ time if randomization is
allowed [40, 25]. (Here, by time we mean the worse of the update and query
times.) Unfortunately, no unconditional lower bounds is known for
prefix-$U_{1}$.

Amarilli et al. [4] presented a large class of problems that are at least as
hard as the prefix-$U_{1}$ problem. Moreover, they showed that there are
problems equivalent to prefix-$U_{1}$. These led them to conjecture that there
is no data structure for prefix-$U_{1}$ that offers updates and queries in
$\mathcal{O}(1)$.

######  Conjecture 6.1 ([4]).

There is no data structure for prefix-$U_{1}$ that achieves $\mathcal{O}(1)$
amortized time for updates and queries in the word-RAM model.

For large enough word-size $w$ the complexity of even harder Predecessor is
$\mathcal{O}(1)$ in the word-RAM model [21]. However, for general $w$ and $n$,
there are tight lower bounds [36]. In Conjecture 6.1 we just expect that the
complexity of prefix-$U_{1}$ cannot be $\mathcal{O}(1)$ for general $w$ and
$n$.

We say that a problem $\mathcal{P}$ is prefix-$U_{1}$-hard if assuming that
$\mathcal{P}$ admits a data structure achieving amortized $\mathcal{O}(1)$
time of operations, the same can be said also about prefix-$U_{1}$. In this
section we show that the dynamic versions of Disjoint Factors and of Edit
Distance are prefix-$U_{1}$-hard.

###  6.1 Lower bound for Disjoint Factors

Now we prove that the $k$-Disjoint Factors problem is prefix-$U_{1}$-hard for
$k=3$. We complement our result and show that Disjoint Factors for $k=2$
admits a data structure with operations taking $\mathcal{O}(1)$ time.

######  Lemma 6.2.

Unless Conjecture 6.1 fails, there does not exist a data structure for the
dynamic variant of Disjoint Factors for $k\geqslant 3$ with $\mathcal{O}(1)$
amortized update and query time.

###### Proof.

We show a reduction from prefix-$U_{1}$ to Disjoint Factors on alphabets of
size $3$. Without loss of generality let us assume that
$\Sigma\coloneqq\\{\mathtt{0,1,\\#\\}}$. Assume that $S\subseteq[n]$ is the
set maintained in the prefix-$U_{1}$ problem. Based on $S$ we construct a
word:

$w(S):=\mathtt{1}\;\alpha_{1}\;\alpha_{2}\;\ldots\;\alpha_{n}\;\mathtt{0\;\\#\;0\;0},$

where $\alpha_{i}$ is $\mathtt{1}$ if $i\in S$ and $\mathtt{0}$ otherwise. On
$w(S)$ we maintain the assumed data structure for Disjoint Factors. The
updates to set $S$ are relayed to $w(S)$ in a natural manner. For a threshold
query to prefix-$U_{1}$ of form $i\in[n]$ we do the following:

  * •

Temporarily change the symbol at position $(i+2)$ of $w(S)$ to $\mathtt{\\#}$.

  * •

Query the data structure for Disjoint Factors to decide whether the current
word is a positive instance, and return this answer as the answer to the
query.

  * •

Finally, revert the word back to the original $w(S)$.

This concludes the construction of the reduction. Observe, that each step of
that reduction can be implemented in (amortized) $\mathcal{O}(1)$ time.

For correctness, observe that after a query $i\in[n]$ the input to Disjoint
Factors is of the form (when $i<n$):

$\mathtt{1}\;\alpha_{1}\ldots\alpha_{i}\;\mathtt{\\#}\;\alpha_{i+2}\ldots\alpha_{n}\;\mathtt{0\;\\#\;0\;0}.$

In the resulting word, there are only two occurrences of symbol
$\mathtt{\\#}$. Therefore, if the answer to Disjoint Factors is positive, then
word $\mathtt{\\#}\alpha_{i+2}\ldots\alpha_{n}\mathtt{\\#}$ is a
$\mathtt{\\#}$-factor. Observe that two last letters $\mathtt{0\;0}$ already
form a $\mathtt{0}$-factor. We are left with determining the position of a
$\mathtt{1}$-factor. However, all factors need to be pairwise disjoint. Hence
$\mathtt{1}$-factor exists iff at least one of $\alpha_{1},\ldots,\alpha_{i}$
is $\mathtt{1}$. This is possible only if $[i]\cap S\neq\emptyset$, which
proves the correctness of our reduction. ∎

Now we show that Disjoint Factors for $k=2$ can be maintained in
$\mathcal{O}(1)$ time. We first need a simple lemma.

######  Lemma 6.3.

For any word $w\in\Sigma^{\star}$, if every symbol in $w$ occurs more than
$|\Sigma|$ times, then the answer to Disjoint Factors on $w$ is positive.

###### Proof.

Let $k:=|\Sigma|$. We prove the statement by induction on $k\geqslant 1$. In
the base case $k=1$ the statement trivially holds. Let $w\in\Sigma^{\star}$ be
a word over alphabet of size $k$ were each letter appears at least $k+1$
times. Let $i\in[n]$ be the maximal index such that no symbol from $\Sigma$ is
repeated in $w[1:i]$. It follows that in $w[i+1:n]$ each symbol occurs at
least $k$ times. By the maximality of $i$ the symbol $\alpha:=w[i+1]$ occurs
twice in $w[1:i+1]$. Let us greedily take these two occurrences of $\alpha$ as
an $\alpha$-factor.

Consider the word $w[i+1:n]$ and delete from it all occurrences of $\alpha$.
This word contains $k-1$ symbols and each symbol occurs at least $k$ times.
Therefore, by the induction assumption it contains $k-1$ disjoint factors. By
combining them with our $\alpha$-factor, we see that the original word $w$
contains $k$ disjoint factors. ∎

Now, we show that Disjoint Factors for binary alphabets can be dynamically
maintained in $\mathcal{O}(1)$ time.

######  Lemma 6.4.

There exists a data-structure for the dynamic variant of Disjoint Factors for
$k=2$ that supports updates and queries in amortized time $\mathcal{O}(1)$.

###### Proof.

Consider Lemma 6.3 for an alphabet of size $2$, say
$\Sigma=\\{\mathtt{0},\mathtt{1}\\}$. If both symbols occur at least $3$ times
in a given word, then the answer to Disjoint Factors is positive. On the other
hand, if one symbol appears less than twice, then the answer to Disjoint
Factors must be negative.

It remains to consider the situation when one of the symbols occurs exactly
twice. Let $w\in\Sigma^{n}$ be the considered word Without loss of generality
let $\mathtt{1}$ be the symbol that occurs twice in $w$ on positions
$i,j\in[n]$. Therefore, we need to take these positions to construct a
$\mathtt{1}$-factor. Observe, that if an answer to Disjoint Factors is
positive then the $\mathtt{0}$-factor must be contained in either $w[1,i-1]$
or $w[j+1:n]$. Since the symbol $\mathtt{1}$ appears only twice, both of these
words consist of symbol $\mathtt{0}$ exclusively. Hence the answer to Disjoint
Factors is negative iff $i\leqslant 2$ and $j\geqslant n-1$.

Necessary information to store and verify this procedure can be easily
maintained in $\mathcal{O}(1)$ update/query time. ∎

###  6.2 Lower bound for Edit Distance

Next, we prove a lower bound for Edit Distance problem for $k=2$. In this
section we consider words over alphabet $\Sigma=\\{\mathtt{a,b,c}\\}$. Before
we proceed let us consider a simple gadget.

######  Claim 6.5.

Consider any word $w\in\\{\mathtt{a,b}\\}^{n}$. Then the edit distance between
words

$\mathtt{aca}\,w\,\mathtt{cac}\qquad\text{ and
}\qquad\mathtt{cac}\,w\,\mathtt{aca}$

is equal to $2$ if $w=\mathtt{a}^{n}$. Otherwise, if $w$ contains any symbol
$\mathtt{b}$, then the edit distance is strictly greater than $2$.

We postpone the proof of Claim 6.5 for a moment. Let us now use it to prove
the prefix-$U_{1}$-hardness of Edit Distance for distances at least $2$.

######  Lemma 6.6.

Unless Conjecture 6.1 fails, there does not exist a data structure for the
dynamic variant of Edit Distance for $k\geqslant 2$ that supports updates and
queries in amortized time $\mathcal{O}(1)$.

###### Proof.

We reduce prefix-$U_{1}$ to $2$-Edit Distance on
$\Sigma=\\{\mathtt{a,b,c}\\}$. Let $S\subseteq[n]$ be the set maintained in
the prefix-$U_{1}$ problem. Based on $S$ we maintain the following input words
to the Edit Distance problem:

$\displaystyle x_{S}:=$
$\displaystyle\,\mathtt{a\,c\,a}\,\alpha_{1}\,\ldots\,\alpha_{n}\,\mathtt{a\,a\,a}$
$\displaystyle y_{S}:=$
$\displaystyle\,\mathtt{c\,a\,c}\,\alpha_{1}\,\ldots\,\alpha_{n}\,\mathtt{a\,a\,a}$

where $\alpha_{i}\coloneqq\mathtt{b}$ if $i\in S$ and
$\alpha_{i}\coloneqq\mathtt{a}$ otherwise. Updates to $S$ are naturally
relayed to $x_{S}$ and $y_{S}$.

During a query $i\in[n]$ to the prefix-$U_{1}$ problem we make the following
modifications in $x_{S}$ and $y_{S}$. First, we replace symbols in
$x_{S}[i+3:i+5]$ with $\mathtt{cac}$ and in $y_{S}[i+3:i+5]$ with
$\mathtt{aca}$. After the modification our two words look as follows (when
$i<n-3$):

$\displaystyle\,\mathtt{a\,c\,a}\,\alpha_{1}\,\ldots\,\alpha_{i}\,\mathtt{c\,a\,c}\,\alpha_{i+4}\,\ldots\,\alpha_{n}\mathtt{a\,a\,a}$
$\displaystyle\,\mathtt{c\,a\,c}\,\alpha_{1}\,\ldots\,\alpha_{i}\,\mathtt{a\,c\,a}\,\alpha_{i+4}\,\ldots\,\alpha_{n}\mathtt{a\,a\,a}$

Next we query the data structure for Edit Distance to find out whether the
edit distance between these two words is larger than $2$. If so, we conclude
that the answer to prefix-$U_{1}$ query is positive, and otherwise it is
negative. Then, we clean up and restore the words to the original form of
$x_{S}$ and $y_{S}$. This concludes the description of our reduction. Observe
that all the steps can be done in (amortized) $\mathcal{O}(1)$ time.

For the correctness, observe that during a query, the input words to Edit
Distance are of the following form: $\mathtt{aca}\,w\,\mathtt{cac}\,v$ and
$\mathtt{cac}\,w\,\mathtt{aca}\,v$, for some
$w,v\in\\{\mathtt{a,b}\\}^{\star}$. By Claim 6.5 the edit distance between
these two words is $2$ iff $w=\mathtt{a}^{\star}$. This happens iff
$S\cap[i]=\emptyset$, which concludes the correctness proof. ∎

The remaining proof of Claim 6.5 can be shown by a diligent case analysis.

###### Proof of Claim 6.5.

Observe that the edit distance between words is at least $1$. Indeed, on one
hand the words have equal length hence only a single substitution is possible.
On the other hand, the Hamming distance between words is $6$ so a single
substitution operation is not sufficient.

Hence, we need to verify when it is possible to transform the first word into
the second word by using two edit operations. Because the words have an equal
length and the Hamming distance between them is $6$, two substitutions are not
sufficient. Therefore, only insertions and deletions are possible. We cannot
perform just two insertions or just two deletions to the first word, because
the words have the same length. Therefore, we can only do one insertion and
one deletion.

Observe that initially the number of symbols $\mathtt{a}$, $\mathtt{b}$, and
$\mathtt{c}$ is the same in the both words. Therefore, the letter we insert
and the letter we delete must be the same letter. On the other hand, the words
differ at the first and the last position. Hence, we can only (a) insert
$\mathtt{c}$ to the first position of the first word and delete $\mathtt{c}$
from the last position of the first word; or (b) delete $\mathtt{a}$ from the
first position of the first word and insert $\mathtt{a}$ to the last position
of the first word. Now, observe that (i) if $w=\mathtt{a}^{n}$ then the words
are the same after applying (a), and (ii) if there is at least one symbol
$\mathtt{b}$ in $w$, then regardless whether we apply (a) or (b), the
operations cause a misalignment at the position of $\mathtt{b}$s and the words
differ. ∎

## References

  * [1] A. Abboud, A. Backurs, and V. V. Williams.  Tight hardness results for LCS and other sequence similarity measures.  In V. Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59–78. IEEE Computer Society, 2015.
  * [2] A. Abboud, T. D. Hansen, V. V. Williams, and R. Williams.  Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made.  In D. Wichs and Y. Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 375–388. ACM, 2016.
  * [3] J. Alman, M. Mnich, and V. V. Williams.  Dynamic parameterized problems and algorithms.  ACM Trans. Algorithms, 16(4):45:1–45:46, 2020.
  * [4] A. Amarilli, L. Jachiet, and C. Paperman.  Dynamic membership for regular languages.  In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 of LIPIcs, pages 116:1–116:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [5] A. Amir, P. Charalampopoulos, S. P. Pissis, and J. Radoszewski.  Dynamic and internal longest common substring.  Algorithmica, 82(12):3707–3743, 2020.
  * [6] A. Andoni and N. S. Nosatzki.  Edit distance in near-linear time: it’s a constant factor.  In S. Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 990–1001. IEEE, 2020.
  * [7] A. Backurs and P. Indyk.  Edit distance cannot be computed in strongly subquadratic time (unless SETH is false).  SIAM J. Comput., 47(3):1087–1097, 2018.
  * [8] M. Basavaraju, F. Panolan, A. Rai, M. S. Ramanujan, and S. Saurabh.  On the kernelization complexity of string problems.  Theor. Comput. Sci., 730:21–31, 2018.
  * [9] T. Batu, F. Ergün, J. Kilian, A. Magen, S. Raskhodnikova, R. Rubinfeld, and R. Sami.  A sublinear algorithm for weakly approximating edit distance.  In L. L. Larmore and M. X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 316–324. ACM, 2003.
  * [10] P. Beame and F. E. Fich.  Optimal bounds for the predecessor problem and related problems.  J. Comput. Syst. Sci., 65(1):38–72, 2002.
  * [11] H. L. Bodlaender, S. Thomassé, and A. Yeo.  Kernel bounds for disjoint cycles and disjoint paths.  Theor. Comput. Sci., 412(35):4570–4578, 2011.
  * [12] H. L. Bodlaender, S. Thomassé, and A. Yeo.  Kernel bounds for disjoint cycles and disjoint paths.  Theor. Comput. Sci., 412(35):4570–4578, 2011.
  * [13] M. Bojańczyk.  Languages recognised by finite semigroups and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic.  2020\.  In preparation.
  * [14] K. Bringmann and M. Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In V. Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79–97. IEEE Computer Society, 2015.
  * [15] P. Charalampopoulos.  Data Structures for Strings in the Internal and Dynamic Settings.  PhD thesis, King’s College London, 2021.
  * [16] J. Chen, W. Czerwiński, Y. Disser, A. E. Feldmann, D. Hermelin, W. Nadara, M. Pilipczuk, M. Pilipczuk, M. Sorge, B. Wróblewski, and A. Zych-Pawlewicz.  Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 796–809. SIAM, 2021.
  * [17] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [18] Z. Dvořák, M. Kupec, and V. Tůma.  A dynamic data structure for MSO properties in graphs with bounded tree-depth.  In Proceedings of the 22th Annual European Symposium on Algorithms, ESA 2014, volume 8737 of Lecture Notes in Computer Science, pages 334–345. Springer, 2014.
  * [19] Z. Dvořák and V. Tůma.  A dynamic data structure for counting subgraphs in sparse graphs.  In Proceedings of the 13th International Symposium on Algorithms and Data Structures, WADS 2013, volume 8037 of Lecture Notes in Computer Science, pages 304–315. Springer, 2013.
  * [20] G. S. Frandsen, P. B. Miltersen, and S. Skyum.  Dynamic word problems.  J. ACM, 44(2):257–271, 1997.
  * [21] M. L. Fredman and D. E. Willard.  Surpassing the information theoretic bound with fusion trees.  J. Comput. Syst. Sci., 47(3):424–436, 1993.
  * [22] E. Goldenberg, T. Kociumaka, R. Krauthgamer, and B. Saha.  Gap edit distance via non-adaptive queries: Simple and optimal.  CoRR, abs/2111.12706, 2021.
  * [23] J. Gramm, R. Niedermeier, and P. Rossmanith.  Fixed-parameter algorithms for Closest String and related problems.  Algorithmica, 37(1):25–42, 2003.
  * [24] A. Grez, F. Mazowiecki, M. Pilipczuk, G. Puppis, and C. Riveros.  Dynamic data structures for timed automata acceptance.  In Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, volume 214 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2021.
  * [25] Y. Han and M. Thorup.  Integer sorting in $O(n\sqrt{\log\log n})$ expected time and linear space.  In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 135–144. IEEE Computer Society, 2002.
  * [26] H. Hyyrö, K. Narisawa, and S. Inenaga.  Dynamic edit distance table under a general weighted cost function.  Journal of Discrete Algorithms, 34:2–17, 2015.
  * [27] D. Knop, M. Koutecký, and M. Mnich.  Combinatorial $n$-fold integer programming and applications.  Math. Program., 184(1):1–34, 2020.
  * [28] G. M. Landau and U. Vishkin.  Fast string matching with k differences.  J. Comput. Syst. Sci., 37(1):63–78, 1988.
  * [29] D. Lokshtanov, D. Marx, and S. Saurabh.  Slightly superexponential parameterized problems.  SIAM J. Comput., 47(3):675–702, 2018.
  * [30] B. Ma and X. Sun.  More efficient algorithms for closest string and substring problems.  SIAM J. Comput., 39(4):1432–1443, 2009.
  * [31] K. Majewski, M. Pilipczuk, and M. Sokołowski.  Maintaining ${CMSO}_{2}$ properties on dynamic structures with bounded feedback vertex number.  CoRR, abs/2107.06232, 2021.
  * [32] W. J. Masek and M. Paterson.  A faster algorithm computing string edit distances.  J. Comput. Syst. Sci., 20(1):18–31, 1980.
  * [33] R. McNaughton and S. Papert.  Counter-free automata.  MIT Press, 1971.
  * [34] K. Mehlhorn, S. Näher, and H. Alt.  A lower bound on the complexity of the union-split-find problem.  SIAM J. Comput., 17(6):1093–1102, 1988.
  * [35] G. Navarro and J. Rojas-Ledesma.  Predecessor search.  ACM Comput. Surv., 53(5):105:1–105:35, 2020.
  * [36] M. Patrascu and M. Thorup.  Dynamic integer sets with optimal rank, select, and predecessor search.  In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 166–175. IEEE Computer Society, 2014.
  * [37] M. Pilipczuk.  Tournaments and optimality: New results in parameterized complexity.  PhD thesis, University of Bergen, 2013.
  * [38] M. P. Schützenberger.  On finite monoids having only trivial subgroups.  Inf. Control., 8(2):190–194, 1965.
  * [39] L. J. Stockmeyer.  The Complexity of Decision Problems in Automata Theory and Logic.  PhD thesis, MIT, 1974.
  * [40] M. Thorup.  Equivalence between priority queues and sorting.  J. ACM, 54(6):28, 2007.
  * [41] P. van Emde Boas.  Preserving order in a forest in less than logarithmic time and linear space.  Inf. Process. Lett., 6(3):80–82, 1977.

##  Appendix A Omitted proofs

###### Proof of Lemma 3.7.

We assume the familiarity with the proof of Lemma 3.3, as our data structure
will extend the one proposed there. Recall that in the context of Lemma 3.7,
we maintain the data structure of Lemma 3.3 for the dictionary
$\widetilde{\mathcal{S}}$ and $o$ is the maintained word.

The data structure of Lemma 3.3 stores, for every
$\tilde{s}\in\widetilde{\mathcal{S}}$, the following set:

$\Delta(o,\tilde{s})=\\{i\in[L]\;|\;o[i]\neq\tilde{s}[i]\\}.$

As, we have a fixed coloring $\pi\colon[L]\to[16d]$, we can maintain a table
of counters

$\mathcal{T}(\tilde{s},c)\coloneqq|\\{i\in[L]\;|\;\pi(i)=c\text{ and
}i\in\Delta(o,\tilde{s})\\}|\qquad\textrm{for all
}\tilde{s}\in\widetilde{\mathcal{S}}\textrm{ and }c\in[16d].$

Upon initialization, we explicitly compute $\mathcal{T}(\tilde{s},c)$ for
every $\tilde{s}\in\tilde{S}$ and $c\in[16d]$ in $\mathcal{O}(nL+nd)$ time.
During an update to the position $i\in[L]$ of a word
$\tilde{s}\in\widetilde{\mathcal{S}}$ we check if $o[i]\neq\tilde{s}[i]$ and
update the number of colors in $\mathcal{T}(\tilde{s},c)$ based on $\pi(i)$
accordingly. It may happen that the update to $\tilde{s}$ at position $i$
triggered a modification of the word $o$ at position $i$. Then we need to
change $\mathcal{T}(\tilde{s},\pi(i))$ for every
$\tilde{s}\in\widetilde{\mathcal{S}}$. Note that this alone requires
$\mathcal{O}(|\mathcal{S}|)$ time. However, recall that in the proof of Lemma
3.3 we argued that before update when the position $i$ of the word $o$
changes, there were at least $|\widetilde{\mathcal{S}}|/4$ updates to that
position where $o$ was not modified (recall here that we work over the binary
alphabet). Therefore, as in the proof of Lemma 3.3, we may charge the running
time $\mathcal{O}(|\mathcal{S}|)$ to those previous updates to argue that the
amortized update time is $\mathcal{O}(1)$.

Observe that based on the table $\mathcal{T}$, we can compute the set
$\mathsf{colors}_{o,\pi}(\tilde{s})=\\{\pi(i)\;|\;i\in[L]\text{ and
}\tilde{s}[i]=o[i]\\}$ for any given $\tilde{s}$ in time $\mathcal{O}(d)$,
because it is enough to iterate through all $c\in[16d]$ and check whether
$\mathcal{T}(\tilde{s},c)>0$.

Now we describe how to maintain the sets

$\Phi(C)=\\{\tilde{s}\in\widetilde{\mathcal{S}}\;|\;\mathsf{colors}_{o,\pi}(\tilde{s})=C\\}\qquad\textrm{for
every }C\subseteq[16d].$

Each set $\Phi(C)$ is stored as a doubly-linked list of pointers to words from
$\widetilde{\mathcal{S}}$. Upon initialization, we iterate over every
$\tilde{s}\in\tilde{S}$, lookup the value of
$C_{\tilde{s}}\coloneqq\mathsf{colors}_{o,\pi}(\tilde{s})$ and add a pointer
to $\tilde{s}$ to the list $\Phi(C_{\tilde{s}})$. Observe, that this operation
can be implemented in total time $2^{\mathcal{O}(d)}+nL$ time, as we can
compute sets $C_{\tilde{s}}$ for all $\tilde{s}\in\widetilde{\mathcal{S}}$ in
total time $\mathcal{O}(nL)$.

Next, when a word $\tilde{s}$ is updated on some position and is changed to
$\tilde{s}^{\prime}$, we compute the previous set of colors
$C\coloneqq\mathsf{colors}_{o,\pi}(\tilde{s})$ and the new set of colors
$C^{\prime}\coloneqq\mathsf{colors}_{o,\pi}(\tilde{s^{\prime}})$. As argued,
this operation can be done in $\mathcal{O}(d)$ time. Next, we delete the
pointer to the word $\tilde{s}$ from the list $\Phi(C)$ and append a pointer
to $\tilde{s}^{\prime}$ to list $\Phi(C^{\prime})$. Alongside $\tilde{s}$ we
store the pointer to its list entry in the list $\Phi(C^{\prime})$ in order to
be able to remove it efficiently. Both of these operations can be implemented
in $\mathcal{O}(1)$ time. During a query $C\subseteq[16d]$ we return any
element from the list $\Phi(C)$ or assert that it is empty in $\mathcal{O}(1)$
time. ∎