In order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to y. We use an array z—assumed to be large enough to hold all the characters it will need—to hold the intermediate results. Initially, z is empty, and at termination, we should have z[j] = y[j] for j = 1, 2, ..., n. We maintain current indices i into x and j into z, and the operations are allowed to alter z and these indices. Initially, i = j = 1. We are required to examine every character in x during the transformation, which means that at the end of the sequence of transformation operations, we must have i = m + 1. There are six transformation operations:
• Copy a character from x to z by setting z[j] ← x[i] and then incrementing both i and j. This operation examines x[i].
• Replace a character from x by another character c, by setting z[j] ← c, and then incrementing both i and j. This operation examines x[i].
• Delete a character from x by incrementing i but leaving j alone. This operation examines x[i].
• Insert the character c into z by setting z[j] ← c and then incrementing j, but leaving i alone. This operation examines no characters of x.
• Twiddle (i.e., exchange) the next two characters by copying them from x to z but in the opposite order; we do so by setting z[j] ← x[i + 1] and z[j + 1] ← x[i] and then setting i ← i + 2 and j ← j + 2. This operation examines x[i] and x [i + 1].
• Kill the remainder of x by setting i ← m + 1. This operation examines all characters in x that have not yet been examined. If this operation is performed, it must be the final operation.