Aufgabe 372: Levenshtein-Distanz

Die Levenshtein-Distanz (auch Edit-Distanz, Editierdistanz oder Editierabstand) bezeichnet in der Informationstheorie ein Maß für den Unterschied zwischen zwei Zeichenketten bezüglich der minimalen Anzahl der Operationen Einfügen, Löschen und Ersetzen, um die eine Zeichenkette in die andere zu überführen. Benannt ist die Distanz nach dem russischen Wissenschaftler Wladimir Lewenstein, der sie 1965 einführte.

Um beispielsweise von 'Tier' zu 'Tor' zu kommen ist eine Ersetzung und eine Löschung notwendig, die Levenshtein-Distanz beträgt also 2:

Tier
Toer (Ersetze i durch o)
Tor (Lösche e)

In der Praxis wird die Levenshtein-Distanz zur Bestimmung der Ähnlichkeit von Zeichenketten beispielsweise zur Rechtschreibprüfung oder bei der Duplikaterkennung angewandt.
Quelle: Wikipedia

Seit Januar 2001 gibt es den Euro. Die Länder, die zuerst den Euro eingeführt haben, waren Belgien, Deutschland, Finnland, Frankreich, Griechenland, Irland, Italien, Luxemburg, Niederlande, Österreich, Portugal und Spanien.

Gesucht sind sowohl die beiden Euro-Länder, deren Levenshtein-Distanz möglichst klein ist (zwei Lösungen!), als auch die beiden Hauptstädte mit möglichst kleiner Distanz (drei Lösungen)!