problemdescription  Input: Question: 11institutetext: University of Wrocław,
Faculty of Mathematics and Computer Science, Poland 11email:
<EMAIL_ADDRESS>22institutetext: Göttingen University, Computer Science
Department and CIDAS, Germany 22email<EMAIL_ADDRESS>goettingen.de

# Matching Patterns with Variables Under Edit Distance

Paweł Gawrychowski 11 0000-0002-6993-5440 Florin Manea 22 0000-0001-6094-3324
Stefan Siemer 22 0000-0001-7509-8135

###### Abstract

A pattern $\alpha$ is a string of variables and terminal letters. We say that
$\alpha$ matches a word $w$, consisting only of terminal letters, if $w$ can
be obtained by replacing the variables of $\alpha$ by terminal words. The
matching problem, i.e., deciding whether a given pattern matches a given word,
was heavily investigated: it is NP-complete in general, but can be solved
efficiently for classes of patterns with restricted structure. If we are
interested in what is the minimum Hamming distance between $w$ and any word
$u$ obtained by replacing the variables of $\alpha$ by terminal words (so
matching under Hamming distance), one can devise efficient algorithms and
matching conditional lower bounds for the class of regular patterns (in which
no variable occurs twice), as well as for classes of patterns where we allow
unbounded repetitions of variables, but restrict the structure of the pattern,
i.e., the way the occurrences of different variables can be interleaved.
Moreover, under Hamming distance, if a variable occurs more than once and its
occurrences can be interleaved arbitrarily with those of other variables, even
if each of these occurs just once, the matching problem is intractable. In
this paper, we consider the problem of matching patterns with variables under
edit distance. We still obtain efficient algorithms and matching conditional
lower bounds for the class of regular patterns, but show that the problem
becomes, in this case, intractable already for unary patterns, consisting of
repeated occurrences of a single variable interleaved with terminals.

###### Keywords:

Pattern with variables Matching Edit distance

##  1 Introduction

A _pattern with variables_ is a string consisting of _constant_ or _terminal
letters_ from a finite alphabet $\Sigma$ (e.g., $\mathtt{a,b,c}$), and
_variables_ (e.g., $x,y,x_{1},x_{2}$) from a potentially infinite set
$\mathcal{X}$, with $\Sigma\cap\mathcal{X}=\emptyset$. In other words, a
pattern $\alpha$ is an element of
$PAT_{\Sigma}=(\mathcal{X}\cup\Sigma)^{\mathtt{+}}$. A pattern $\alpha$ is
mapped (by a function $h$ called substitution) to a word by substituting the
variables by arbitrary strings of terminal letters; as such, $h$ simply maps
the variables occurring in $\alpha$ to words over $\Sigma$. For example,
$xx\mathtt{bbb}yy$ can be mapped to $\mathtt{aaaabbbbb}$ by the substitution
$h$ defined by $(x\to\mathtt{aa},y\to\mathtt{b})$. In this framework,
$h(\alpha)$ denotes the word obtained by substituting every occurrence of a
variable $x$ in $\alpha$ by $h(x)$ and leaving all the terminals unchanged. If
a pattern $\alpha$ can be mapped to a string of terminals $w$, we say that
$\alpha$ matches $w$; the problem of deciding whether there exists a
substitution which maps a given pattern $\alpha$ to a given word $w$ is called
the (exact) matching problem.

$\mathtt{Match}$ appears frequently in various areas of theoretical computer
science, such as combinatorics on words (e.g., unavoidable patterns [32],
string solving and the theory of word equations [31]), stringology (e.g.,
generalized function matching [1]), language theory (e.g., pattern languages
[2], the theory of extended regular expressions with backreferences [7, 22,
18, 21]), database theory (e.g., the theory of document spanners [20, 19, 13,
40, 27, 41]), or algorithmic learning theory (e.g., the theory of descriptive
patterns for finite sets of words [43, 2, 14]).

$\mathtt{Match}$ is NP-complete [2], in general. In fact, a detailed analysis
[37, 42, 16, 17, 15, 39] of the matching problem has provided a better
understanding of the parameterized complexity of this problem, highlighting,
in particular, several subclasses of patterns for which the matching problem
is polynomial, when various structural parameters of patterns are bounded by
constants. Prominent examples in this direction are patterns with a bounded
number of repeated variables, patterns with bounded scope coincidence degree
[37], patterns with bounded locality [12], or patterns with a bounded
treewidth [37]. See [15, 12, 37] for efficient algorithms solving
$\mathtt{Match}_{P}$ restricted to (or, in other words, parameterized by) to
such classes $P$ of patterns. In general, each of the structural parameters
defining such classes $P$ is a number $k$ characterizing in some way the
structure of the patterns of the class $P$ and the matching algorithms for the
respective class of patterns runs in $O(n^{ck})$ for some constant $c$.
Moreover, these restricted matching problems are usually shown to be
$W[1]$-hard w.r.t. the respective parameters.

In [23], the study of efficient matching algorithms for patterns with
variables was extended to an approximate setting. More precisely, the problem
of deciding, for a pattern $\alpha$ from a class of patterns $P$ (defined by
structural restrictions), a word $w$, and a non-negative integer $\Delta$,
whether there exists a substitution $h$ such that the Hamming distance
$d_{\mathtt{HAM}}(h(\alpha),w)$ between $h(\alpha)$ and $w$ is at most
$\Delta$ was investigated. The corresponding minimization problem of computing
$d_{\mathtt{HAM}}(\alpha,w)=\min\\{d_{\mathtt{HAM}}(h(\alpha),w)\mid h$ is a
substitution of the variables of $\alpha\\}$ was also considered. The main
results of [23] were rectangular time algorithms and matching conditional
lower bounds for the class of regular patterns $\mathtt{Reg}$ (which contain
at most one occurrence of any variable). Moreover, polynomial time algorithms
were obtained for unary patterns (also known as one-variable patterns, which
consist in one or more occurrences of a single variable, potentially
interleaved with terminal strings) or non-cross patterns (which consist in
concatenations of unary patterns, whose variables are pairwise distinct).
However, as soon as the patterns may contain multiple variables, whose
occurrences are interleaved, the problems became NP-hard, even if only one of
the variables occurs more than once. As such, unlike the case of exact
matching, the approximate matching problem under Hamming distance is NP-hard
even if some of the aforementioned parameters (number of repeated variables,
scope coincidence degree, treewidth, but, interestingly, not locality) were
upper bounded by small constants.

Our Contribution. In this paper, inspired by, e.g., [28, 10, 5, 34, 4, 9, 8,
35] where various stringology patterns are considered in an approximate
setting under edit distance [30, 29], and as a natural extension of the
results of [23], we consider the aforementioned approximate matching problems
(parameterized by a class of patterns $P$) for the edit distance
$d_{\mathtt{ED}}(\cdot,\cdot)$, instead of Hamming Distance:

Our paper presents two main results, which allow us to paint a rather
comprehensive picture of the approximate matching problem under edit distance.

Firstly, we consider the class of regular patterns, and show that
$\mathtt{MisMatch}_{\mathtt{Reg}}$ and $\mathtt{MinMisMatch}_{\mathtt{Reg}}$
can be solved in $O(n\Delta)$ time (where, for $\mathtt{MinMisMatch}$,
$\Delta$ is the computed result); a matching conditional lower bound follows
from the literature [3]. This is particularly interesting because the problem
of computing $d_{\mathtt{ED}}(\alpha,w)$ for $\alpha=w_{0}x_{1}w_{1}\ldots
x_{k}w_{k}$ can be seen as the problem of computing the minimal edit distance
between any string in which $w_{1},\ldots,w_{k}$ occur, without overlaps, in
this exact order and the word $w$.

Secondly, we show that, unlike the case of matching under Hamming distance,
$\mathtt{MisMatch}_{P}$ becomes $W[1]$-hard already for $P$ being the class of
unary patterns, with respect to the number of occurrences of the single
variable. So, interestingly, the problem of matching patterns with variables
under edit distance is computationally hard for all the classes (that we are
aware of) of structurally restricted patterns with polynomial exact matching
problem, as soon as at least one variable is allowed to occur an unbounded
number of times.

To complement the results presented in this paper, we note that, for the
classes of patterns considered in [15, 12, 37, 23], which admit polynomial-
time exact matching algorithms, one can straightforwardly adapt those
algorithms to work in polynomial time in the case of matching under edit
distance, when a constant upper bound $k_{1}$ on the number of occurrences of
each variable exists. The complexity of these algorithms is usually
$O(n^{f(k_{1},k_{2})})$, for a polynomial function $f$ and for $k_{2}$ being a
constant upper bound for the value of the structural parameter considered when
defining these classes (locality, scope coincidence degree, treewidth, etc.).
If no restriction is imposed on the structure of the pattern, $\mathtt{Match}$
(and, as such, the matching under both Hamming and edit distances) is NP-hard
even if there are at most two occurrences of each variable [16].

##  2 Preliminaries

Some basic notations and definitions regarding strings and patterns with
variables were already given in the introduction and, for more details, we
also refer to [33, 23]. We only recall here some further notations. The set of
all patterns, over all terminal-alphabets $\Sigma$, is denoted
$PAT=\bigcup_{\Sigma}PAT_{\Sigma}$. Given a word or pattern $\gamma$, we
denote by $\mathtt{alph}(\gamma)=B$ the smallest set (w.r.t. inclusion)
$B\subseteq\Sigma$ and by $\mathtt{var}(\gamma)=Y$ the smallest set
$Y\subseteq\mathcal{X}$ such that $\gamma\in(B\cup Y)^{\star}$. For any symbol
$t\in\Sigma\cup\mathcal{X}$ and $\alpha\in PAT_{\Sigma}$, $|\alpha|_{t}$
denotes the total number of occurrences of the symbol $t$ in $\alpha$. For a
pattern $\alpha=w_{0}x_{1}w_{1}\ldots w_{k}x_{k}$, we denote by
$\mathtt{term}(\alpha)=w_{0}w_{1}\ldots w_{k}$ the projection of $\alpha$ on
the terminal alphabet $\Sigma$.

For words $u,w\in\Sigma^{\star}$, the _edit distance_ [30, 29] between $u$ and
$w$ is defined as the minimal number $d_{\mathtt{ED}}(u,w)$ of letter
insertions, letter deletions, and letter to letter substitutions which one has
to apply to $u$ to obtain $w$ .

We recall some basic facts about the edit distance. Assume that $u$ is
transformed into $w$ by a sequence of edits $\gamma$ (i.e., $u$ is aligned to
$w$ by $\gamma$). We can assume without losing generality that the edits in
$\gamma$ are ordered left to right with respect to the position of $u$ where
they are applied. Then, for each factorization $u=u_{1}\ldots u_{k}$ of $u$,
there exists a factorization $w=w_{1}\ldots w_{k}$ of $w$ such that $w_{i}$ is
obtained from $u_{i}$ when applying the edits of $\gamma$ which correspond to
the positions of $u_{i}$, for $i\in\\{1,\ldots,k\\}$. Note that this
factorization of $w$ is not unique: we assume that the insertions applied at
the beginning of $u$ correspond to positions of $u_{1}$, the insertions
applied at the end of $u$ correspond to positions of $u_{k}$, but the
insertions applied between $u_{i-1}$ and $u_{i}$ can be split arbitrarily in
two parts: when considering them in the order in which they occur in $\gamma$
(so left to right w.r.t. the positions of $u$ where they are applied) we
assume to first have a (possibly empty) set of insertions which correspond to
positions of $u_{i-1}$ and then a (possibly empty) set of insertions which
correspond to positions of $u_{i}$. On the other hand, if $w=w_{1}w_{2}$, we
can uniquely identify the shortest prefix $u_{1}$ (respectively, the longest
prefix $u^{\prime}_{1}$) of $u$ from which, when applying the edits of
$\gamma$ we obtain the prefix $w_{1}$ of $w$.

Now, for a pattern $\alpha$ and a word $w$, we can define the edit distance
between $\alpha$ and $w$ as
$d_{\mathtt{ED}}(\alpha,w)=\min\\{d_{\mathtt{ED}}(h(\alpha),w)\mid h\mbox{ is
a substitution of the variables of }\alpha\\}$. It is worth noting that
$d_{\mathtt{ED}}(\alpha,w)\leq|w|+|\mathtt{term}(\alpha)|$.

With these definitions, we can consider the two pattern matching problems for
families of patterns $P\subseteq PAT$, as already defined in the introduction.
In the first problem $\mathtt{MisMatch}_{P}$, which extends
$\mathtt{Match}_{P}$, we allow for a certain edit distance $\Delta$ between
the image $h(\alpha)$ of $\alpha$ under a substitution $h$ and the target word
$w$ instead of searching for an exact matching. In the second problem,
$\mathtt{MinMisMatch}_{P}$, we are interested in finding the substitution $h$
for which the edit distance between $h(\alpha)$ and the word $w$ is minimal,
over all possible choices of $h$.

As a remark, based on our general comments regarding the edit distance, the
following theorem follows.

######  Theorem 2.1 ()

$\mathtt{MisMatch}_{PAT}$ and $\mathtt{MinMisMatch}_{PAT}$ can be solved in
$O(n^{2k_{2}+k_{1}})$ time, where $k_{1}$ is the maximum number of occurrences
of any variable in the input pattern $\alpha$ and $k_{2}$ is the total number
of occurrences of variables in $\alpha$.

As mentioned in the Introduction, the result of the previous Theorem can be
improved if we consider the two problems for classes of patterns with
restricted structure, where we obtain algorithms whose complexity depends on
the structural parameter associated to that class, rather than the total
number of occurrences of variables.

##  3 Our Results

The first main result of our paper is about the class of regular patterns. A
pattern $\alpha$ over the terminal alphabet $\Sigma$ is regular if
$\alpha=w_{0}(\Pi_{i=1}^{k}x_{i}w_{i})$ where, for $i\in\\{1,\ldots,k\\}$,
$w_{i}\in\Sigma^{*}$ and $x_{i}$ is a variable, and $x_{i}\neq x_{j}$ for all
$i\neq j$. The class of regular patterns is denoted by $\mathtt{Reg}$. We can
show the following theorem.

######  Theorem 3.1 ()

$\mathtt{MisMatch}_{\mathtt{Reg}}$ can be solved in $O(n\Delta)$ time. For an
accepted instance $w,\alpha,\Delta$ of $\mathtt{MisMatch}_{\mathtt{Reg}}$ we
also compute $d_{\mathtt{ED}}(\alpha,w)$ (which is at most $\Delta$).

###### Proof

Preliminaries and setting. We begin with an observation. For
$\alpha=w_{0}(\Pi_{i=1}^{k}x_{i}w_{i})$, we can assume w.l.o.g. that
$w_{i}\in\Sigma^{+}$ for all $i\leq k$ as otherwise we would have neighboring
variables that could be replaced by a single variable; thus,
$k\leq|\mathtt{term}(\alpha)|$. To avoid some corner cases, we can assume
w.l.o.g. that $\alpha$ and $w$ start with the same terminal symbol (this can
be achieved by adding a fresh letter $\$$ in front of both $\alpha$ and $w$).
While not fundamental, these simplifications make the exposure of the
following algorithm easier to follow.

Before starting the presentation of the algorithm, we note that a solution for
$\mathtt{MisMatch}_{\mathtt{Reg}}$ with distance $\Delta=0$ is a solution to
$\mathtt{Match}_{\mathtt{Reg}}$ and can be solved in $\mathcal{O}(n)$ by a
greedy approach (as shown, for instance, in [15]). Further, the special case
$x_{1}w_{1}x_{2}$ can be solved by an algorithm due to Landau and Vishkin [28]
in $\mathcal{O}(n\Delta)$ time. In the following, we are going to achieve the
same complexity for the general case of $\mathtt{MisMatch}_{\mathtt{Reg}}$ by
extending the ideas of this algorithm to accommodate the existence of an
unbounded number of pairwise-distinct variables.

One important idea which we use in the context of computing the edit distance
between an arbitrary regular pattern and a word is to interpret each regular
variable as an arbitrary amount of “free” insertions on that position, where
“free” means that they will not be counted as part of the actual distance (in
other words, they do not increase this distance). Indeed, we can see that the
factor which substitutes a variable should always be equal to the factor to
which it is aligned (after all the edits are performed) from the target word,
hence does not add anything to the overall distance (and, therefore, it is
“free”). As such, this factor can be seen as being obtained via an arbitrary
amount of letter insertions. Now, using this observation, it is easier to
design an $O(nm)$-time algorithm which computes the edit distance between the
terminal words $\beta=\mathtt{term}(\alpha)$ (instead of the pattern $\alpha$)
and $w$ with the additional property that, for the positions
$F_{g}=|(\Pi_{i=0}^{g}|w_{i}|)|$ for $0\leq g\leq k-1$, we have that the
insertions done between positions $\beta[F_{g}]$ and $\beta[F_{g}+1]$ when
editing $\beta$ to obtain $w$ do not count towards the total edit distance
between $\beta$ and $w$. For simplicity, we denote the set $\\{F_{g}|0\leq
g\leq k-1\\}$ by $F$, we set $F_{k}=+\infty$, and note that $|\beta|=m-k$ (so
$\beta\in\Theta(m)$).

The description of our algorithm is done in two phases. We first explain how
$\mathtt{MisMatch}_{\mathtt{Reg}}$ can be solved by dynamic programming in
$O(nm)$ time. Then, we refine this approach to an algorithm which fulfills the
statement of the theorem.

When presenting our algorithms, we refer to an alignment of prefixes
$\beta[1:j]$ of $\beta$ and $w[1:\ell]$ of $w$, which simply means editing
$\beta[1:j]$ to obtain $w[1:\ell]$.

First phase: a classical dynamic programming solution. We define the
$(|\beta|+1)\times(n+1)$ matrix $D[\cdot][\cdot]$, where $D[j][\ell]$ is the
edit distance between the prefixes $\beta[1:j]$, with $0\leq j\leq|\beta|$,
and $w[1:\ell]$, with $0\leq\ell\leq n$, with the additional important
property that the insertions done between positions $\beta[F_{g}]$ and
$\beta[F_{g}+1]$, for $F_{g}\leq j$, are not counted in this distance (they
correspond to variables in the pattern $\alpha$). As soon as this matrix is
computed, we can retrieve the edit distance between $\alpha$ and $w$ from the
element $D[m-k][n]$. Clearly, now the instance $(\alpha,w,\Delta)$ of
$\mathtt{MisMatch}_{\mathtt{Reg}}$ is answered positively if and only if
$D[m-k][n]\leq\Delta$. So, let us focus on an algorithm computing this matrix.

The elements of the matrix $D[\cdot][\cdot]$ can be computed by dynamic
programming in $O(mn)$ time (see Appendix). Moreover, by tracing back the
computation of $D[m-k][n]$, we obtain a path consisting in elements of the
matrix, leading from $D[0][0]$ to $D[m-k][n]$, which encodes the edits needed
to transform $\beta$ into $w$. An edge between $D[j-1][\ell]$ and $D[j][\ell]$
corresponds to the deletion of $\beta[j]$; and edge between $D[j-1][\ell-1]$
and $D[j][\ell]$ corresponds to a substitution of $\beta[j]$ by $w[\ell]$, or
to the case where $\beta[j]$ and $w[\ell]$ are left unchanged, and will be
aligned in the end. Moreover, an edge between $D[j][\ell-1]$ and $D[j][\ell]$
corresponds to an insertion of $w[\ell]$ after position $j$ in $\beta$; this
can be a free insertion too (and part of the image of a variable of $\alpha$),
but only when $j\in F$. This concludes the first phase of our proof.

Second phase: a succinct representation and more efficient computation of the
dynamic programming table. In the second phase of our proof, we will focus on
how to solve $\mathtt{MisMatch}_{\mathtt{Reg}}$ more efficiently. The idea is
to avoid computing all the elements of the matrix $D[\cdot][\cdot]$, and
compute, instead, only the relevant elements of this matrix, following the
ideas of the algorithm by Landau and Vishkin [28]. The main difference between
the setting of that algorithm (which can be directly used to compute the edit
distance between two terminal words or between a word $w$ and a pattern
$\alpha$ of the form $xuy,xu$, or $uy$, where $x$ and $y$ are variables and
$u$ is a terminal word) and ours is that, in our case, the diagonals of the
matrix $D[\cdot][\cdot]$ are not non-decreasing (when traversed in increasing
order of the rows intersected by the respective diagonal), as we now also have
free insertions which may occur at various positions in $\beta$ (not only at
the beginning and end). This is a significant complication, which we will
address next.

The main idea of the optimization done in this second phase is that we could
actually compute and represent the matrix $D[\cdot][\cdot]$ more succinctly,
by only computing and keeping track of at most $\Delta$ relevant elements on
each diagonal of this matrix, where relevant means that we cannot explicitly
rule out the existence of a path leading from $D[0][0]$ to $D[m-k][n]$ which
goes through that element.

For the clarity of exposure, we recall that the diagonal $d$ of the matrix
$D[\cdot][\cdot]$ is defined as the array of elements $D[j][\ell]$ where
$\ell-j=d$ (ordered in increasing order w.r.t. the first component $j$), where
$-|\beta|+1\leq d\leq n$. Very importantly, for a diagonal $d$, we have that
if $D[j][j+d]\leq D[j+1][j+1+d]$ then $D[j+1][j+1+d]-D[j][j+d]\leq 1$;
however, it might also be the case that $D[j][j+d]>D[j+1][j+1+d]$, when
$D[j+1][j+1+d]$ is obtained from $D[j+1][j+d]$ by a free insertion.

Analysis of the diagonals, definition of $M_{d}[\delta]$ and its usage. Now,
for each diagonal $d$, with $-|\beta|+1\leq d\leq n$, and $\delta\leq\Delta$,
we define $M_{d}[\delta]=\max\\{j\mid D[j][j+d]=\delta,$ and
$D[j^{\prime}][j^{\prime}+d]>\delta$ for all $j^{\prime}>j\\}$ (by convention,
$M_{d}[\delta]=-\infty$, if $\\{j\mid D[j][j+d]=\delta,$ and
$D[j^{\prime}][j^{\prime}+d]>\delta$ for all $j^{\prime}>j\\}=\emptyset$).
That is, $M_{d}[\delta]$ is the greatest row where we find the value $\delta$
on the diagonal $d$ and, moreover, all the elements appearing on greater rows
on that diagonal are strictly greater than $\delta$ (or
$M_{d}[\delta]=-\infty$ if such a row does not exist).

Note that if a value $\delta$ appears on diagonal $d$ and there exists some
$j^{\prime}$ such that $D[j][j+d]\geq\delta$ for all $j\geq j^{\prime}$, then,
due to the only relations which may occur between two consecutive elements of
$d$, we have that $M_{d}[\delta]\neq-\infty$. In particular, if a value
$\delta$ appears on diagonal $d$ then $M_{d}[\delta]\neq-\infty$ if and only
if $D[|\beta|][|\beta|+d]\geq\delta$. Consequently, if there exists $k>0$ such
that $M_{d}[\delta-k]=|\beta|$ then $M_{d}[\delta]=-\infty$.

In general, all values $M_{d}[\delta]$ which are equal to $-\infty$ are not
relevant to our computation. To understand which other values $M_{d}[\delta]$
are not relevant for our algorithm, we note that if there exist some $k>0$ and
$s\geq 0$ such that $M_{d+s}[\delta-k]=|\beta|$ then it is not needed to
compute $M_{d-g}[\delta+h]$, for any $g,h\geq 0$, at all, as any path going
from $D[0][0]$ to $D[|\beta|][n]$, which corresponds to an optimal sequence of
edits, does not go through $D[M_{d-g}[\delta+h]][M_{d}[\delta+h]+d]$. If
$s=0$, then it is already clear that $M_{d}[\delta]=-\infty$, and we do not
need to compute it. If $s\geq 1$, it is enough to show our claim for $h=0$ and
$g=0$. Indeed, assume that the optimal sequence of edits transforming $\beta$
into $w$ corresponds to a path from $D[0][0]$ to $D[|\beta|][n]$ going through
$D[M_{d}[\delta]][M_{d}[\delta]+d]$. By the fact that $M_{d}[\delta]$ is the
largest $j$ for which $D[j][j+d]\leq\delta$, we get that this path would have
to intersect, after going through $D[M_{d}[\delta]][M_{d}[\delta]+d]$, the
path from $D[0][0]$ to
$D[M_{d+s}[\delta-k]][M_{d+s}[\delta-k]+d+s]=D[|\beta|][|\beta|+d+s]$ (which
goes only through elements $\leq\delta-k$). As $k>0$, this is a contradiction,
as the path from $D[0][0]$ to $D[|\beta|][n]$ going through
$D[M_{d}[\delta]][M_{d}[\delta]+d]$ goes only through elements $\geq\delta$
after going through $D[M_{d}[\delta]][M_{d}[\delta]+d]$. So, $M_{d}[\delta]$
is not relevant if there exist $k>0$ and $s>0$ such that
$M_{d+s}[\delta-k]=m$.

Once all relevant values $M_{d}[\delta]$ are computed, for $d$ diagonal and
$\delta\leq\Delta$, we simply have to check if $M_{n-|\beta|}[\delta]=|\beta|$
(i.e., $D[|\beta|][n]=\delta$) for some $\delta\leq\Delta$. So, we can focus,
from now on, on how to compute the relevant elements $M_{d}[\delta]$
efficiently. In particular, all these elements are not equal to $-\infty$.

Towards an algorithm: understanding the relations between elements on
consecutive diagonals. Let us now understand under which conditions
$D[j][\ell]=\delta$ holds, as this is useful to compute $M_{d}[\delta]$. In
general, this means that there exists a path leading from $D[0][0]$ to
$D[j][\ell]$ consisting only in elements with value $\leq\delta$, and which
ends with a series of edges belonging to the diagonal $d=\ell-j$, that
correspond to substitutions or to letters being left unchanged. In particular,
if all the edges connecting $D[j^{\prime}][j^{\prime}+d]$ and $D[j][\ell]$ on
this path correspond to unchanged letters, then $\beta[j^{\prime}:j]$ is a
common prefix of $\beta[j^{\prime}:|\beta|]$ and $w[j^{\prime}+d:n]$. Looking
more into details, there are several cases when $D[j][\ell]=\delta$.

If $j\notin F$ and $\beta[j]\neq w[\ell]$, then $D[j-1][\ell-1]\geq\delta-1$
and $D[j-1][\ell]\geq\delta-1$ and $D[j][\ell-1]\geq\delta-1$ and at least one
of the previous inequalities is an equality (i.e., one of the following must
hold: $D[j][\ell-1]=\delta-1$ or $D[j-1][\ell-1]=\delta-1$ or
$D[j-1][\ell]=\delta-1$). If $j\notin F$ and $\beta[j]=w[\ell]$, then
$D[j-1][\ell-1]\geq\delta$ and $D[j-1][\ell]\geq\delta-1$ and
$D[j][\ell-1]\geq\delta-1$ and at least one of the previous inequalities is an
equality.

If $j\in F$ and $\beta[j]\neq w[\ell]$, then $D[j-1][\ell-1]\geq\delta-1$ and
$D[j-1][\ell]\geq\delta-1$ and $D[j][\ell-1]\geq\delta$ and at least one of
the previous inequalities is an equality. If $j\in F$ and $\beta[j]=w[\ell]$
then $D[j-1][\ell-1]\geq\delta$ and $D[j-1][\ell]\geq\delta-1$ and
$D[j][\ell-1]\geq\delta$ and at least one of the previous inequalities is an
equality.

Moving forward, assume now that $M_{d}[\delta]=j\neq-\infty$. This means that
$D[j][\ell]=\delta,$ and $D[j^{\prime\prime}][j^{\prime\prime}+d]>\delta$ for
all $j^{\prime\prime}>j$. By the observations above, there exists
$j^{\prime}\leq j$ such that $D[j^{\prime}][j^{\prime}+d]=\delta$ and the
longest common prefix of $\beta[j^{\prime}:|\beta|]$ and $w[j^{\prime}+d:n]$
has length $j-j^{\prime}+1$, i.e., it equals $\beta[j^{\prime}:j]$. The last
part of this statement means that once we have aligned $\beta[1:j^{\prime}]$
to $w[1:j^{\prime}+d]$, we can extend this alignment to an alignment of
$\beta[1:j]$ to $w[1:j+d]$ by simply leaving the symbols of
$\beta[j^{\prime}+1:j]$ unchanged.

Let us see now what this means for the elements of diagonals $d$, $d+1$, and
$d-1$.

Firstly, we consider the diagonal $d$. Here we have that $j^{\prime}\geq
M_{d}[\delta-1]+1$. Note that if $\delta-1$ appears on diagonal $d$ then
$M_{d}[\delta-1]\neq-\infty$.

Secondly, we consider the diagonal $d+1$. Here, for all rows $\ell$ with
$j^{\prime}\leq\ell\leq j$, we have that $D[\ell-1][\ell+d]\geq\delta-1$ and
$D[j^{\prime\prime}-1][j^{\prime\prime}+d]>\delta-1$, for all
$j^{\prime\prime}$ with $|\beta|\geq j^{\prime\prime}>j$. Therefore, if
$\delta-1$ appears on diagonal $d+1$, either $D[m][m+d+1]\leq d-1$ or
$M_{d+1}[\delta-1]\neq-\infty$ and $M_{d}[\delta-1]+1\leq j$.

Finally, we consider the diagonal $d-1$. Here, for all rows $\ell$ with
$j^{\prime}\leq\ell\leq j$, we have that $D[\ell][\ell+d-1]\geq\delta-1$ and
$D[j^{\prime\prime}][j^{\prime\prime}+d-1]\geq\delta$, for all
$j^{\prime\prime}$ with $m\geq j^{\prime\prime}>j$. Thus, either all elements
on the diagonal $d-1$ are $\geq\delta$, or $\delta-1$ occurs on diagonal $d-1$
and $M_{d-1}[\delta-1]\neq-\infty$. In the second case, when
$M_{d-1}[\delta-1]\neq-\infty$, we have that $j\geq M_{d-1}[\delta-1]$ as,
otherwise, we would have that
$D[M_{d-1}[\delta-1]][M_{d-1}[\delta-1]+d]\leq\delta$ and
$M_{d-1}[\delta-1]>j$, a contradiction.

Still on diagonal $d-1$, if $\delta$ occurs on it, then
$M_{d}[\delta]\neq-\infty$ holds. So, for $g\leq k-1$ with $F_{g}\leq
M_{d-1}[\delta]<F_{g+1}$, we have that $F_{g}\leq M_{d}[\delta]$. Indeed,
otherwise we would have two possibilities. If the path connecting $D[0][0]$ to
$D[M_{d-1}[\delta]][M_{d-1}[\delta]+d-1]$ via elements $\leq d$ intersects row
$F_{g}$ on $D[F_{g}][F_{g}+d^{\prime}]$ for some $d^{\prime}\leq d$, then
$D[F_{g}][F_{g}+d]\leq D[F_{g}][F_{g}+d^{\prime}]\leq\delta$ and $F_{g}>j$, a
contradiction. If the path connecting $D[0][0]$ to
$D[M_{d-1}[\delta]][M_{d-1}[\delta]+d-1]$ via elements $\leq d$ intersects row
$F_{g}$ on $D[F_{g}][F_{g}+d^{\prime}]$ for some $d^{\prime}>d$, then the
respective path will also intersect diagonal $d$ on a row $>j$ before reaching
$M_{d-1}[\delta]$, a contradiction with the fact that $j$ is the last row on
diagonal $d$ where we have an element $\leq\delta$.

So, for $M_{d}[\delta]$ to be relevant, we must have
$D[|\beta|][|\beta|+d+1]\geq\delta$ (so there exists no $k>0$ such that
$M_{d+1}[\delta-k]=|\beta|$). In this case, if $M_{d}[\delta]=j$, then the
following holds. The path (via elements $\leq d$) from $D[0][0]$ to
$D[j][j+d]$ goes through an element $D[g][g+d^{\prime}]=\delta-1$. If the last
such element on the respective path is on diagonal $d$, then it must be
$M_{d}[\delta-1]$. If it is on diagonal $d-1$, then either
$g=M_{d-1}[\delta-1]$ (and then the path moves on diagonal $d$ via an edge
corresponding to an insertion) or $g<M_{d-1}[\delta-1]$ (and then the path
moves on diagonal $d$ via an edge corresponding to an insertion); in this
second case, we could replace the considered path by a path connecting
$D[0][0]$ to $D[M_{d-1}[\delta-1]][M_{d-1}[\delta-1]+d-1]$ (via elements
$\leq\delta-1$), which then moves on diagonal $d$ via an edge corresponding to
an insertion, and continues along that diagonal (with edges corresponding to
letters left unchanged). If $D[g][g+d^{\prime}]$ is on diagonal $d+1$ (i.e.,
$d^{\prime}=d+1$) then, just like in the previous case, we can simply consider
the path connecting $D[0][0]$ to $D[M_{d+1}[\delta-1]][M_{d+1}[\delta-1]+d+1]$
(via elements $\leq\delta-1$), which then moves on diagonal $d$ via an edge
corresponding to a deletion, and then continues along diagonal $d$ (with edges
corresponding to letters left unchanged). If $D[g][g+d^{\prime}]$ is on none
of the diagonals $d-1,d,d+1$ then we reach diagonal $d$ by edges corresponding
to free insertions from some diagonal $d^{\prime\prime}<d$. The respective
path also intersects diagonal $d-1$ (when coming from $d^{\prime\prime}$ to
$d$ by free insertions), so diagonal $d-1$ contains $\delta$ and
$M_{d-1}[\delta]\neq\infty$, and we might simply consider as path between
$D[0][0]$ and $D[j][j+d]$ the path reaching diagonal $d-1$ on position
$D[F_{g}][F_{g}+d-1]$ (via elements $\leq\delta$), where $F_{g}\leq
M_{d-1}[\delta]<F_{g+1}$, which then moves on diagonal $d$ by an edge
corresponding to a free insertion, and then continues along $d$ (with edges
corresponding to letters left unchanged, as $F_{g}$ is greater or equal to the
row where the initial path intersected diagonal $d$). This analysis covers all
possible cases.

Computing $M_{d}[\delta]$. Therefore, if $M_{d}[\delta]$ is relevant (and, as
such, $M_{d}[\delta]\neq-\infty$), then $M_{d}[\delta]$ can be computed as
follows. Let $g$ be such that $F_{g}\leq M_{d-1}[\delta]<F_{g+1}$ (and $g=-1$
and $F_{g}=-\infty$ if $M_{d-1}[\delta]=-\infty$). Let
$H=\max\\{M_{d-1}[\delta-1],F_{g},M_{d}[\delta-1]+1,M_{d+1}[\delta-1]+1\\}$
(as explained, in the case we are discussing, at least one of these values is
not $-\infty$). Then we have that $j\geq H$ and the longest common prefix of
$\beta[H+1:|\beta|]$ and $w[H+d+1:n]$ is exactly $\beta[H+1:j]$ (or we could
increase $j$). So, to compute $j=M_{d}[\delta]$, we compute $H$ and then we
compute the longest common prefix $\beta[H+1:j]$ of $\beta[H+1:|\beta|]$ and
$w[H+d+1:n]$.

In general, $M_{d}[\delta]$ is not relevant either because there exists some
$s\geq 0$ and $\delta^{\prime}<\delta$ such that
$M_{d+s}[\delta^{\prime}]=|\beta|$ or because all elements of diagonal $d$ are
strictly greater than $\delta$. In the second case, we note that all values
$M_{d-1}[\delta-1]$, $F_{g}$, $M_{d}[\delta-1]$, and $M_{d+1}[\delta-1]$ must
be $-\infty$ (as otherwise the diagonal $d$ would contain an element equal to
$\delta$), so our computation of $M_{d}[\delta]$ returns $-\infty$ (which is
correct).

Now, based on these observations, we can see a way to compute the relevant
values $M_{d}[\delta]$, for $-|\beta|\leq d\leq n$ and $\delta\leq\Delta$
(without computing the matrix $D$).

We first construct the word $\beta$ and longest common prefix data structures
for the word $\beta w$, allowing us to compute
$\mathtt{LCP}(\beta[h:|\beta|],w[h+d:n])$, the length of the longest common
prefix of $\beta[h:|\beta|]$ and $w[h+d:n]$ for all $h$ and $d$.

Then, we will compute the values of $M_{d}[0]$ for all diagonals $d$.
Basically, we need to identify, if it exists, a path from $D[0][0]$ to
$D[M_{d}[0]][M_{d}[0]+d]$ which consists only of edges corresponding to
letters left unchanged, or to free insertions. By an analysis similar to the
one done above, we can easily show that $M_{0}[0]$ is
$\mathtt{LCP}(\beta[1:|\beta|],w[1:n])$ (which is $\geq 1$, by our
assumptions). Further, $M[d][0]=-\infty$ for $d<0$ and, for $d\geq 0$,
$M_{d}[0]=F_{g}+\mathtt{LCP}(\beta[F_{g}+1:|\beta|],w[F_{g}+1+d:n])$, where
$F_{g}\in F$ is such that $F_{g}\leq M_{d-1}[0]<F_{g+1}$ ($M_{d}[0]=-\infty$
if such an element $F_{g}$ does not exist).

Further, for $\delta$ from $1$ to $\Delta$ we compute all the values
$M_{d}[\delta]$, in order for $d$ from $-|\beta|+1$ to $n$. We first compute
the largest diagonal $d^{\prime}$ such that
$M_{d^{\prime}}[\delta-k]=|\beta|$, for some $k>0$. We will only compute
$M_{d}[\delta]$, for $d$ from $d^{\prime}+1$ to $n$. For each such diagonal
$d$, we compute $g$ such that $F_{g}\leq M_{d-1}[\delta]<F_{g+1}$ and
$H=\max\\{M_{d-1}[\delta-1],F_{g},M_{d}[\delta-1]+1,M_{d+1}[\delta-1]+1\\}$.
Then we set $M_{d}[\delta]$ to be
$H+\mathtt{LCP}(\beta[H+1:|\beta|],w[H+d+1:n])-1$.

Conclusions. This algorithm, which computes all relevant values
$M_{d}[\delta],$can be implemented in $O((n+m)\Delta)$ time, as discussed in
the Appendix (where also its pseudocode is given). As explained before, this
allows us to solve $\mathtt{MisMatch}_{\mathtt{Reg}}$ for the input
$(\alpha,w,\Delta)$. Moreover, if the instance can be answered positively, the
value $\delta$ for which $M_{n-|\beta|}[\delta]=|\beta|$ equals
$d_{\mathtt{ED}}(\alpha,w)$. ∎

The following result now follows.

######  Theorem 3.2 ()

$\mathtt{MinMisMatch}_{\mathtt{Reg}}$ can be solved in $O(n\Phi)$ time, where
$\Phi=d_{\mathtt{ED}}(\alpha,w)$.

The upper bounds reported in Theorems 3.1 and 3.2 are complemented by the
following conditional lower bound, known from the literature [3, Thm. 3] (see
Appendix).

######  Theorem 3.3 ()

$\mathtt{MisMatch}_{\mathtt{Reg}}$ can not be solved in time
$\mathcal{O}(|w|^{h}\Delta^{g})$ (or $\mathcal{O}(|w|^{h}|\alpha|^{g})$) where
$h+g=2-\epsilon$ with $\epsilon>0$, unless the Orthogonal Vectors Conjecture
fails.

It is worth noting that the lower bound from Theorem 3.3 already holds for
very restricted regular patterns, i.e., for $\alpha=xuy$, where $u$ is a
string of terminals and $x$ and $y$ are variables. Interestingly, a similar
lower bound (for such restricted patterns) does not hold in the case of the
Hamming distance, covered in [23].

Our second main result addresses another class of restricted patterns. To this
end, we consider the class of unary (or one-variable) patterns
$\mathtt{1Var}$, which is defined as follows: $\alpha\in\mathtt{1Var}$ if
there exists $x\in X$ such that $\mathtt{var}(\alpha)=\\{x\\}$. An example of
unary pattern is $\alpha_{1}=\mathtt{ab}x\mathtt{ab}xx\mathtt{baab}$.

We can show the following theorem.

######  Theorem 3.4 ()

$\mathtt{MisMatch}_{\mathtt{1Var}}$ is $W[1]$-hard w.r.t. the number of
occurrences of the single variable $x$ of the input pattern $\alpha$.

######  Proof (Sketch)

We begin by recalling the following problem: Without loss of generality, we
can assume that $\Delta\leq\sum_{i=1}^{k}|w_{i}|$ as, otherwise, the answer is
clearly yes (for instance, for $s=\varepsilon$ we have that
$\sum_{i=1}^{k}d_{\mathtt{ED}}(w_{i},\varepsilon)\leq\sum_{i=1}^{k}|w_{i}|$).
Similarly, we can assume that $|s|\leq\Delta+\max\\{|w_{i}|\mid
i\in\\{1,\ldots,k\\}\\}.$ In [36] it was shown that $\mathtt{MS}$ is NP-
complete even for binary input strings and W[1]-hard with respect to the
parameter $k$, the number of input strings.

We will reduce now $\mathtt{MS}$ to $\mathtt{MisMatch}_{\mathtt{1Var}}$, such
that an instance of $\mathtt{MS}$ with $k$ input strings is mapped to an
instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ with exactly $k$ occurrences
of the variable $x$ (the single variable occurring in the pattern).

Thus, we consider an instance of $\mathtt{MS}$ which consists in the $k$
binary strings $w_{1},\ldots,w_{k}\in\\{0,1\\}^{*}$ and the integer
$\Delta\leq\sum_{i=1}^{k}|w_{i}|$. The instance of
$\mathtt{MisMatch}_{\mathtt{1Var}}$ which we construct consists of a word $w$
and a pattern $\alpha$, such that $\alpha$ contains exactly $k$ occurrences of
a variable $x$, and both strings are of polynomial size w.r.t. the size of the
$\mathtt{MS}$-instance. Moreover, the bound on the $d_{\mathtt{ED}}(\alpha,w)$
defined in this instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ equals
$\Delta$. That is, if there exists a solution for the $\mathtt{MS}$-instance
such that $\sum_{i=1}^{k}d_{\mathtt{ED}}(w_{i},s)\leq\Delta$, then, and only
then, we should be able to find a solution of the
$\mathtt{MisMatch}_{\mathtt{1Var}}$-instance with
$d_{\mathtt{ED}}(\alpha,w)\leq\Delta$. The construction of the
$\mathtt{MisMatch}_{\mathtt{1Var}}$ instance is realized in such a way that
the word $w$ encodes the $k$ input strings for $\mathtt{MS}$, conveniently
separated by some long strings over two fresh symbols $\$,\\#$, while $\alpha$
can be obtained from $w$ by simply replacing each of the words $w_{i}$ by a
single occurrence of the variable $x$. Intuitively, in this way, for
$d_{\mathtt{ED}}(\alpha,w)$ to be minimal, $x$ should be mapped to the median
string of $\\{w_{1},\ldots,w_{k}\\}$. In this proof sketch, we just define the
reduction. The proof of its correctness is given in the Appendix.

For the strings $w_{1},\ldots w_{k}\in\\{0,1\\}^{*}$, let
$S=6(\sum_{i=1}^{k}|w_{i}|)$; clearly, $S\geq 6\Delta$. Let
$w=w_{1}(\$^{S}\\#^{S})^{S}w_{2}(\$^{S}\\#^{S})^{S}\ldots
w_{k}(\$^{S}\\#^{S})^{S}$ and $\alpha=\left(x(\$^{S}\\#^{S})^{S}\right)^{k}$.

The constructed instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ (i.e.,
$\alpha,w,\Delta$) is of polynomial size w.r.t. the size of the
$\mathtt{MS}$-instance (i.e., $\\{w_{1},\ldots,w_{k}\\},\Delta$). Therefore,
it (and our entire reduction) can be computed in polynomial time. Moreover, we
can show that the instance $(w,\alpha,\Delta)$ of
$\mathtt{MisMatch}_{\mathtt{1Var}}$ is answered positively if and only if the
original instance of $\mathtt{MS}$ is answered positively. Finally, as the
number of occurrences of the variable $x$ blocks in $\alpha$ is $k$, where $k$
is the number of input strings in the instance of $\mathtt{MS}$, and
$\mathtt{MS}$ is $W[1]$-hard with respect to this parameter, it follows that
$\mathtt{MisMatch}_{\mathtt{1Var}}$ is also $W[1]$-hard when the number of
occurrences of the variable $x$ in $\alpha$ is considered as parameter. The
statement follows. ∎

A simple corollary of Theorem 2.1 is the following:

######  Theorem 3.5 ()

$\mathtt{MisMatch}_{\mathtt{1Var}}$ and $\mathtt{MinMisMatch}_{\mathtt{1Var}}$
can be solved in $O(n^{3|\alpha|_{x}})$ time, where $x$ is the single variable
occurring in $\alpha$.

Clearly, finding a polynomial time algorithm for
$\mathtt{MisMatch}_{\mathtt{1Var}}$, for which the degree of the polynomial
does not depend on $|\alpha|_{x}$, would be ideal. Such an algorithm would be,
however, an FPT-algorithm for $\mathtt{MisMatch}_{\mathtt{1Var}}$,
parameterized by $|\alpha|_{x}$, and, by Theorem 3.4 and common parameterized
complexity assumptions, the existence of such an algorithm is unlikely. This
makes the straightforward result reported in Theorem 3.5 relevant, to a
certain extent.

##  4 Conclusion

Our results regarding the problem $\mathtt{MisMatch}$ for various classes of
patterns are summarized in Table 1, which highlights the differences to the
case of exact matching and to the case of approximate matching under Hamming
distance.

Table 1: Our new results are listed in column 4. The results overviewed in column 3 were all shown in [23]. We assume $|w|=n$ and $|\alpha|=m$. Class | $\mathtt{Match}(w,\alpha)$ | $\mathtt{MisMatch}(w,\alpha,\Delta)$ | $\mathtt{MisMatch}(w,\alpha,\Delta)$
---|---|---|---
|  |  for $d_{\mathtt{HAM}}(\cdot,\cdot)$ |  for $d_{\mathtt{ED}}(\cdot,\cdot)$
$\mathtt{Reg}$ |  $O(n)$ [folklore] |  $O(n\Delta)$, matching |  $O(n\Delta)$, matching
|  | cond. lower bound | cond. lower bound
$\mathtt{1Var}$ |  $O(n)$ [folklore] | $O(n)$ | $O(n^{3|\alpha|_{x}})$
$(\mathtt{var}(\alpha)=\\{x\\})$ |  |  |  W[1]-hard w.r.t. $|\alpha|_{x}$
$\mathtt{NonCross}$ |  $O(nm\log n)$ [15] | $O(n^{3}p)$ | NP-hard
$\mathtt{1RepVar}$ |  $O(n^{2})$ [15] | $O(n^{k+2}m)$ |  NP-hard for $k\geq 1$
$k$=# $x$-blocks |  |  W[1]-hard w.r.t. $k$ |
$\mathtt{kLOC}$ |  $O(mkn^{2k+1})$ [12] | $O(n^{2k+2}m)$ |  NP-hard for $k\geq 1$
|  W[1]-hard w.r.t. $k$ |  W[1]-hard w.r.t. $k$ |
$\mathtt{kSCD}$ |  $O(m^{2}n^{2k})$ [15] |  NP-hard for $k\geq 2$ |  NP-hard for $k\geq 1$
|  W[1]-hard w.r.t. $k$ |  |
$\mathtt{kRepVar}$ |  $O(n^{2k})$ [15] |  NP-hard for $k\geq 1$ |  NP-hard for $k\geq 1$
|  W[1]-hard w.r.t. $k$ |  |
$k$-bounded |  $O(n^{2k+4})$ [37] |  NP-hard for $k\geq 3$ |  NP-hard for $k\geq 1$
treewidth |  W[1]-hard w.r.t. $k$ |  |

Note that the results reported in the first row of the rightmost column of
this table are based on Theorem 3.1 (the upper bound) and Theorem 3.3 (the
lower bound). The rest of the cells of that rightmost column are all
consequences of the result of Theorem 3.4. Indeed, the classes of patterns
covered in this table, which are presented in detail in [23], are defined
based on a common idea. In the pattern $\alpha$, we identify for each variable
$x$ the $x$-blocks: maximal factors of $\alpha$ (w.r.t. length) which contain
only the variable $x$ and terminals, and start and end with $x$. Then, classes
of patterns are defined based on the way the blocks defined for all variables
occurring in $\alpha$ are interleaved. However, in the patterns of all these
classes, there may exist at least one variable which occurs an unbounded
number of times, i.e., they all include the class of unary patterns.
Therefore, the hardness result proved for unary patterns carries over and, as
the structural parameters used to define those classes do not take into
account the overall number of occurrences of a variable, but rather the number
of blocks for the variables (or the way they are interleaved), we obtain NP-
hardness for $\mathtt{MisMatch}$ for that class, even if the structural
parameters are trivial.

While our results, together with those reported in [23], seem to completely
characterize the complexity of $\mathtt{MisMatch}$ and $\mathtt{MinMisMatch}$
under both Hamming and edit distances, there are still some directions for
future work. Firstly, in [24] the fine-grained complexity of computing the
median string under edit distance for $k$ input strings is discussed. Their
main result, a lower bound, was only shown for inputs over unbounded
alphabets; it would be interesting to see if it still holds for alphabets of
constant size. Moreover, it would be interesting to obtain similar lower
bounds for $\mathtt{MisMatch}_{\mathtt{1Var}}$, as the two problem seem
strongly related. To that end, it would be interesting if the upper bound of
Theorem 3.5 can be improved, and brought closer to the one reported for median
string in [38]. Secondly, another interesting problem is related to Theorem
3.3. The lower bound we reported in that theorem holds for regular patterns
with a constant number of variables (e.g., two variables). It is still open
what is the complexity of $\mathtt{MisMatch}$ for regular patterns with a
constant number of variables under Hamming distance.

## References

  * [1] Amir, A., Nor, I.: Generalized function matching. J. Discrete Algorithms 5, 514–523 (2007). https://doi.org/10.1016/j.jda.2006.10.001
  * [2] Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21(1), 46–62 (1980). https://doi.org/10.1016/0022-0000(80)90041-0, https://doi.org/10.1016/0022-0000(80)90041-0
  * [3] Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput. 47(3), 1087–1097 (2018). https://doi.org/10.1137/15M1053128, https://doi.org/10.1137/15M1053128
  * [4] Bernardini, G., Chen, H., Loukides, G., Pisanti, N., Pissis, S.P., Stougie, L., Sweering, M.: String Sanitization Under Edit Distance. In: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). LIPIcs, vol. 161, pp. 7:1–7:14 (2020). https://doi.org/10.4230/LIPIcs.CPM.2020.7
  * [5] Bernardini, G., Pisanti, N., Pissis, S.P., Rosone, G.: Approximate pattern matching on elastic-degenerate text. Theor. Comput. Sci. 812, 109–122 (2020). https://doi.org/10.1016/j.tcs.2019.08.012, https://doi.org/10.1016/j.tcs.2019.08.012
  * [6] Bringmann, K.: Fine-grained complexity theory (tutorial). In: Proc. 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019\. LIPIcs, vol. 126, pp. 4:1–4:7 (2019). https://doi.org/10.4230/LIPIcs.STACS.2019.4
  * [7] Câmpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14, 1007–1018 (2003). https://doi.org/10.1142/S012905410300214X
  * [8] Charalampopoulos, P., Kociumaka, T., Mozes, S.: Dynamic String Alignment. In: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). LIPIcs, vol. 161, pp. 9:1–9:13 (2020). https://doi.org/10.4230/LIPIcs.CPM.2020.9
  * [9] Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster approximate pattern matching: A unified approach. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. pp. 978–989. IEEE (2020). https://doi.org/10.1109/FOCS46700.2020.00095, https://doi.org/10.1109/FOCS46700.2020.00095
  * [10] Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster pattern matching under edit distance. CoRR abs/2204.03087 (2022). https://doi.org/10.48550/arXiv.2204.03087, https://doi.org/10.48550/arXiv.2204.03087
  * [11] Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press (2007). https://doi.org/10.1017/CBO9780511546853
  * [12] Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: Proc. 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017. LIPIcs, vol. 93, pp. 24:1–24:14 (2017). https://doi.org/10.4230/LIPIcs.FSTTCS.2017.24
  * [13] Fagin, R., Kimelfeld, B., Reiss, F., Vansummeren, S.: Document spanners: A formal approach to information extraction. J. ACM 62(2), 12:1–12:51 (2015). https://doi.org/10.1145/2699442, https://doi.org/10.1145/2699442
  * [14] Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Revisiting Shinohara’s algorithm for computing descriptive patterns. Theor. Comput. Sci. 733, 44–54 (2018). https://doi.org/10.1016/j.tcs.2018.04.035, https://doi.org/10.1016/j.tcs.2018.04.035
  * [15] Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Pattern matching with variables: Efficient algorithms and complexity results. ACM Trans. Comput. Theory 12(1), 6:1–6:37 (2020). https://doi.org/10.1145/3369935, https://doi.org/10.1145/3369935
  * [16] Fernau, H., Schmid, M.L.: Pattern matching with variables: A multivariate complexity analysis. Inf. Comput. 242, 287–305 (2015). https://doi.org/10.1016/j.ic.2015.03.006
  * [17] Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. Theory Comput. Syst. 59(1), 24–51 (2016). https://doi.org/10.1007/s00224-015-9635-3, https://doi.org/10.1007/s00224-015-9635-3
  * [18] Freydenberger, D.D.: Extended regular expressions: Succinctness and decidability. Theory of Comput. Syst. 53, 159–193 (2013). https://doi.org/10.1007/s00224-012-9389-0
  * [19] Freydenberger, D.D.: A logic for document spanners. Theory Comput. Syst. 63(7), 1679–1754 (2019). https://doi.org/10.1007/s00224-018-9874-1, https://doi.org/10.1007/s00224-018-9874-1
  * [20] Freydenberger, D.D., Holldack, M.: Document spanners: From expressive power to decision problems. Theory Comput. Syst. 62(4), 854–898 (2018). https://doi.org/10.1007/s00224-017-9770-0, https://doi.org/10.1007/s00224-017-9770-0
  * [21] Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. J. Comput. Syst. Sci. 105, 1–39 (2019). https://doi.org/10.1016/j.jcss.2019.04.001, https://doi.org/10.1016/j.jcss.2019.04.001
  * [22] Friedl, J.E.F.: Mastering Regular Expressions. O’Reilly, Sebastopol, CA, third edn. (2006)
  * [23] Gawrychowski, P., Manea, F., Siemer, S.: Matching patterns with variables under hamming distance. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021. LIPIcs, vol. 202, pp. 48:1–48:24 (2021). https://doi.org/10.4230/LIPIcs.MFCS.2021.48, https://doi.org/10.4230/LIPIcs.MFCS.2021.48
  * [24] Hoppenworth, G., Bentley, J.W., Gibney, D., Thankachan, S.V.: The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance. In: 28th Annual European Symposium on Algorithms (ESA 2020). LIPIcs, vol. 173, pp. 61:1–61:19 (2020). https://doi.org/10.4230/LIPIcs.ESA.2020.61
  * [25] Kärkkäinen, J., Sanders, P.: Simple linear work suffix array construction. In: Proc. 30th International Colloquium Automata, Languages and Programming, ICALP 2003. LNCS, vol. 2719, pp. 943–955 (2003). https://doi.org/10.1007/3-540-45061-0_73
  * [26] Kärkkäinen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918–936 (2006). https://doi.org/10.1145/1217856.1217858, https://doi.org/10.1145/1217856.1217858
  * [27] Kleest-Meißner, S., Sattler, R., Schmid, M.L., Schweikardt, N., Weidlich, M.: Discovering event queries from traces: Laying foundations for subsequence-queries with wildcards and gap-size constraints. In: 25th International Conference on Database Theory, ICDT 2022. LIPIcs, vol. 220, pp. 18:1–18:21 (2022). https://doi.org/10.4230/LIPIcs.ICDT.2022.18, https://doi.org/10.4230/LIPIcs.ICDT.2022.18
  * [28] Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. Journal of Algorithms 10(2), 157–169 (1989). https://doi.org/https://doi.org/10.1016/0196-6774(89)90010-2, https://www.sciencedirect.com/science/article/pii/0196677489900102
  * [29] Levenshtein, V.: Binary codes capable of correcting spurious insertions and deletions of ones. Problems of Information Transmission 1, 8–17 (1965)
  * [30] Levenshtein, V.I.: Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady 10, 707 (Feb 1966)
  * [31] Lothaire, M.: Combinatorics on Words. Cambridge University Press (1997). https://doi.org/10.1017/CBO9780511566097
  * [32] Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press (2002). https://doi.org/10.1017/CBO9781107326019
  * [33] Manea, F., Schmid, M.L.: Matching patterns with variables. In: Proc. 12th International Conference Combinatorics on Words, WORDS 2019. LNCS, vol. 11682, pp. 1–27 (2019). https://doi.org/10.1007/978-3-030-28796-2_1
  * [34] Mieno, T., Pissis, S.P., Stougie, L., Sweering, M.: String sanitization under edit distance: Improved and generalized. In: 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021. LIPIcs, vol. 191, pp. 19:1–19:18 (2021)
  * [35] Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31–88 (2001). https://doi.org/10.1145/375360.375365, https://doi.org/10.1145/375360.375365
  * [36] Nicolas, F., Rivals, E.: Hardness results for the center and median string problems under the weighted and unweighted edit distances. J. Discrete Algorithms 3(2-4), 390–415 (2005). https://doi.org/10.1016/j.jda.2004.08.015, https://doi.org/10.1016/j.jda.2004.08.015
  * [37] Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. Inf. Comput. 239, 87–99 (2014). https://doi.org/10.1016/j.ic.2014.08.010, https://doi.org/10.1016/j.ic.2014.08.010
  * [38] Sankoff, D.: Minimal mutation trees of sequences. SIAM Journal on Applied Mathematics 28(1), 35–42 (1975). https://doi.org/10.1137/0128004, https://doi.org/10.1137/0128004
  * [39] Schmid, M.L.: A note on the complexity of matching patterns with variables. Inf. Process. Lett. 113(19), 729–733 (2013). https://doi.org/10.1016/j.ipl.2013.06.011
  * [40] Schmid, M.L., Schweikardt, N.: A purely regular approach to non-regular core spanners. In: Proc. 24th International Conference on Database Theory, ICDT 2021\. LIPIcs, vol. 186, pp. 4:1–4:19 (2021). https://doi.org/10.4230/LIPIcs.ICDT.2021.4
  * [41] Schmid, M.L., Schweikardt, N.: Document spanners - A brief overview of concepts, results, and recent developments. In: PODS ’22: International Conference on Management of Data. pp. 139–150. ACM (2022). https://doi.org/10.1145/3517804.3526069, https://doi.org/10.1145/3517804.3526069
  * [42] Shinohara, T.: Polynomial time inference of pattern languages and its application. In: Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, MFCS. pp. 191–209 (1982)
  * [43] Shinohara, T., Arikawa, S.: Pattern inference. In: Algorithmic Learning for Knowledge-Based Systems, GOSLER Final Report. LNAI, vol. 961, pp. 259–291 (1995)
  * [44] Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2-3), 357–365 (2005). https://doi.org/10.1016/j.tcs.2005.09.023, https://doi.org/10.1016/j.tcs.2005.09.023

##  Appendix 0.A Computational Model

The computational model we use to describe our results is the standard unit-
cost RAM with logarithmic word size: for an input of size $n$, each memory
word can hold $\log n$ bits. Arithmetic and bitwise operations with numbers in
$[1:n]$ are, thus, assumed to take $O(1)$ time. Numbers larger than $n$, with
$\ell$ bits, are represented in $O(\ell/\log n)$ memory words, and working
with them takes time proportional to the number of memory words on which they
are represented. In all the problems, we assume that we are given a word $w$
and a pattern $\alpha$, with $|w|=n$ and $|\alpha|=m$, over a terminal-
alphabet $\Sigma=\\{1,2,\ldots,\sigma\\}$, with $|\Sigma|=\sigma\leq n+m$. The
variables are chosen from the set $\\{x_{1},\ldots,x_{m}\\}$ and can be
encoded as integers between $n+1$ and $n+m$. That is, we assume that the
processed words are sequences of integers (called letters or symbols), each
fitting in $O(1)$ memory words. This is a common assumption in string
algorithms: the input alphabet is said to be an integer alphabet. For
instance, the same assumption was also used for developing efficient
algorithms for $\mathtt{Match}$ in [14, 23]. For a more detailed general
discussion on this computational model see, e.g., [11].

##  Appendix 0.B Longest Common Prefix data structure (LCP)

Given a word $w$, of length $n$, we can construct in $O(n)$-time longest
common prefix-data structures which allow us to return in $O(1)$-time the
value $LCP_{w}(i,j)=max\\{|v|\mid v\mbox{ is a prefix of both }w[i:n]\mbox{
and }w[j:n]\\}$. See [25, 26] and the references therein. Now, given a word
$w$, of length $n$, and a word $\beta$, of length $m$, we can construct in
$O(n+m)$-time data structures which allow us to return in $O(1)$-time the
value $\mathtt{LCP}(w[i:n],\beta[j:m])$, the length of the longest common
prefix of the strings $\beta[j:m]$ and $w[i:n]$ for all $j$ and $i$. In other
words, $\mathtt{LCP}(w[i:n],\beta[j:m])=max\\{|v|\mid v\mbox{ is a prefix of
both }w[i:n]\mbox{ and }\beta[j:m]\\}$. This is achieved by constructing
$LCP_{w\beta}$-data structures for the word $w\beta$, as above, and noting
that $\mathtt{LCP}(w[i:n],\beta[j:m])=\min(LCP_{w\beta}(i,n+j),n-i)$.

##  Appendix 0.C Proofs

### Proof of Theorem 2.1

See 2.1

###### Proof

We only give the proof for $\mathtt{MinMisMatch}_{PAT}$.

Assume the input pattern is $\alpha=u_{0}x_{1}u_{1}\ldots x_{k_{2}}u_{k_{2}}$
from $PAT_{\Sigma}$, where $x_{i}$ is a variable, for
$i\in\\{1,\ldots,{k_{2}}\\}$, and $w_{i}\in\Sigma^{*}$ a terminal word, for
$i\in\\{0,\ldots,{k_{2}}\\}$. Note that there might be the case that
$x_{i}=x_{j}$ for some $i\neq j$, as there are no restrictions on the
structure of the pattern $\alpha$.

We make several observations.

Let $h$ be a substitution of the variables from $\alpha$, such that
$h(x_{i})=t_{i}$, for $i\in\\{1,\ldots,{k_{2}}\\}$. Then,
$h(\alpha)=u_{0}t_{1}u_{1}\ldots t_{k_{2}}u_{k_{2}}$. When computing the edit
distance $d_{\mathtt{ED}}(h(\alpha),w)$, one obtains a factorization of
$w=w_{0}w^{\prime}_{1}w_{1}\ldots w^{\prime}_{k_{2}}w_{k_{2}}$ such that the
optimal sequence of edits transforming $h(\alpha)$ into $w$ transforms $u_{i}$
into $w_{i}$, for $i\in\\{0,\ldots,{k_{2}}\\}$, and $t^{\prime}_{i}$ into
$w_{i}$, for $i\in\\{1,\ldots,{k_{2}}\\}$.

Now, let $V_{x}=\\{i\in\\{1,\ldots,{k_{2}}\\}\mid x_{i}=x\\}$ and assume $h$
is a substitution of the variables from $\alpha$ such that
$d_{\mathtt{ED}}(h(\alpha),w)$ is minimal w.r.t. all possible substitutions of
the variables of $\alpha$. Moreover, let $h(x_{i})=t_{i}$ for
$i\in\\{1,\ldots,{k_{2}}\\}$. As before, there exists a factorization of
$w=w_{0}w^{\prime}_{1}w_{1}\ldots w^{\prime}_{k_{2}}w_{k_{2}}$ such that the
optimal sequence of edits transforming $h(\alpha)$ into $w$ transforms $u_{i}$
into $w_{i}$, for $i\in\\{0,\ldots,{k_{2}}\\}$, and $t^{\prime}_{i}$ into
$w_{i}$, for $i\in\\{1,\ldots,{k_{2}}\\}$. In this case, from the fact that
$h$ is optimal, it is immediate that $h(x)=s_{x}$ where $s_{x}$ is the median
string of $\\{w^{\prime}_{i}\mid i\in V_{x}\\}$.

Based on these observations, we can use the following algorithm solving
$\mathtt{MinMisMatch}_{PAT}$.

For each $x\in\mathtt{var}(\alpha)$, define
$V_{x}=\\{i\in\\{1,\ldots,{k_{2}}\\}\mid x_{i}=x\\}$. For each factorization
$f$ of $w=w_{0}w^{\prime}_{1}w_{1}\ldots w^{\prime}_{k_{2}}w_{k_{2}}$ and for
each variable $x$: compute the median string $s_{x}$ of $\\{w^{\prime}_{i}\mid
i\in V_{x}\\}$; define the substitution $h_{f}$ which maps $x$ to $s_{x}$ for
all $x$; compute the edit distance $d_{\mathtt{ED}}(h_{f}(\alpha),w)$. After
considering each possible factorization $f$, return the substitution $h_{f}$
for which $d_{\mathtt{ED}}(h_{f}(\alpha),w)$ is minimal.

In the above algorithm, to compute the median string of $\\{w^{\prime}_{i}\mid
i\in V_{x}\\}$, we use the algorithm of [38]. This algorithm runs in
$O(\ell_{x}^{|V_{x}|})$, where $\ell_{x}=\max\\{|w^{\prime}_{i}|\mid i\in
V_{x}\\}$. Therefore, the running time of our algorithm can be upper bounded
by $O(n^{2{k_{2}}}n^{k_{1}})$, so also by $O(n^{2{k_{2}}+k_{1}})$. ∎

### Algorithms from the proof of Theorem 3.1

#### Computing matrix $D[\cdot][\cdot]$.

The elements of the matrix $D[\cdot][\cdot]$ can be computed by dynamic
programming. The base cases are $D[j][0]=j$, for all $j\leq\beta$ and
$D[0][\ell]=\ell$. In the case of computing $D[0][\ell]$, we simply insert all
the letters of $w[1:\ell]$ in $\beta[1:0]=\varepsilon$, while in the case of
$D[j][0]$ we are deleting all letters from $\beta[1:j]$ (and, if we refer to
the edits in $\alpha$, where we also have variables, then we substitute all
the variables of the prefix of $\alpha$ which corresponds to $\beta[1:j]$ by
the empty word, as well).

The rest of the elements of $D[\cdot][\cdot]$ are now computed according to
two cases.

Firstly, we consider the computation of $D[j][\ell]$ for $j\notin F$. In this
case, we cannot use the aforementioned free insertions, so the element
$D[j][\ell]$ is computed as in the case of computing the usual edit distance
between two strings.

$D[j][\ell]=min\begin{cases}D[j-1][\ell]+1,&\text{$\beta[j]$ is deleted in the
alignment of $\beta[1:j]$}\\\ $ $&\text{to $w[1:\ell]$};\\\
D[j][\ell-1]+1,&\text{$w[\ell]$ is inserted after position $j$ of $\beta$ in
}\\\ $ $&\text{the alignment of $\beta[1:j]$ to $w[1:\ell]$};\\\
D[j-1][\ell-1]+1,&\text{$\beta[j]$ is substituted by $w[j]$ in}\\\ &\text{the
alignment of $\beta[1:j]$ to $w[1:\ell]$};\\\ D[j-1][\ell-1],&\text{$\beta[j]$
is left unchanged in the alignment}\\\ $ $&\text{of $\beta[1:j]$ to
$w[1:\ell]$ because $\beta[j]=w[\ell]$}.\\\ \end{cases}$

The more interesting case is when $j\in F$ and we can use free insertions.
Naturally, our starting point is still represented by the four possible cases
based on which we computed $D[j][\ell]$ when $j\notin F$. However, the case
corresponding to the insertion of $w[\ell]$ to extend an alignment of
$\beta[1:j]$ and $w[1:\ell-1]$ to an alignment of $\beta[1:j]$ and $w[1:\ell]$
can now be obtained by a free insertion, instead of an insertion of cost $1$.
This brings us to the main difference between the two cases. In this case, an
alignment between $\beta[1:j]$ and $w[1:\ell]$ can be obtained as follows. We
first obtain an alignment of $\beta[1:j]$ to some prefix $w[1:\ell-k]$ of $w$
and then use free insertions to append $w[\ell-k+1:\ell]$ to the edited
pattern, and, as such, obtain $w[1:\ell]$. But, this also means that we first
obtain an alignment of $\beta[1:j]$ to some prefix $w[1:\ell-k]$ of $w$ and
then use free insertions to append $w[\ell-k+1:\ell-1]$ to the edited pattern,
and, as such, obtain an alignment of the pattern to $w[1:\ell-1]$, and then
insert (again, without counting this towards the edit distance) $w[\ell]$ to
obtain $w[\ell-k+1:\ell]$. Thus, in this case, an alignment between
$\beta[1:j]$ and $w[1:\ell]$ which uses free insertions corresponding to the
position $j\in F$ is obtained from an alignment between $\beta[1:j]$ and
$w[1:\ell-1]$ followed by an additional free insertion. We obtain, as such,
the following recurrence relation for $D[j][\ell]$, when $j\in F$:

$D[j][\ell]=min\begin{cases}D[j-1][\ell]+1,&\text{$\beta[j]$ is deleted};\\\
D[j-1][\ell-1]+1,&\text{$\beta[j]$ is substituted by $w[\ell]$, if
$\beta[j]\neq w[\ell]$};\\\ D[j-1][\ell-1],&\text{$\beta[j]$ is left
unchanged, if $\beta[j]=w[\ell]$};\\\ D[j][\ell-1],&\text{$w[\ell]$ is
inserted after position $j$, for free}.\\\ \end{cases}$

Using the two recurrence relation above, we can compute the elements of the
matrix $D$ by dynamic programming (for $j$ from $0$ to $m-k$, for $\ell$ from
$0$ to $n$) in $O(nm)$ time.

Moreover, by tracing back the computation of $D[m-k][n]$, we obtain a path
consisting of elements of the matrix, leading from $D[0][0]$ to $D[m-k][n]$,
which encodes the edits needed to transform $\beta$ into $w$. An edge between
$D[j-1][\ell]$ and $D[j][\ell]$ corresponds to the deletion of $\beta[j]$; and
edge between $D[j-1][\ell-1]$ and $D[j][\ell]$ corresponds to a substitution
of $\beta[j]$ by $w[\ell]$, or to the case where $\beta[j]$ and $w[\ell]$ are
left unchanged, and will be aligned in the end. Moreover, an edge between
$D[j][\ell-1]$ and $D[j][\ell]$ corresponds to an insertion of $w[\ell]$ after
position $j$ in $\beta$; this can be a free insertion too (and part of the
image of a variable of $\alpha$), but only when $j\in F$.

A listing of an algorithm computing $D[\cdot][\cdot]$ is given in Figure 1.

Input: $w,\alpha$

Output: minimal edit distance between $\alpha$ and $w$ in $\mathcal{O}(nm)$

1 compute $\beta$ and the set $F$;

2 for  _$j\leftarrow[0$ to $|\beta|]$_ do

3 $D[j][0]\leftarrow j$;

4

5 end for

6for  _$\ell\leftarrow[0$ to $n]$_ do

7 $D[0][\ell]\leftarrow\ell$;

8

9 end for

10$g\leftarrow 0\;$

11 for  _$j\leftarrow[0$ to $|\beta|]$_ do

12 if  _$j=F_{g}$_ then

13 for  _$\ell\leftarrow[0$ to $n]$_ do

14 $D[j][\ell]\leftarrow min\begin{cases}D[j][\ell-1],&\text{free
insertion}\\\ D[j-1][\ell]+1,&\text{deletion}\\\
D[j-1][\ell-1]+1,&\text{substitution}\\\ D[j-1][\ell-1],&\text{if
}w[\ell]=\beta[j]\\\ \end{cases}\;$

15 end for

16 $g\leftarrow g+1\;$

17 else

18 for  _$\ell\leftarrow[0$ to $n]$_ do

19 $D[j][\ell]\leftarrow min\begin{cases}D[j][\ell-1]+1,&\text{insertion}\\\
D[j-1][\ell]+1,&\text{deletion}\\\ D[j-1][\ell-1]+1,&\text{substitution}\\\
D[j-1][\ell-1],&\text{if }w[\ell]=\beta[j]\\\ \end{cases}\;$

20 end for

21

22 end if

23

24 end for

return $D[|\beta|][n]$

Figure 1: Algorithm to compute $D[\cdot][\cdot]$ in $\mathcal{O}(nm)$ time.

#### Data structures for computing $M_{d}[\delta]$.

We first use a linear time algorithm for the computation of the longest common
prefix data structures for $\beta$ and $w$ (see the section of this Appendix
about such data structures and [26]). Secondly, we use an auxiliary array $G$
of size $|\beta|+1$, which stores for each positive integer $i\leq\beta$ the
value $G[i]=\max\\{g\mid F_{g}\leq i\\}$, and can be computed in linear time.
This allows us to efficiently retrieve the values $F_{g}$. Finally, while
computing the values $M_{d}[\delta]$, for $d$ and $\delta$, we can maintain
the value $d^{\prime}$ of the greatest diagonal such that there exist $k$ with
$M_{d^{\prime}}[\delta-k]=|\beta|$: when we are done with computing all the
values $M_{d}[\delta-1]$, for all $d$, we simply check if we need to update
$d^{\prime}$ because we might have found some $d^{\prime\prime}>d^{\prime}$
for which $M_{d^{\prime\prime}}[\delta-1]=|\beta|$.

#### Computing $M_{d}[\delta]$.

The algorithm for computing the relevant values $M_{d}[\Delta]$ and how these
are used to solve Problem $\mathtt{MisMatch}_{\mathtt{Reg}}$ is given in
Figure 2.

Input: $w,\alpha$

Output: minimal edit distance between $\alpha$ and $w$ in
$\mathcal{O}((n+m)\Delta)$

1 construct $\beta$;

2 construct $F$;

3 init $g\leftarrow-1$;

4 construct $LCP_{\beta,w}$;

5 for  _$d\leftarrow[-|\beta|$ to $0]$_ do

6 $M_{d}[0]\leftarrow-\infty$;

7

8 end for

9$M_{0}[0]\leftarrow LCP(\beta[1:|\beta|],w[1:n])$;

10 compute $g$ such that $F_{g}\leq M_{0}[0]<F_{g+1}$ ($g\leftarrow-1$ if
$F_{0}>M_{0}[d]$);

11 if  _$g=-1$_ then

12 for  _$d\leftarrow[1$ to $n]$_ do

13 $M_{d}[0]\leftarrow-\infty$;

14

15 end for

16

17else

18 for  _$d\leftarrow[1$ to $n]$_ do

19 $M_{d}[0]\leftarrow
F_{g}+\mathtt{LCP}(\beta[F_{g}+1:|\beta|],w[F_{g}+1+d:n])$;

20 update $g$ such that $F_{g}\leq M_{d}[0]<F_{g+1}$;

21

22 end for

23

24 end if

25$g\leftarrow-1$;

26 compute $d^{\prime}=\min\\{d\leq n\mid M_{d}[0]=m\\}$;

27 for  _$\delta\leftarrow[1$ to $\Delta]$_ do

28 for  _$d\leftarrow[d^{\prime}+1$ to $n]$_ do

29 update $g$ such that $F_{g}\leq M_{d-1}[\delta]<F_{g+1}$;

30 $H\leftarrow max\begin{cases}M_{d-1}[\delta-1],&\text{diagonal below}\\\
F_{g},&\text{for $F_{g}$ with $F_{g}\leq M_{d-1}[\delta]<F_{g+1}$}\hskip
14.22636pt;\\\ M[d][\delta-1]+1,&\text{same diagonal}\\\
M[d+1][\delta-1]+1,&\text{diagonal above}\\\ \end{cases}$
$M[d][\delta]\leftarrow H+\mathtt{LCP}(\beta[H+1:|\beta|],w[H+d+1:n])-1$;

31 if  _$(d=n-|\beta|)~{}\wedge~{}(M[d][\delta]=|\beta|)$_ then

32 return $\delta$;

33

34 end if

35

36 end for

37 maintain $d^{\prime}=\min\\{d^{\prime\prime}\leq|\beta|\mid
M_{d^{\prime\prime}}[\delta-s]=|\beta|$ for some $s\geq 0\\}$;

38

39 end for

40return No solution with $\Delta$ edit operations.;

Figure 2: Algorithm to compute the relevant values of $M$ in
$\mathcal{O}((n+m)\Delta)$ time.

### Proof of Theorem 3.2

See 3.2

###### Proof

We use the algorithm of Theorem 3.1 for $\Delta=2^{i}$, for increasing values
of $i$ starting with $1$ and repeating until the algorithm returns a positive
answer and computes $\Phi=d_{\mathtt{ED}}(\alpha,w)$. The algorithm is clearly
correct. Moreover, the value of $i$ which was considered last is such that
$2^{i-1}<\Phi\leq 2^{i}$. So $i=\lceil\log_{2}\Phi\rceil$, and the total
complexity of our algorithm is
$O(n\sum_{i=1}^{\lceil\log_{2}\Phi\rceil}2^{i})=O(n\Phi)$. ∎

### Lower bound for $\mathtt{MisMatch}_{\mathtt{Reg}}$

The results of Theorems 3.1 and 3.2 are complemented by the following lower
bound, known from the literature [3]. Firstly, we recall the $\mathtt{OV}$
problem.

It is clear that, for input sets $U$ and $V$ as in the above definition, one
can solve $\mathtt{OV}$ trivially in $\mathcal{O}(n^{2}d)$ time. The following
conditional lower bound is known.

######  Lemma 1 ($\mathtt{OV}$-Conjecture)

$\mathtt{OV}$ can not be solved in $\mathcal{O}(n^{2-\epsilon}d^{c})$ for any
$\epsilon>0$ and constant $c$, unless the Strong Exponential Time Hypothesis
(SETH) fails.

See [6, 44] and the references therein for a detailed discussion regarding
conditional lower bounds related to OV. In this context, the following result
is an immediate consequence of [3, Thm. 3]. See 3.3

### Proof of Theorem 3.4

See 3.4 Before starting the proof of Theorem 3.4 we need the following
technical lemma.

######  Lemma 2 ()

Let $\$$ and $\\#$ be two letters and let $S$, $g$, and $\ell$ be integers. If
$g\geq 0$, $2g\leq S$, $\frac{S}{2}\leq\ell-g$, and $\ell\leq S$ then:

  1. 1.

$d_{\mathtt{ED}}(\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell},(\$^{S}\\#^{S})^{S})=g+(S-\ell);$

  2. 2.

$d_{\mathtt{ED}}(\$^{\ell}\\#^{S}(\$^{S}\\#^{S})^{S-1}\\#^{g},(\$^{S}\\#^{S})^{S})=g+(S-\ell).$

###### Proof

We only show the first claim, as the second follows identically (as it is
symmetrical).

Firstly, it is clear that $g+(S-\ell)$ edits suffice to transform
$\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell}$ into $(\$^{S}\\#^{S})^{S}$.

Now, we will show that we cannot transform
$\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell}$ into $(\$^{S}\\#^{S})^{S}$ with
fewer than $S-\ell+g$ edits.

Note that from $\frac{S}{2}\leq\ell-g$ we get $\ell\geq g+(S-\ell)$. So, the
suffix $\\#^{S}$ of $(\$^{S}\\#^{S})^{S}$ must be obtained by a series of
edits from a suffix of the suffix $\$^{S}\\#^{\ell}$ of
$\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell}$. This means that at least
$S-\ell$ edits must be performed in the respective suffix to obtain $S$
symbols $\\#$. This leaves us with at most $g$ edits remaining to obtain
$(\$^{S}\\#^{S})^{S-1}\$^{S}$. In particular, this means that the prefix
$\$^{S}\\#^{S}$ of $(\$^{S}\\#^{S})^{S-1}\$^{S}$ must be obtained from a
prefix of the prefix $\$^{g}\$^{S}\\#^{S}$ of
$\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell}$. As, in the best case, $g$ $\$$
symbols need to be substituted or removed, it follows that we need to use $g$
edits to obtain the prefix $\$^{S}\\#^{S}$ of $(\$^{S}\\#^{S})^{S}$. As such,
we already had to use $g+(S-\ell)$ edits to transform
$\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell}$ into $(\$^{S}\\#^{S})^{S}$, so
it cannot be done with fewer edits. The conclusion follows. ∎

We can now proceed with the proof of Theorem 3.4.

###### Proof

Preliminaries. We begin by recalling the following problem: Without loss of
generality, we can assume that $\Delta\leq\sum_{i=1}^{k}|w_{i}|$ as,
otherwise, the answer is clearly yes (for instance, for $s=\varepsilon$ we
have that
$\sum_{i=1}^{k}d_{\mathtt{ED}}(w_{i},\varepsilon)\leq\sum_{i=1}^{k}|w_{i}|$).
Similarly, we can assume that $|s|\leq\Delta+\max\\{|w_{i}|\mid
i\in\\{1,\ldots,k\\}\\}.$

In [36] it was shown that $\mathtt{MS}$ is NP-complete even for binary input
strings and W[1]-hard with respect to the parameter $k$, the number of input
strings.

Reduction: intuition and definition. We will reduce $\mathtt{MS}$ to
$\mathtt{MisMatch}_{\mathtt{1Var}}$, such that an instance of $\mathtt{MS}$
with $k$ input strings is mapped to an instance of
$\mathtt{MisMatch}_{\mathtt{1Var}}$ with exactly $k$ occurrences of the
variable $x$ (the single variable occurring in the pattern).

Thus, we consider an instance of $\mathtt{MS}$ which consists in the $k$
binary strings $w_{1},\ldots,w_{k}\in\\{0,1\\}^{*}$ and the integer $\Delta$.
As mentioned above, we can assume that in this instance
$\Delta\leq\sum_{i=1}^{k}|w_{i}|$.

The instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ which we construct
consists of a word $w$ and a pattern $\alpha$, such that $\alpha$ contains
exactly $k$ occurrences of a variable $x$, and both strings are of polynomial
size w.r.t. the size of the $\mathtt{MS}$-instance. Moreover, the bound on the
$d_{\mathtt{ED}}(\alpha,w)$ defined in this instance equals $\Delta$. That is,
if there exists a solution for the $\mathtt{MS}$-instance such that
$\sum_{i=1}^{k}d_{\mathtt{ED}}(w_{i},s)\leq\Delta$, then, and only then, we
should be able to find a solution of the
$\mathtt{MisMatch}_{\mathtt{1Var}}$-instance with
$d_{\mathtt{ED}}(\alpha,w)\leq\Delta$.

The construction of the $\mathtt{MisMatch}_{\mathtt{1Var}}$ instance is
realized in such a way that the word $w$ encodes the $k$ input strings,
conveniently separated by some long strings over $\\{\$,\\#\\}$ (where
$\$,\\#$ are two fresh symbols), while $\alpha$ can be obtained from $w$ by
simply replacing each of the words $w_{i}$ by a single occurrence of the
variable $x$. Intuitively, in this way, for $d_{\mathtt{ED}}(\alpha,w)$ to be
minimal, $x$ should be mapped to the median string of
$\\{w_{1},\ldots,w_{k}\\}$.

We can now formally define the reduction.

For the $k$ binary strings $w_{1},\ldots w_{k}\in\\{0,1\\}^{*}$defining the
instance of $\mathtt{MS}$, let $S=6(\sum_{i=1}^{k}|w_{i}|)$; clearly $S\geq
6\Delta$. Let now $w=w_{1}(\$^{S}\\#^{S})^{S}w_{2}(\$^{S}\\#^{S})^{S}\ldots
w_{k}(\$^{S}\\#^{S})^{S}$ and $\alpha=\left(x(\$^{S}\\#^{S})^{S}\right)^{k}$.

Reduction: correctness. We prove first the correctness of the reduction, that
is, the following claim: the instance of $\mathtt{MS}$ defined by
$w_{1},\ldots,w_{k}$ and $\Delta$ is answered positively if and only if the
instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ defined by $w,\alpha,\Delta$
is answered positively.

Assume first that the instance of $\mathtt{MS}$ defined by
$w_{1},\ldots,w_{k}$ and $\Delta$ is answered positively. Then, it is
immediate to see that $d_{\mathtt{ED}}(\alpha,w)\leq\Delta$. Indeed, let
$w^{\prime}=\left(s(\$^{S}\\#^{S})^{S}\right)^{k}$ be the word obtained from
$\alpha$ by replacing $x$ with the median string $s$ of $w_{1},\ldots,w_{k}$.
Then, clearly, $d_{\mathtt{ED}}(w^{\prime},w)\leq\Delta$.

Now, assume that the instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ defined
by $w,\alpha,\Delta$ is answered positively. This means that there exists some
word $t\in\\{0,1,\$,\\#\\}^{*}$ such that $d_{\mathtt{ED}}(u,w)\leq\Delta$ for
$u=\left(t(\$^{S}\\#^{S})^{S}\right)^{k}$.

Therefore, there exists an optimal (w.r.t. length) sequence of edits $\gamma$
which transforms $u$ into $w$, such that the length of $\gamma$ is at most
$\Delta$. As explained in the preliminaries, we can assume that the edits in
the sequence $\gamma$ are ordered increasingly by the position of $u$ to which
they are applied (i.e., left to right). Our road plan is to show that if such
a sequence of edits $\gamma$ exists, then there exists a sequence $\delta$ of
edits of equal length (so also optimal) transforming $u$ into $w$, such that
the edits rewrite the $i^{th}$ occurrence of the factor $t$ in $w$ into
$w_{i}$, for $i$ from $1$ to $k$, and leave the rest of the string $u$
unchanged.

Let $u_{1}$ be the shortest prefix of $u$ from which we obtain the prefix
$w_{1}(\$^{S}\\#^{S})^{S}$ of $w$ when applying the edits of $\gamma$.
Clearly,
$|w_{1}(\$^{S}\\#^{S})^{S}|-S\leq|u_{1}|\leq|w_{1}(\$^{S}\\#^{S})^{S}|+S$ (as
the overall distance between $u$ and $w$ is upper bounded by $\Delta\leq S$).
Let now $u^{\prime}_{1}$ be the longest prefix of $u_{1}$ from which we obtain
$w_{1}$ when applying the edits of $\gamma$, and let
$u_{1}=u^{\prime}_{1}u^{\prime\prime}_{1}$. Clearly, the edits of $\gamma$
transform $u^{\prime\prime}_{1}$ into $(\$^{S}\\#^{S})^{S}$. We are now
performing a case analysis.

Case 1: $|u^{\prime}_{1}|\leq|t|$.

Case 1.1: $u^{\prime\prime}_{1}=v(\$^{S}\\#^{S})^{S}s$, where
$v,s\in\\{0,1,\\#,\$\\}^{*}$ and $v$ is a suffix of $t$ and $s$ a prefix of
$(t(\$^{S}\\#^{S})^{S})^{k-1}$. As $|u^{\prime\prime}_{1}|=2S^{2}+|v|+|s|$,
then at least $|v|+|s|$ edits are needed to transform $u^{\prime\prime}_{1}$
into $(\$^{S}\\#^{S})^{S}$. We can modify $\gamma$ such that these operations
are deletions of all symbols of $v$ and $s$, and obtain a new sequence of
edits $\gamma^{\prime}$.

Case 1.2: $u^{\prime\prime}_{1}=v(\$^{S}\\#^{S})^{S-1}s$, where
$v\in\\{0,1,\\#,\$\\}^{*}$ is a suffix of $t$ and $s=\$^{S}\\#^{\ell}$ for
some $\ell\geq S-\Delta$. We thus have $t=u^{\prime}_{1}v$ and $|v|\leq
2\Delta$ (because $\left||u^{\prime\prime}_{1}|-2S^{2}\right|\leq\Delta$).
Further, when applying the operations of $\gamma$, after all the edits in
$u_{1}$ were performed, we obtain $w_{2}(\$^{S}\\#^{S})^{S}\ldots
w_{k}(\$^{S}\\#^{S})^{S}$ from $\\#^{S-\ell}(t(\$^{S}\\#^{S})^{S})^{k-1}$
optimally. Hence, from $u^{\prime\prime}_{1}$ we obtain $(\$^{S}\\#^{S})^{S}$
so, after performing the $p$ edits corresponding to positions of $v$
(excluding the potential insertions on positions occurring to the right of the
last symbol of $v$), we must edit them into $\$$ letters, so we must obtain a
string $\$^{g}(\$^{S}\\#^{S})^{S-1}\$^{S}\\#^{\ell}$ for some $0\leq g\leq
2\Delta$. It is immediate that $p+g\geq|v|$ (as when counting the $p$ edit
operations, we count the symbols which were deleted from $v$, while all the
symbols which were substituted in $v$ correspond to distinct positions of
$\$^{g}$). Now, by Lemma 2, since $g\leq 2\Delta$, $S-\ell\leq\Delta$, and
$S\geq 6\Delta$, we get that the minimum number of edits needed to transform
$\\#^{g}(\$^{S}\\#^{S})^{S-1}\\#^{S}\$^{\ell}$ into $(\$^{S}\\#^{S})^{S}$ is
$g+(S-\ell)$. So, to transform $u^{\prime\prime}_{1}$ into
$(\$^{S}\\#^{S})^{S}$ we use $p+g+S-\ell\geq|v|+S-\ell$ edits. We can,
therefore, modify $\gamma$ to obtain a new sequence of edits
$\gamma^{\prime}$, which has at most the same length as $\gamma$, in which we
first apply all the edit operations from $\gamma$ to $u^{\prime}_{1}$, then we
delete all symbols of $v$, then we simply leave $(\$^{S}\\#^{S})^{S}$ alone,
then we insert $\\#^{S-\ell}$ after $(\$^{S}\\#^{S})^{S}$, and we continue by
editing $\\#^{S-\ell}(t(\$^{S}\\#^{S})^{S})^{k-1}$ into
$w_{2}(\$^{S}\\#^{S})^{S}\ldots w_{k}(\$^{S}\\#^{S})^{S}$ exactly as in
$\gamma$. Clearly, we have just replaced $p+g+S-\ell$ operations in $\gamma$
by $|v|+S-\ell$ edits to obtain $\gamma^{\prime}$. As $\gamma$ was of optimal
length, and $p+g+S-\ell\geq|v|+S-\ell$, we have that $\gamma^{\prime}$ must be
of optimal length too.

Case 2: $|u^{\prime}_{1}|>|t|$. Then $u^{\prime}_{1}=t\$^{S-\ell}$, for some
$\ell$ such that $0<S-\ell\leq\Delta$.

Case 2.1:
$u^{\prime\prime}_{1}=\$^{\ell}\\#^{S}(\$^{S}\\#^{S})^{S-2}\$^{S}\\#^{S-g}$
for some $g$ such that $(S-\ell)+g\leq\Delta$. Moreover, when considering the
sequence $\gamma$, we have that $\\#^{g}(t(\$^{S}\\#^{S})^{S})^{k-1}$ is
transformed into $w_{2}(\$^{S}\\#^{S})^{S}\ldots w_{k}(\$^{S}\\#^{S})^{S}$
optimally after the edits in $u_{1}$ are performed. As
$|u^{\prime\prime}_{1}|=2S^{2}-g-(S-\ell)$, then at least $S-\ell+g$ edits are
needed to transform $u^{\prime\prime}_{1}$ into $(\$^{S}\\#^{S})^{S}$. Now we
can modify $\gamma$ as follows. We first note that, in $\gamma$, the suffix
$\$^{S-\ell}$ of $u^{\prime}_{1}$ has to be completely rewritten to obtain
$w_{1}$ (as $w_{1}$ does not contain $\$$ symbols). Therefore, we transform
$t$ into $w_{1}$ by simulating the edits performed in the suffix $\$^{S-\ell}$
by only applying insertions after the last symbol of $t$ (instead of
substitutions in $\$^{S-\ell}$ we do insertions, the insertions are done as
before, and the deletions from $\$^{S-\ell}$ are not needed anymore); the
number of these insertions is at most as big as the number of initial edits
applied to the suffix $\$^{S-\ell}$ of $u^{\prime}_{1}$. Then, the factor
$(\$^{S}\\#^{S})^{S}$ following the first $t$ in $u$ is not edited, as it
corresponds to the identical factor of $w$ which follows $w_{1}$, and then we
insert after the first factor $(\$^{S}\\#^{S})^{S}$ of $u$ a factor $\\#^{g}$,
with $g$ insertions, and then continue editing
$\\#^{g}(t(\$^{S}\\#^{S})^{S})^{k-1}$ to obtain
$w_{2}(\$^{S}\\#^{S})^{S}\ldots w_{k}(\$^{S}\\#^{S})^{S}$ as in $\gamma$. The
resulting sequence $\gamma^{\prime}$ of edits is at least ${S-\ell}$ edits
shorter than $\gamma$, with $S-\ell>0$. As $\gamma$ was optimal, this is a
contradiction, so this case is not possible.

Case 2.2: $u^{\prime\prime}_{1}=\$^{\ell}\\#^{S}(\$^{S}\\#^{S})^{S-1}s$ where
$0<S-\ell\leq\Delta$ and $s\in\\{0,1,\\#,\$\\}^{*}$ is a prefix of
$(t(\$^{S}\\#^{S})^{S})^{k-1}$. In this case, in $\gamma$, we have that the
suffix $u^{\prime}$ of $u$ occurring after $u_{1}$ is transformed into
$w_{2}(\$^{S}\\#^{S})^{S}\ldots w_{k}(\$^{S}\\#^{S})^{S}$ optimally after the
edits in $u_{1}$ are performed. Now, the suffix $s$ is transformed, by $p$
edits into $\\#^{g}$ for some $g\leq 2\Delta$, and we have $p+g\geq|v|$
(similarly to the Case 1.2). By Lemma 2, as in Case 1.2, we get that the
minimum number of edits needed to transform
$\$^{\ell}\\#^{S}(\$^{S}\\#^{S})^{S-1}\\#^{g}$ into $(\$^{S}\\#^{S})^{S}$ is
$g+(S-\ell)$. So, overall, the number of edits needed to transform
$\$^{\ell}\\#^{S}(\$^{S}\\#^{S})^{S-1}s$ into $(\$^{S}\\#^{S})^{S}$ is
$(S-\ell)+g+p\geq(S-\ell)+|s|$. Therefore, we can modify $\gamma$ as follows
to obtain a new optimal sequence of edits $\gamma^{\prime}$. As in Case 2.1 we
simulate the edits in the suffix $\$^{S-\ell}$ of $u^{\prime}_{1}$ by
insertions. Then, the factor $(\$^{S}\\#^{S})^{S}$ is left unchanged. Then we
simply delete the letters of $s$, and we continue by editing $u^{\prime}$ as
in $\gamma$ to obtain $w_{2}(\$^{S}\\#^{S})^{S}\ldots
w_{k}(\$^{S}\\#^{S})^{S}$. Clearly, in $\gamma^{\prime}$ we have at least
$S-\ell$ edits less than in $\gamma$, with $S-\ell>0$. As $\gamma$ was
optimal, his is a contradiction, so this case is also not possible.

This concludes our case analysis.

In all possible cases (1.1 and 1.2), in the newly obtained sequence
$\gamma^{\prime}$ of edits, which has the same optimal length as $\gamma$, we
have that the prefix $t$ of $u$ is transformed into $w_{1}$ by a sequence of
edits $\gamma^{\prime}_{1}$ (which ends with the deletion of the suffix $v$ of
$t$), the first factor $(\$^{S}\\#^{S})^{S}$ of $u$ is then trivially
transformed (by an empty sequence of edits) into the first factor
$(\$^{S}\\#^{S})^{S}$ of $w$, and then $(t(\$^{S}\\#^{S})^{S})^{k-1}$ is
transformed into $w_{2}(\$^{S}\\#^{S})^{S}\ldots w_{k}(\$^{S}\\#^{S})^{S}$ by
an optimal sequence of edits $\gamma^{\prime}_{2}$ (which starts, in Case 1.1,
the deletion of the prefix $s$ of $(t(\$^{S}\\#^{S})^{S})^{k-1}$ or, in Case
1.2, with the insertion of a factor $\\#^{S-\ell}$ before
$(t(\$^{S}\\#^{S})^{S})^{k-1}$).

Now, we can apply the same reasoning, inductively, to the optimal sequence of
edits $\gamma^{\prime}_{2}$ which transforms $(t(\$^{S}\\#^{S})^{S})^{k-1}$
into $w_{2}(\$^{S}\\#^{S})^{S}\ldots w_{k}(\$^{S}\\#^{S})^{S}$, and, we will
ultimately obtain that there exists an optimal sequence of edits $\delta$
which transforms $u$ into $w$ by transforming the $i^{th}$ factor $t$ of $u$
into $w_{i}$, for all $i$ from $1$ to $k$, and leaving the rest of the symbols
of $u$ unchanged. As the length of $\delta$ is at most $\Delta$, this means
that for the string $t$ we have $\sum_{i=1}^{k}d_{\mathtt{ED}}(t,w_{i})\
leq\Delta$, so the instance defined by $w_{1},\ldots,w_{k}$ and $\Delta$ of
$\mathtt{MS}$ can be answered positively. This concludes the proof of our
claim and, as such, the proof of the correctness of our reduction.

Conclusion. The instance of $\mathtt{MisMatch}_{\mathtt{1Var}}$ (i.e.,
$\alpha,w,\Delta$) is of polynomial size w.r.t. the size of the
$\mathtt{MS}$-instance. Therefore, the instance of
$\mathtt{MinMisMatch}_{\mathtt{1RepVar}}$ can be computed in polynomial time,
and our entire reduction is done in polynomial time. Moreover, we have shown
that the instance $(w,\alpha,\Delta)$ of $\mathtt{MisMatch}_{\mathtt{1Var}}$
is answered positively if and only if the original instance of $\mathtt{MS}$
is answered positively. Finally, as the number of occurrences of the variable
$x$ blocks in $\alpha$ is $k$, where $k$ is the number of input strings in the
instance of $\mathtt{MS}$, and $\mathtt{MS}$ is $W[1]$-hard with respect to
this parameter, it follows that $\mathtt{MisMatch}_{\mathtt{1Var}}$ is also
$W[1]$-hard when the number of occurrences of the variable $x$ in $\alpha$ is
considered as parameter. This completes the proof of our theorem. ∎