## 5 Edit Distance with Block Deletions
### Block Deletions with or without Character Insertions  
Given two strings \(S\) and \(T\), where \(T\) is a sub-sequence of \(S\) (_i.e._, it is possible to delete characters from \(S\) to obtain \(T\)), we are interested in the smallest integer \(k\) such that \(T\) is partitioned into \(k\) blocks (substrings), and the blocks of \(T\) are substrings of \(S\), and occur in \(S\) in the same order as in \(T\). If \(k=1\) this is the traditional pattern matching problem, which returns whether the pattern \(T\) occurs in \(S\) or not. Consider for example \(S=bcxyabczdlmefij\) and \(T=abcdef\). In this case there are three blocks in \(S\) occurring in the same order as in \(T\). Define \(S^{\prime}=SSS\), where \(S\) is a new character not occurring in \(S\) nor \(T\). Finding the minimum number of blocks of \(S\) so that the blocks of \(T\) occur in \(S\) in the same order as in \(T\) is equivalent to finding the minimum number of block deletions minus 1, performed on \(S^{\prime}\) so that \(S^{\prime}\) is identical to \(T\). The difference of 1 in the cost is since every block deletion of \(S\) can be matched with the corresponding preceding block of \(S\), except for the first block of \(S\). The block deletion problem can be solved in polynomial time using dynamic programming. Allowing character insertions in addition to block deletions requires small changes in the algorithm. Let \(o\) be a block deletion which deletes a substring that ends with a character \(c\), \(o\mid_{c}\) denotes the substring \(o\) after truncating its last character. If \(o\) does not end with \(c\), \(o\mid_{c}\) is equal to \(o\). The following lemma refers to the case of block deletions only, and implies a recurrence formula which is the basis of the dynamic programming algorithm presented in Algorithm 2. **Lemma 1:** Let \(S=s_{1}\cdots s_{n}\) and \(T=t_{1}\cdots t_{m}\) be two strings of lengths \(n\) and \(m\), respectively, and let \(O=\left\{o_{1,\ldots}o_{k}\right\}\) be an optimal sequence of block deletions which converts \(S\) into \(T\). If \(o_{k}\) ends with the character \(s_{n}\), then \(O^{\prime}=\left\{o_{1,\ldots}o_{k}\mid_{s_{n}}\right\}\) is an optimal sequence of block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(T\). Otherwise, \(O\) is an optimal sequence of block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(t_{1}\cdots t_{m-1}\). **Proof:**  
(1) Assume that \(o_{k}\) ends with the character \(s_{n}\):  
* If \(o_{k}\) deletes \(s_{n}\) alone (being \(o_{k}\) a character deletion) then \(O^{\prime}=\left\{o_{1,\ldots}o_{k-1}\right\}\) is an optimal sequence of block deletions which converts \(S=s_{1}\cdots s_{n-1}\) into \(T\). Otherwise, if \(O^{\prime}\) is not optimal, let \(\left\{\delta_{i_{m}}\delta_{i_{k}}\right\}\) be an optimal sequence of block deletions converting \(s_{1}\cdots s_{n-1}\) intowith cost less than \(O^{\prime}\). Define \(\tilde{O}=\left\{\tilde{o}_{{}_{1\cdots\tilde{o}_{t}}},o_{k}\right\}\). The sequence \(\tilde{O}\) of block deletions is a sequence of block deletions which converts \(S\) into \(T\) with cost less than \(O\), which contradicts the optimality of \(O\). * If \(o_{k}\) deletes \(s_{n}\), and \(s_{n}\) is deleted within a block deletion of length greater than 1, the block deletion charge is applied to some previous character, and \(s_{n}\) is deleted for free. Thus, shortening \(o_{k}\) to not include \(s_{n}\) is done within the same cost, and \(O^{\prime}=\left\{o_{{}_{1\cdots\tilde{o}_{k}}}\,o_{k}\right\}\) is an optimal sequence of block deletions which converts \(s_{1}\cdots s_{n-1}\) into \(T\). Otherwise, if \(O^{\prime}\) is not optimal, let \(\left\{\tilde{o}_{{}_{1\cdots\tilde{o}_{t}}}\right\}\) be an optimal sequence of block deletions converting \(s_{1}\cdots s_{n-1}\) into \(T\) with cost less than \(O^{\prime}\) (meaning \(\ell<k\) ). Let \(i\) be the minimum index \(1\leq i\leq\ell\) so that the block deletion \(\tilde{o}_{i}\) deletes some character which is also deleted by \(o^{\prime}_{k}\).