Matching Patterns with Variables Under Edit Distance

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.


Introduction
A pattern with variables is a string consisting of constant or terminal letters from a finite alphabet Σ (e.g., a, b, c), and variables (e.g., x, y, x 1 , x 2 ) from a potentially infinite set X , with Σ ∩ X = ∅. In other words, a pattern α is an element of P AT Σ = (X ∪ Σ) + . A pattern α 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 α to words over Σ. For example, xxbbbyy can be mapped to aaaabbbbb by the substitution h defined by (x → aa, y → b). In this framework, h(α) denotes the word obtained by substituting every occurrence of a variable x in α by h(x) and leaving all the terminals unchanged. If a pattern α can be mapped to a string of terminals w, we say that α matches w; the problem of deciding whether there exists a substitution which maps a given pattern α to a given word w is called the (exact) matching problem.
Exact Matching Problem: Match Input: A pattern α, with |α| = m, a word w, with |w| = n. Question: Is there a substitution h with h(α) = w?
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 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 α from a class of patterns P (defined by structural restrictions), a word w, and a non-negative integer ∆, whether there exists a substitution h such that the Hamming distance d HAM (h(α), w) between h(α) and w is at most ∆ was investigated. The corresponding minimization problem of computing d HAM (α, w) = min{d HAM (h(α), w) | h is a substitution of the variables of α} was also considered. The main results of [23] were rectangular time algorithms and matching conditional lower bounds for the class of regular patterns 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 ED (·, ·), instead of Hamming Distance: Approximate Matching Decision Problem for MisMatch P Input: A pattern α ∈ P , with |α| = m, a word w, with |w| = n, an integer ∆ ≤ m. Question: Is d ED (α, w) ≤ ∆?
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 MisMatch Reg and MinMisMatch Reg can be solved in O(n∆) time (where, for MinMisMatch, ∆ is the computed result); a matching conditional lower bound follows from the literature [3]. This is particularly interesting because the problem of computing d ED (α, w) for α = w 0 x 1 w 1 . . . x k w k can be seen as the problem of computing the minimal edit distance between any string in which w 1 , . . . , 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, 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 (k1,k2) ), 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, 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].

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 Σ, is denoted P AT = Σ P AT Σ . Given a word or pattern γ, we denote by alph(γ) = B the smallest set (w.r.t. inclusion) B ⊆ Σ and by var(γ) = Y the smallest set Y ⊆ X such that γ ∈ (B ∪ Y ) ⋆ . For any symbol t ∈ Σ ∪ X and α ∈ P AT Σ , |α| t denotes the total number of occurrences of the symbol t in α. For a pattern α = w 0 x 1 w 1 . . . w k x k , we denote by term(α) = w 0 w 1 . . . w k the projection of α on the terminal alphabet Σ.
For words u, w ∈ Σ ⋆ , the edit distance [30,29] between u and w is defined as the minimal number d 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 γ (i.e., u is aligned to w by γ). We can assume without losing generality that the edits in γ are ordered left to right with respect to the position of u where they are applied. Then, for each factorization u = u 1 . . . u k of u, there exists a factorization w = w 1 . . . w k of w such that w i is obtained from u i when applying the edits of γ which correspond to the positions of u i , for i ∈ {1, . . . , 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 γ (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 ′ 1 ) of u from which, when applying the edits of γ we obtain the prefix w 1 of w. Now, for a pattern α and a word w, we can define the edit distance between α and w as d ED (α, w) = min{d ED (h(α), w) | h is a substitution of the variables of α}. It is worth noting that d ED (α, w) ≤ |w| + |term(α)|.
With these definitions, we can consider the two pattern matching problems for families of patterns P ⊆ P AT , as already defined in the introduction. In the first problem MisMatch P , which extends Match P , we allow for a certain edit distance ∆ between the image h(α) of α under a substitution h and the target word w instead of searching for an exact matching. In the second problem, MinMisMatch P , we are interested in finding the substitution h for which the edit distance between h(α) 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 1. MisMatch P AT and MinMisMatch P AT can be solved in O(n 2k2+k1 ) time, where k 1 is the maximum number of occurrences of any variable in the input pattern α and k 2 is the total number of occurrences of variables in α.
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.

Our Results
The first main result of our paper is about the class of regular patterns. A pattern α over the terminal alphabet Σ is regular if where, for i ∈ {1, . . . , k}, w i ∈ Σ * and x i is a variable, and x i = x j for all i = j. The class of regular patterns is denoted by Reg. We can show the following theorem. Proof. Preliminaries and setting. We begin with an observation. For α = w 0 (Π k i=1 x i w i ), we can assume w.l.o.g. that w i ∈ Σ + for all i ≤ k as otherwise we would have neighboring variables that could be replaced by a single variable; thus, k ≤ |term(α)|. To avoid some corner cases, we can assume w.l.o.g. that α and w start with the same terminal symbol (this can be achieved by adding a fresh letter $ in front of both α 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 MisMatch Reg with distance ∆ = 0 is a solution to Match Reg and can be solved in 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 O(n∆) time. In the following, we are going to achieve the same complexity for the general case of MisMatch 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 β = term(α) (instead of the pattern α) and w with the additional property that, for the positions F g = |(Π g i=0 |w i |)| for 0 ≤ g ≤ k−1, we have that the insertions done between positions β[F g ] and β[F g + 1] when editing β to obtain w do not count towards the total edit distance between β and w. For simplicity, we denote the set {F g |0 ≤ g ≤ k − 1} by F , we set F k = +∞, and note that |β| = m − k (so β ∈ Θ(m)).
The description of our algorithm is done in two phases. We first explain how MisMatch 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.
First phase: a classical dynamic programming solution. We define the (|β| + 1) is the edit distance between the prefixes β[1 : j], with 0 ≤ j ≤ |β|, and w[1 : ℓ], with 0 ≤ ℓ ≤ n, with the additional important property that the insertions done between positions β[F g ] and β[F g + 1], for F g ≤ j, are not counted in this distance (they correspond to variables in the pattern α). As soon as this matrix is computed, we can retrieve the edit distance between α and w from the element D 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 MisMatch Reg more efficiently. The idea is to avoid computing all the elements of the matrix D[·][·], 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 α 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[·][·] 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 β (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[·][·] more succinctly, by only computing and keeping track of at most ∆ relevant elements on each diagonal of this matrix, where relevant means that we cannot explicitly rule out the existence of a path leading from For the clarity of exposure, we recall that the diagonal d of the matrix D[·][·] is defined as the array of elements Analysis of the diagonals, definition of M d [δ] and its usage. Now, for is the greatest row where we find the value δ on the diagonal d and, moreover, all the elements appearing on greater rows on that diagonal are strictly greater Note that if a value δ appears on diagonal d and there exists some j ′ such that D[j][j +d] ≥ δ for all j ≥ j ′ , then, due to the only relations which may occur between two consecutive elements of d, In and at least one of the previous inequalities is an equality (i.e., one of the following must hold: and at least one of the previous inequalities is an equality. If ≥ δ and at least one of the previous inequalities is an equality.
Secondly, we consider the diagonal d + 1. Here, for all rows ℓ with Finally, we consider the diagonal d − 1.
Here, for all rows ℓ with j ′ ≤ ℓ ≤ j, . Indeed, otherwise we would have two possibilities. If the path connecting (and then the path moves on diagonal d via an edge corresponding to an insertion) or g < M d−1 [δ − 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 , 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 ′ ] is on diagonal d + 1 (i.e., d ′ = d + 1) then, just like in the previous case, we can simply consider the path connecting 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.
Further, for δ from 1 to ∆ we compute all the values M d [δ], in order for d from −|β|+1 to n. We first compute the largest diagonal d ′ such that M d ′ [δ −k] = |β|, for some k > 0. We will only compute M d [δ], for d from d ′ + 1 to n. For each such diagonal d, we compute g such that Conclusions. This algorithm, which computes all relevant values M d [δ],can be implemented in O((n + m)∆) time, as discussed in the Appendix (where also its pseudocode is given). As explained before, this allows us to solve MisMatch Reg for the input (α, w, ∆). Moreover, if the instance can be answered positively, the value δ for which M n−|β| [δ] = |β| equals d ED (α, w).
⊓ ⊔ The following result now follows.  It is worth noting that the lower bound from Theorem 4 already holds for very restricted regular patterns, i.e., for α = 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 1Var, which is defined as follows: α ∈ 1Var if there exists x ∈ X such that var(α) = {x}. An example of unary pattern is α 1 = abxabxxbaab.
We can show the following theorem. Proof (Sketch). We begin by recalling the following problem: Median String: MS Input: k strings w 1 , . . . , w k ∈ σ * and an integer ∆. Question: Does there exist a string s such that is minimum is called the median string of the strings {w 1 , . . . , w k }.) Without loss of generality, we can assume that ∆ ≤ k i=1 |w i | as, otherwise, the answer is clearly yes (for instance, for s = ε we have that Similarly, we can assume that |s| ≤ ∆ + max{|w i | | i ∈ {1, . . . , k}}.
In [36] it was shown that 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 MS to MisMatch 1Var , such that an instance of MS with k input strings is mapped to an instance of MisMatch 1Var with exactly k occurrences of the variable x (the single variable occurring in the pattern).
Thus, we consider an instance of MS which consists in the k binary strings w 1 , . . . , w k ∈ {0, 1} * and the integer ∆ ≤ k i=1 |w i |. The instance of MisMatch 1Var which we construct consists of a word w and a pattern α, such that α contains exactly k occurrences of a variable x, and both strings are of polynomial size w.r.t. the size of the MS-instance. Moreover, the bound on the d ED (α, w) defined in this instance of MisMatch 1Var equals ∆. That is, if there exists a solution for the MS-instance such that k i=1 d ED (w i , s) ≤ ∆, then, and only then, we should be able to find a solution of the MisMatch 1Var -instance with d ED (α, w) ≤ ∆. The construction of the MisMatch 1Var instance is realized in such a way that the word w encodes the k input strings for MS, conveniently separated by some long strings over two fresh symbols $, #, while α 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 ED (α, w) to be minimal, x should be mapped to the median string of {w 1 , . . . , 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 , . . . w k ∈ {0, 1} * , let S = 6( The constructed instance of MisMatch 1Var (i.e., α, w, ∆) is of polynomial size w.r.t. the size of the MS-instance (i.e., {w 1 , . . . , w k }, ∆). Therefore, it (and our entire reduction) can be computed in polynomial time. Moreover, we can show that the instance Clearly, finding a polynomial time algorithm for MisMatch 1Var , for which the degree of the polynomial does not depend on |α| x , would be ideal. Such an algorithm would be, however, an FPT-algorithm for MisMatch 1Var , parameterized by |α| x , and, by Theorem 5 and common parameterized complexity assumptions, the existence of such an algorithm is unlikely. This makes the straightforward result reported in Theorem 6 relevant, to a certain extent.

Conclusion
Our results regarding the problem 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. were all shown in [23]. We assume |w| = n and |α| = m.

Class
Match Note that the results reported in the first row of the rightmost column of this table are based on Theorem 2 (the upper bound) and Theorem 4 (the lower bound). The rest of the cells of that rightmost column are all consequences of the result of Theorem 5. 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 α, we identify for each variable x the x-blocks: maximal factors of α (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 α 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 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 MisMatch and 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 MisMatch 1Var , as the two problem seem strongly related. To that end, it would be interesting if the upper bound of Theorem 6 can be improved, and brought closer to the one reported for median string in [38]. Secondly, another interesting problem is related to Theorem 4. The lower bound we reported in that theorem holds for regular patterns with a constant number of variables (e.g., two variables

A Computational Model
The computational model we use to describe our results is the standard unitcost 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 ℓ bits, are represented in O(ℓ/ 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 α, with |w| = n and |α| = m, over a terminal-alphabet Σ = {1, 2, . . . , σ}, with |Σ| = σ ≤ n + m. The variables are chosen from the set {x 1 , . . . , 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 Match in [14,23]. For a more detailed general discussion on this computational model see, e.g., [11]. Proof. We only give the proof for MinMisMatch P AT .
Assume the input pattern is α = u 0 x 1 u 1 . . . x k2 u k2 from P AT Σ , where x i is a variable, for i ∈ {1, . . . , k 2 }, and w i ∈ Σ * a terminal word, for i ∈ {0, . . . , k 2 }. Note that there might be the case that x i = x j for some i = j, as there are no restrictions on the structure of the pattern α.
We make several observations.
Let h be a substitution of the variables from α, such that h(x i ) = t i , for i ∈ {1, . . . , k 2 }. Then, h(α) = u 0 t 1 u 1 . . . t k2 u k2 . When computing the edit distance d ED (h(α), w), one obtains a factorization of w = w 0 w ′ 1 w 1 . . . w ′ k2 w k2 such that the optimal sequence of edits transforming h(α) into w transforms u i into w i , for i ∈ {0, . . . , k 2 }, and t ′ i into w i , for i ∈ {1, . . . , k 2 }. Now, let V x = {i ∈ {1, . . . , k 2 } | x i = x} and assume h is a substitution of the variables from α such that d ED (h(α), w) is minimal w.r.t. all possible substitutions of the variables of α. Moreover, let h(x i ) = t i for i ∈ {1, . . . , k 2 }. As before, there exists a factorization of w = w 0 w ′ 1 w 1 . . . w ′ k2 w k2 such that the optimal sequence of edits transforming h(α) into w transforms u i into w i , for i ∈ {0, . . . , k 2 }, and t ′ i into w i , for i ∈ {1, . . . , 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 ′ i | i ∈ V x }. Based on these observations, we can use the following algorithm solving MinMisMatch P AT .
For each factorization f of w = w 0 w ′ 1 w 1 . . . w ′ k2 w k2 and for each variable x: compute the median string s x of {w ′ i | i ∈ V x }; define the substitution h f which maps x to s x for all x; compute the edit distance d ED (h f (α), w). After considering each possible factorization f , return the substitution h f for which d ED (h f (α), w) is minimal.
In the above algorithm, to compute the median string of Firstly, we consider the computation of D[j][ℓ] for j / ∈ F . In this case, we cannot use the aforementioned free insertions, so the element D[j][ℓ] is computed as in the case of computing the usual edit distance between two strings.
The more interesting case is when j ∈ 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][ℓ] when j / ∈ F . However, the case corresponding to the insertion of w[ℓ] to extend an alignment of β[1 : j] and w[1 : ℓ−1] to an alignment of β[1 : j] and w[1 : ℓ] 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 β[1 : j] and w[1 : ℓ] can be obtained as follows. We first obtain an alignment of β[1 : j] to some prefix w[1 : ℓ − k] of w and then use free insertions to append w[ℓ−k+1 : ℓ] to the edited pattern, and, as such, obtain w[1 : ℓ]. But, this also means that we first obtain an alignment of β[1 : j] to some prefix w[1 : ℓ−k] of w and then use free insertions to append w[ℓ−k +1 : ℓ−1] to the edited pattern, and, as such, obtain an alignment of the pattern to w[1 : ℓ−1], and then insert (again, without counting this towards the edit distance) w[ℓ] to obtain w[ℓ−k+1 : ℓ]. Thus, in this case, an alignment between β[1 : j] and w[1 : ℓ] which uses free insertions corresponding to the position j ∈ F is obtained from an alignment between β[1 : j] and w[1 : ℓ−1] followed by an additional free insertion. We obtain, as such, the following recurrence relation for D[j][ℓ], when j ∈ F : is inserted after position j, for free.
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 ℓ from 0 to n) in O(nm) time.
Input: w, α Output: minimal edit distance between α and w in O(nm) 1 compute β and the set F ;   Proof. We use the algorithm of Theorem 2 for ∆ = 2 i , for increasing values of i starting with 1 and repeating until the algorithm returns a positive answer and computes Φ = d ED (α, w). The algorithm is clearly correct. Moreover, the value of i which was considered last is such that 2 i−1 < Φ ≤ 2 i . So i = ⌈log 2 Φ⌉, and the total complexity of our algorithm is O(n ⊓ ⊔

Lower bound for MisMatch Reg
The results of Theorems 2 and 3 are complemented by the following lower bound, known from the literature [3]. Firstly, we recall the OV problem.
Orthogonal Vectors (for short, OV) Input: Two sets U, V consisting each of n vectors from {0, 1} d , where d ∈ ω(log n). Question: Do vectors u ∈ U, v ∈ V exist, such that u and v are orthogonal, i.e., for all It is clear that, for input sets U and V as in the above definition, one can solve OV trivially in O(n 2 d) time. The following conditional lower bound is known. 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]. Before starting the proof of Theorem 5 we need the following technical lemma.
Lemma 2. Let $ and # be two letters and let S, g, and ℓ be integers. If g ≥ 0, 2g ≤ S, S 2 ≤ ℓ − g, and ℓ ≤ S then: Proof. We only show the first claim, as the second follows identically (as it is symmetrical).
Firstly, it is clear that g +(S −ℓ) edits suffice to transform Now, we will show that we cannot transform $ g ($ S # S ) S−1 $ S # ℓ into ($ S # S ) S with fewer than S − ℓ + g edits.
Note that from S 2 ≤ ℓ − g we get ℓ ≥ g + (S − ℓ). So, the suffix # S of ($ S # S ) S must be obtained by a series of edits from a suffix of the suffix $ S # ℓ of $ g ($ S # S ) S−1 $ S # ℓ . This means that at least S − ℓ 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 # ℓ . 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 − ℓ) edits to transform $ g ($ S # S ) S−1 $ S # ℓ into ($ S # S ) S , so it cannot be done with fewer edits. The conclusion follows.

⊓ ⊔
We can now proceed with the proof of Theorem 5.
Proof. Preliminaries. We begin by recalling the following problem: Median String: MS Input: k strings w 1 , . . . , w k ∈ Σ * and an integer ∆. Question: Does there exist a string s such that is minimum is called the median string of the strings {w 1 , . . . , w k }.) Without loss of generality, we can assume that ∆ ≤ k i=1 |w i | as, otherwise, the answer is clearly yes (for instance, for s = ε we have that Similarly, we can assume that |s| ≤ ∆ + max{|w i | | i ∈ {1, . . . , k}}. In [36] it was shown that 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 MS to MisMatch 1Var , such that an instance of MS with k input strings is mapped to an instance of MisMatch 1Var with exactly k occurrences of the variable x (the single variable occurring in the pattern).
Thus, we consider an instance of MS which consists in the k binary strings w 1 , . . . , w k ∈ {0, 1} * and the integer ∆. As mentioned above, we can assume that in this instance ∆ ≤ k i=1 |w i |. The instance of MisMatch 1Var which we construct consists of a word w and a pattern α, such that α contains exactly k occurrences of a variable x, and both strings are of polynomial size w.r.t. the size of the MS-instance. Moreover, the bound on the d ED (α, w) defined in this instance equals ∆. That is, if there exists a solution for the MS-instance such that k i=1 d ED (w i , s) ≤ ∆, then, and only then, we should be able to find a solution of the MisMatch 1Var -instance with d ED (α, w) ≤ ∆.
The construction of the MisMatch 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 α 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 ED (α, w) to be minimal, x should be mapped to the median string of {w 1 , . . . , w k }.
We can now formally define the reduction. For the k binary strings w 1 , . . . w k ∈ {0, 1} * defining the instance of MS, let S = 6( Reduction: correctness. We prove first the correctness of the reduction, that is, the following claim: the instance of MS defined by w 1 , . . . , w k and ∆ is answered positively if and only if the instance of MisMatch 1Var defined by w, α, ∆ is answered positively. Assume first that the instance of MS defined by w 1 , . . . , w k and ∆ is answered positively. Then, it is immediate to see that d ED (α, w) ≤ ∆. Indeed, let w ′ = s($ S # S ) S k be the word obtained from α by replacing x with the median string s of w 1 , . . . , w k . Then, clearly, d ED (w ′ , w) ≤ ∆. Now, assume that the instance of MisMatch 1Var defined by w, α, ∆ is answered positively. This means that there exists some word t ∈ {0, 1, $, #} * such that d ED (u, w) ≤ ∆ for u = t($ S # S ) S k .
Therefore, there exists an optimal (w.r.t. length) sequence of edits γ which transforms u into w, such that the length of γ is at most ∆. As explained in the preliminaries, we can assume that the edits in the sequence γ 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 γ exists, then there exists a sequence δ 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 γ. Clearly, |w 1 ($ S # S ) S |−S ≤ |u 1 | ≤ |w 1 ($ S # S ) S |+ S (as the overall distance between u and w is upper bounded by ∆ ≤ S). Let now u ′ 1 be the longest prefix of u 1 from which we obtain w 1 when applying the edits of γ, and let u 1 = u ′ 1 u ′′ 1 . Clearly, the edits of γ transform u ′′ 1 into ($ S # S ) S . We are now performing a case analysis. Case 1: |u ′ 1 | ≤ |t|. Case 1.1: u ′′ 1 = v($ S # S ) S s, where v, s ∈ {0, 1, #, $} * and v is a suffix of t and s a prefix of (t($ S # S ) S ) k−1 . As |u ′′ 1 | = 2S 2 + |v| + |s|, then at least |v| + |s| edits are needed to transform u ′′ 1 into ($ S # S ) S . We can modify γ such that these operations are deletions of all symbols of v and s, and obtain a new sequence of edits γ ′ . Case 1.2: u ′′ 1 = v($ S # S ) S−1 s, where v ∈ {0, 1, #, $} * is a suffix of t and s = $ S # ℓ for some ℓ ≥ S − ∆. We thus have t = u ′ 1 v and |v| ≤ 2∆ (because |u ′′ 1 | − 2S 2 ≤ ∆). Further, when applying the operations of γ, after all the edits in u 1 were performed, we obtain w 2 ($ S # S ) S . . . w k ($ S # S ) S from # S−ℓ (t($ S # S ) S ) k−1 optimally. Hence, from u ′′ 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 # ℓ for some 0 ≤ g ≤ 2∆. It is immediate that p + g ≥ |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 ≤ 2∆, S − ℓ ≤ ∆, and S ≥ 6∆, we get that the minimum number of edits needed to transform # g ($ S # S ) S−1 # S $ ℓ into ($ S # S ) S is g + (S − ℓ). So, to transform u ′′ 1 into ($ S # S ) S we use p + g + S − ℓ ≥ |v| + S − ℓ edits. We formed into w 1 by a sequence of edits γ ′ 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 . . . w k ($ S # S ) S by an optimal sequence of edits γ ′ 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−ℓ before (t($ S # S ) S ) k−1 ). Now, we can apply the same reasoning, inductively, to the optimal sequence of edits γ ′ 2 which transforms (t($ S # S ) S ) k−1 into w 2 ($ S # S ) S . . . w k ($ S # S ) S , and, we will ultimately obtain that there exists an optimal sequence of edits δ 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 δ is at most ∆, this means that for the string t we have k i=1 d ED (t, w i ) leq∆, so the instance defined by w 1 , . . . , w k and ∆ of 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 MisMatch 1Var (i.e., α, w, ∆) is of polynomial size w.r.t. the size of the MS-instance. Therefore, the instance of MinMisMatch 1RepVar can be computed in polynomial time, and our entire reduction is done in polynomial time. Moreover, we have shown that the instance (w, α, ∆) of MisMatch 1Var is answered positively if and only if the original instance of MS is answered positively. Finally, as the number of occurrences of the variable x blocks in α is k, where k is the number of input strings in the instance of MS, and MS is W [1]-hard with respect to this parameter, it follows that MisMatch 1Var is also W [1]-hard when the number of occurrences of the variable x in α is considered as parameter. This completes the proof of our theorem.