String-Diff für Java

Hallo,

Ich würde einen Algorythmus (wenns geht in Java ausprogrammiert) suchen, welcher mir aus 2 Strings einen diff-String erstellt - mit dem ich dann den ersten patchen kann damit ich den zweiten draus bekomm.

Im Grunde also eigentlich was rsync macht, nur für Strings

Ich habe schon eine Klasse gefunden welche exakt das macht was ich suche:

String s1 = "Hello I am a very small string";
        String s2 = "Hella I am a very small ding";


        String difference = new StringDiff().exec(s1, s2);
        String patchedString = StringDiff.apply(s1, difference);
        --> s2.equals(patchedString) :-)

Leider ist die Implementierung sehr, sehr schlecht (ich glaub theta(n^2)) und der Speicherverbrauch enorm.
Wenn der String 1000 zeichen lang ist, wird ein 1000x1000-int[] angelegt (4MB) :-/

Kennt ihr zufällig Implementierungen welche auch bei großen Datenmengen noch zuverlässig Arbeiten?

Danke im Vorraus, lg Clemens