Problem
Eine Textzeichenfolge wurde angegeben. Sie können die folgenden Aktionen ausführen:
1. Ersetzen Sie ein Zeilenzeichen durch ein anderes Zeichen.
2. Löschen Sie ein beliebiges Zeichen.
3. Fügt ein beliebiges Zeichen an einer beliebigen Stelle in der Zeile ein.
Zum Beispiel kann man mit Hilfe der ersten Operation aus der Zeile "SAFT" die Zeile "SUK" erhalten, mit Hilfe der zweiten Operation die Zeile "OK", mit Hilfe der dritten Operation die Zeile "ABFLUSS".
Die minimale Anzahl solcher Operationen, mit denen Sie eine andere Zeile abrufen können, wird als Bearbeitungskosten oder Löwenstein-Entfernung bezeichnet.
Definieren Sie den Löwenstein-Abstand für die beiden Zeilendaten.
Eingabe
Das Programm erhält zwei Zeilen, die jeweils 1000 Zeichen lang sind, und die Zeilen bestehen nur aus lateinischen Großbuchstaben.
Ausgabe
Es ist erforderlich, eine Zahl auszugeben – Löwenstein-Abstand für diese Zeilen.
| Eingabe |
Ausgabe |
|
ABCDEFGH
ACDEXGIH
|
3 |