Entfernung Damerau-Löwenstein
Problem
Einer der häufigsten Tippfehler beim Tippen ist das Umordnen von zwei benachbarten Zeichen, z. B. das Wort «Programm» wird anstelle des Wortes «progarm» eingegeben. Die Löwenstein-Entfernung berücksichtigt solche Tippfehler nicht: Bei der Berechnung der Löwenstein-Entfernung zählt eine Permutation für zwei Bearbeitungen (z. B. das Löschen und Einfügen eines Symbols).
Bei der Berechnung der Entfernung von Damerau-Löwenstein ist neben dem Ersetzen, Einfügen und Löschen eines Symbols auch das Umordnen zweier benachbarter Symbole zulässig. Sie können jedoch keine anderen Zeichen zwischen den neu gestellten Zeichen einfügen.
Definieren Sie den Abstand von Damerau-Löwenstein für die beiden Datenzeilen.
| Eingabe |
Ausgabe |
|
XABCDE
ACBYDF
|
4 |