Levenshtein-Distanz

[mael]

Allgemein ist der Algorithmus wohl kaum zu optimieren.
Die Laufzeit ist ungefähr: (N + M) + (N*M)
(mit N = Length(S) und M = Length(T))

N+M sind die beiden ersten for-Schleifen.
N*M sind die verschachtelten for-Schleifen (die sind das eigentliche Problem).
Dabei ist das was in den for-Schleifen steht jetzt nicht wahnsinnig zeitaufwändig, das Problem ist eher die verschachtelte Schleife an sich. Ob man da im Allgemeinen die Funktion vereinfachen kann bezweifle ich.

Dafür müßte man genaueres über die Eingabedaten wissen. So ist eventuell einer der beiden Strings immer gleich und es läßt sich ein Teil der Rechnung nur einmal machen, anstatt bei jedem Funktionsaufruf, bzw. vielleicht sogar N*M zu N machen (deutlich schneller).
Hängt aber wie gesagt von den Eingabedaten ab.

Poste am besten mal den Quelltext der die Funktion aufruft und typische Eingabebeispiele.

EDIT: Eine andere Möglichkeit ist natürlich den Algorithmus genauer zu studieren und zu hoffen einen besseren Ansatz zu finden (aber Webrecherchen legen nahe, daß das nicht trivial ist).
Konkrete Anwendungsbeispiele sind eventuell einfacher zu optimieren.