## 4 Edit Distance with Block Moves, Block Deletions, Character Insertions
### Non Recursive Block Moves and Deletions
However, the blocks \(A_{i-1}^{2}\) and \(A_{j+1}^{1}\) must move to their final location, which adds a cost of two to the number of operations by splitting theoriginal blocks \(A_{i-1}\) and \(A_{j+1}\)(if \(A_{i-1}\) and \(A_{j+1}\) were not moved in previous operation, this additional cost is left for future cost). We show that the inner blocks \(\{A_{i},\cdots,A_{j}\}\) of \(b\), which were not moved within the first \(3(k-1)\) operations, are moved to their final location with no additional cost. Blocks which were never moved, are located in different blocks since there was a block, which was moved in between them or from between them, in one of the previous operations. In the case a block was moved out from between two blocks, this operation was \"charged\" by three non recursive moves, instead of one (since this is a non recursive move to start with), so these blocks are now moved for free. In case a block was moved in between two blocks that were never moved, without loss of generality, the block to the left of the border can be moved for free using the cost that was charged for this operation in its destination. By assigning the charge for each border to the block to its left, we are left with at most a single block for which the block to its right was moved out (otherwise it is a block to the left of a border of a block which was moved in, and is moved for free) or this block is one of the ends of \(b\). In any of these cases the block can be moved for free using the charge that was applied to a block move source. Using the induction hypothesis, we have \"charged\" this move by three non recursive moves instead of one. Therefore, we can move the two adjacent blocks without charging it again. The worst case uses three more operations in order to convert \(T^{\prime}\) to \(T\). Adding it to the number of operations executed in order to convert \(S\) into \(T^{\prime}\)  we get \(3+3(k-1)=3k\) operations. **Theorem 3:** The bound of Theorem 2 is tight. **Proof:** The following example builds two strings \(S\) and \(T\)  of \(n\) substrings of the form \(S_{n}\) and \(T_{n}\) respectively, where \(S_{n}\) and \(T_{n}\) are defined recursively, such that the non-recursive edit distance of \(S\) and \(T\)  is three times the recursive edit distance of these strings. For simplicity, because each character will not occur more than once in both \(S\) and \(T\), for this example we use the notation \(move(s)\) for moving a substring \(s\) of \(S\), without stating its source and destination locations. First consider the alphabet \(\sum=\{L_{0},L_{1},M_{0},R_{0}\}\). Let \(S_{1}=L_{1}L_{0}M_{0}R_{0}\) and \(T_{1}=L_{1}M_{0}L_{0}R_{0}\). Suppose \(S_{1}\) is a substring of \(S\), not aligned with the substring \(T_{1}\) of \(T\), and therefore must be moved. The recursive edit distance is 2 (\(move(M_{0})\) and \(move(L_{1}M_{0}L_{0}R_{0})\)) and the non-recursive edit distance is 4 (\(move(L_{1})\), \(move(M_{0})\), \(move(L_{0})\) and \(move(R_{0})\)). In general, we use the following definition:  
\[ \begin{array}{rclrclrcl}W_{0}&=&L_{0}M_{0}R_{0}&\text{and}&W_{i}&=&L_{i}M_{i }R_{i}W_{i-1}\\ S_{0}&=&L_{0}&\text{and}&S_{i}&=&L_{i}W_{i-1}\\ V_{0}&=&M_{0}L_{0}R_{0}&\text{and}&V_{i}&=&M_{i}L_{i}R_{i}V_{i-1}\\ T_{0}&=&L_{0}&\text{and}&T_{i}&=&L_{i}V_{i-1}\end{array} \]  
We get that  
\[ \begin{array}{rclrclrcl}S_{n}&=&L_{n}W_{n-1}&=&L_{n}L_{n-1}M_{n-1}R_{n-1} \cdots L_{0}M_{0}R_{0}\\ T_{n}&=&L_{n}V_{n-1}&=&L_{n}M_{n-1}L_{n-1}R_{n-1}\cdots M_{0}L_{0}R_{0}\end{array} \]  
Using the above definition of \(S_{n}\) and \(T_{n}\), we continue taking out a mid part of a block (thus, breaking a continuous string into three parts), and putting it into another block, and again breaking a continuous string. This way we add three blocks by each move operation. If \(S_{n}\) should be recursively moved (given the assumption that \(S_{n}\) and \(T_{n}\) are not aligned in the entire strings \(S\) and \(T\)), these previous move operations turn into recursive ones, and cannot be performed by the non-recursive sequence of moves.