Se conoce como transformación de cadenas al proceso de llegar de una cadena a otra a través de cambios de caracteres. Los cambios que generalmente se toman en cuenta son: eliminar un caracter, agregar un caracter, o reemplazar un caracter. Otra restricción que se toma en cuenta es que el número de cambios debe ser mínimo (ya que si no lo fuera, obtenemos la respuesta fácilmente con un algoritmo ávido).

Cuando solo se tienen los tres cambios mencionados, al número mínimo de cambios se le conoce como la distancia Levenshtein, y tiene aplicaciones principalmente en correctores de ortografía. Si agregamos como cambio la permutación de dos caracteres, se conoce como la distancia Damerau – Levenshtein. Si sólo consideramos cadenas de una misma longitud, y el único cambio permitido es reemplazar un carácter, se le conoce como la distancia Hamming. En esta sección solo vamos a considerar la primera (Levenshtein).
Para encontrar un algoritmo, primero vamos a considerar estos casos:

• Si tenemos la cadena ‘ab’ y queremos llegar a ‘abc’, sólo necesitamos agregar un caracter.
• Si tenemos la cadena ‘abc’ y queremos llegar a ‘ab’, sólo necesitamos borrar un caracter.
• Si tenemos la cadena ‘abd’ y queremos llegar a ‘abc’, sólo necesitamos cambiar el último caracter.
• Si tenemos la cadena ‘abd’ y queremos llegar a ‘acd’, necesitamos los mismos pasos que si tuviéramos ‘ab’ y queremos llegar a ‘ac’.

Con esto podemos encontrar una relación similar a la de la subsucesión común máxima. Teniendo dos cadenas, cuyo tamaño difiere a lo más en uno:

• Si el último elemento de las cadenas son iguales, entonces podemos obtener la transformación de cadenas sin considerarlos.
• Si estos elementos son distintos, entonces vemos cual de las tres operaciones nos representa un costo mínimo.

Solución: Nos piden encontrar el número mínimo de cambios que se necesitan para pasar de una cadena a otra, además de escribir cuales son estos cambios. Para encontrar el número de cambios, vamos a utilizar las propiedades que acabamos de estudiar y para escribir los cambios vamos a aprovechar la información que queda guardada en la matriz.





En las primeras tres líneas declaramos la variables que vamos a utilizar. Las cadenas s1 y s2 son las que vamos a transformar y el arreglo a nos va a servir para guardar el mínimo de cambios que se necesitan para todas las subcadenas.

La función min (línea 5) nos devuelve en mínimo de dos números. Similar a la función max del problema anterior, sólo hay que cambiar la comparación.

Entre las líneas 7 y 22 tenemos la función para transformar las cadenas. Empezamos inicializando la matriz (líneas 10 a 14). Los contornos los inicializamos con el valor del contador, ya que para pasar de una cadena vacía a una de tamaño j necesitamos j inserciones, y para pasar de una de tamaño i a una vacía necesitamos borrar i caracteres. Entre las líneas 15 y 20 recorremos el arreglo. Si los caracteres son iguales, entonces no los tomamos en cuenta (línea 18), sino, tomamos el menor entre borrar (a[i-1,j]), insertar (a[i,j-1]), o cambiar (a[i-1,j-1]) las cadenas. Al final devolvemos el valor mínimo para transformar la cadena.

En la función trayectoria (líneas 24 a 43) vamos a escribir los pasos que necesitamos para convertir de una cadena a otra. Como parámetros tenemos i y j que indican en que casilla nos encontramos, n que sirve para contar cuantos cambios llevamos y ch que nos indica con cual operación llegamos a esta casilla. Entre las líneas 26 y 31 escribimos cual operación realizamos para llegar en base al valor de ch. Si no hemos llegado a la casilla inicial, revisamos cual es la casilla anterior. Para saber por cual casilla llegamos, sólo hay que ver cual de las casillas adyacentes es menor a la actual y nos movemos a esa. De acuerdo a la dirección del movimiento es el cambio que hacemos en la cadena. Si ninguna de las casillas es menor es porque llegamos por la diagonal (la línea 40 está de sobra, pero ayuda a entender que sucede).

Al final tenemos la parte principal del código (líneas 45 a 53). Mientras no lleguemos al fin de línea, leemos las dos cadenas (líneas 48 y 49), escribimos la cantidad cambios mínimos necesarios para cambiar la primera a la segunda (línea 50), seguido por los cambios (línea 51).

Al igual que con la subsucesión común máxima, si no necesitamos escribir la operaciones que se realizaron, podemos sustituir la matriz por dos arreglos que representan el renglón actual y el anterior.

Entrada:	abcac bcd aaa aabaaaa
Desarrollo:	b c d   0 1 2 3 a 1 1 2 3 b 2 1 2 3 c 3 2 1 2 a 4 3 2 2 c 5 4 3 3     a a b a a a a   0 1 2 3 4 5 6 7 a 1 0 1 2 3 4 5 6 a 2 1 0 1 2 3 4 5 a 3 2 1 1 1 2 3 4
Salida:	3 1 Delete 5 2 Replace 4,d 3 Delete 1 4 1 Insert 1,a 2 Insert 2,a

Lenguaje	Fecha	Tiempos [s]				Memoria [Kb]
		Ejecución	Mejor	Mediana	Peor
Pascal	07-Jun-2006	0.346	0.047	0.287	17.000	348
C	15-Jun-2006	0.186				424

Valladolid: