## 5 Edit Distance with Block Deletions
### Block Deletions with Character Moves
The Delete-Insert function runs in time \(O(n^{2}\cdot m)\), Traversing the dynamic programming table takes \(O(n\cdot m)\), therefore, the total running time is \(O(n^{2}\cdot m+|\Sigma|)\), where \(\Sigma\) is the alphabet. ```
functionDelete_Insert_Move(\(S\), \(T\)) { \(A\leftarrow\)Delete_Insert(\(S\), \(T\)) for\(1\leq i\leq|\Sigma|\)do  Insert[\(s_{i}\)] \(\gets 0\)  Delete[\(s_{i}\)] \(\gets 0\) \(i\gets n,j\gets m\) while(\(i>0\)) or (\(j>0\)){ if\(s_{i}=t_{j}\) and \(A[i,j]\leftarrow A[i-1j-1]\) \(i\)-,j- // character insertion of \(\mathrm{t_{j}}\) if\(A[i,j]=A[i,j-1]+1\) Insert[\(\mathrm{t_{j}}\)]++ \(j\)- // character deletion of \(\mathrm{s_{i}}\) elseif\(A[i,j]=A[i-1,j]+1\) and (\(i=n\) or \(A[i+1_{j}]\
eq A[i,j]\)) Delete[\(s_{i}\)]++ \(i\)-  else// block deletion output\(s_{i}\) is deleted within a block deletion \(\}\) for\(1\leq i\leq|\Sigma|\)do{ \(\mathbf{m}\leftarrow\mathrm{Insert}[s_{i}]-\mathrm{Delete}[s_{i}]\) output\(s_{i}\) is moved \(|m|\) times if(\(m>0\)) output\(s_{i}\) is inserted Insert[\(s_{i}\)] - \(m\) times else output\(s_{i}\) is deleted Delete[\(s_{i}\)] + \(m\) times \(\}\)
```  
**Algorithm 4**Edit Distance with Block Deletions, Character Insertion and Character Moves. **Lemma 5:**  
The _algorithm_ presented in Algorithm 4 produces an optimal solution for the edit distance problem with character insertions, block deletions and character moves. **Proof:**  
Assume, by _contradiction_ that the algorithm presented in Algorithm 4 is not optimal, and let \(O=\left\{o_{1,\ldots}o_{k}\right\}\) be an optimal sequence of block deletions, character insertions and character moves (\(<\)c,b,c\(>\)), which converts \(S\) into \(T\). We define \(O^{\prime}=\left\{o^{\prime}_{i,\ldots}o^{\prime}_{i}\right\}\) as follows: if \(o_{i}\) is a character insertion or a block deletion then \(o^{\prime}_{i}=o_{i}\). Otherwise, \(o_{i}\), which is a move of a character \(a\), is replaced by two operations \(o^{\prime}_{i}\) for inserting the character \(a\), and \(o^{\prime}_{i}\) for deleting the character \(a\). Obviously, the operations of \(O^{\prime}\) convert S into T. From the fact above, any sequence of operations which convert \(S\) into \(T\), has the same difference between the number of its insertions and the number of its deletions for every character \(\sigma\in\Sigma\). Formally, \(|I^{O^{\prime}}_{\sigma}-D^{O^{\prime}}_{\sigma}\models|I^{\prec b,c,\succ}_{ \sigma}-D^{\prec b,c,\succ}_{\sigma}|\), where \(I^{O^{\prime}}_{\sigma}\) and \(D^{O^{\prime}}_{\sigma}\) stand for the number of insertions and deletions of \(\sigma\) in \(O^{\prime}\), and \(I^{\prec b,c,\succ}_{\sigma}\) and \(D^{\prec b,c,\succ}_{\sigma}\) denote the number of insertions and deletions of an optimal conversion of \(S\) into \(T\) using only character insertions and block deletions (e.g., an output of Algorithm 3). If for all \(\sigma\in\Sigma\), \(I^{O^{\prime}}_{\sigma}=I^{\prec b,c,\succ}_{\sigma}\) then it applies that \(D^{O^{\prime}}_{\sigma}=D^{\prec b,c,\succ}_{\sigma}\) for all \(\sigma\in\Sigma\). Thus, the algorithm presented in Algorithm 4 gives the same _cost_ of the optimal sequence of operations (converting \(o^{\prime}_{i}\) and \(o^{\prime}_{i}\) back into a move character \(o_{i}\)) and it is optimal, which contradicts our assumption. Therefore, there exist a character \(\sigma\) in \(\Sigma\) such that, \(I^{O^{\prime}}_{\sigma}\
eq I^{\prec b,c,\succ}_{\sigma}\). We show that there exists a character \(\sigma\in\Sigma\) for which \(I^{O^{\prime}}_{\sigma}>I^{\prec b,c,\succ}_{\sigma}\). Otherwise, if for all \(\sigma\in\Sigma\), \(I^{O^{\prime}}_{\sigma}<I^{\prec b,c,\succ}_{\sigma}\), then it applies that \(D^{O^{\prime}}_{\sigma}<D^{\prec b,c,\succ}_{\sigma}\) which contradicts the optimality of \(<\)b,c,\(>\) (Lemma 2). Let \(\sigma\) be _such_ character in \(\Sigma\) for which \(I^{O^{\prime}}_{\sigma}>I^{\prec b,c,\succ}_{\sigma}\), thus \(D^{O^{\prime}}_{\sigma}>D^{\prec b,c,\succ}_{\sigma}\).