Setup

In order to transform a source string of text $x[1$:$m]$ to a target string $y[1$:$n],$ you can perform various transformation

operations. The goal is$,$ given $x$ and $y,$ to produce a series of transformations that changes $x$ to $y$ An array $z-$assumed to

be large enough to hold all the characters it needs $-$ holds the intermediate results. Initially, $z$ is empty, and at

termination, you should have $z[j]=y[j]$ for $j=1,2,$dots,$n.$ The procedure for solving this problem maintains current

indices i into $x$ and $j$ into $z,$ and the operations are allowed to alter $z$ and these indices. Initially, $i=j=1.$ Every

character in $x$ must be examined during the transformation, which means that at the end of the sequence of

transformation operations, $i=m+1$

You may choose from among siz transformation operations, each of which has a constant cost that depends on the

operation:

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]$ and

has cost $Q_c.$

Replace a character from $x$ by another character $c,$ by setring $z[j]=c,$ and then incrementing both i and $j.$ This

operation examines $x[i]$ and has cost $Q_n.$

Delete a character from $x$ by incrementing i but leaving $j$ alone. This operation examines $x[i]$ and has cost $Q_D-$

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$ and has cost $Q_{\text{I}}.$

Twiddle $($Le$.,$ exchange$)$ the next two characters by copying them from $x$ to $z$ but in the opposite order: 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]$ and has cost $Q_T.$

Kill the remainder of $x$ by setting $i=m+1.$ This operation examines all characters in $x$ that have not yet been

examined. This operation, if performed, must be the final operation. It has cost $Q_K.$

Assume that $1thm3Q_C+Q_R+Q_D+4Q_{\text{I}}+Q_T+Q_{K}x[1$:$m]y[1$:$n]xyxyx[1$:$m]y[1$:$n]$