Problem
Dada uma string de texto. Você pode realizar as seguintes operações com ele:
1. Substitua um caractere de uma string por outro caractere.
2. Exclua um caractere arbitrário.
3. Insira um caractere arbitrário em uma posição arbitrária na string.
Por exemplo, usando a primeira operação da string "SUCO" você pode obter a string "SUK", usando a segunda operação - a string "OK", usando a terceira operação - a string "STOCK.
O número mínimo de tais operações que podem ser usadas para obter outra de uma string é chamado de custo de edição ou distância de Levenshtein.
Encontre a distância de Levenshtein para as duas strings fornecidas.
Entrada
O programa recebe duas strings como entrada, o comprimento de cada uma delas não excede 1000 caracteres, as strings consistem apenas em letras latinas maiúsculas.
Saída
Necessário para gerar um único número – Distância Levenshtein para strings dadas.
| Entrada |
Saída |
|
ABCDEFGH
ACDEXGIH
|
3 |