Distância de Edição
A distância de edição entre duas strings é o número mínimo de operações necessárias para transformar uma string em outra. As operações permitidas são:
- Adicionar um carácter à string.
- Remover um carácter da string.
- Substituir um carácter na string.
Por exemplo, a distância de edição entre e é 2, porque primeiro pode-se substituir por e depois adicionar .
Dadas duas strings, a sua tarefa é calcular a distância de edição entre elas.
Input
A primeira linha da entrada contém a primeira string, enquanto a segunda linha contém a segunda. Está garantido que o número de caracteres das strings não ultrapassa 1000.
Output
O programa deve imprimir um único inteiro: a distância de edição entre as duas strings fornecidas.
Exemplos
Entrada | Saída |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB