Problem
Dada una cadena de texto. Puede realizar las siguientes operaciones con él:
1. Reemplace un carácter de una cadena con otro carácter.
2. Elimina un carácter arbitrario.
3. Inserte un carácter arbitrario en una posición arbitraria en la cadena.
Por ejemplo, usando la primera operación de la cadena "JUGO" puede obtener la cadena "SUK", usando la segunda operación - la cadena "OK", usando la tercera operación - la cadena "STOCK".
El número mínimo de tales operaciones que se pueden usar para obtener otra de una cadena se denomina costo de edición o distancia de Levenshtein.
Encuentre la distancia de Levenshtein para las dos cadenas dadas.
Entrada
El programa recibe dos cadenas como entrada, la longitud de cada una de las cuales no supera los 1000 caracteres, las cadenas consisten solo en letras latinas mayúsculas.
Salida
Requerido para generar un solo número – Distancia de Levenshtein para cadenas dadas.
| Entrada |
Salida |
|
ABCDEFGH
ACDEXGIH
|
3 |