Grössten gemeinsamen Teilstring aus 2 Strings?

[lulu]

Huhu

Was nun nur noch getan werden muss, ist die Matrix nach existierenden  Diagonalen auszuwerten.

Interessanter Lösungsansatz.
Das Problem hat mich dann auch nicht ruhen lassen und ich habe mit
folgendem Verfahren eine recht brauchbare Lösung gebastelt.

1. Halbiere den String B (den kürzeren) und prüfe jeden Teilstring auf
Übereinstimmungen in A.

2. Wenn es keine Treffer gibt halbiere erneut usw.

3. Wenn es Treffer gibt werden die Teilstrings gespeichert (jeweils mit ihrer Position in A und B.

4. Benachbarte Strings werden "zusammengeklebt".

5. Dann noch zeichenweise an Anfang und Ende auf weitere Übereinstimmungen des Teilstrings in A mit B prüfen und diese ggf. mit Anfügen.

6. Dann den längsten Treffer auswählen.

Das klappt auch bei längeren Texten in einer akzeptablen Geschwindigkeit.

Zum Vergleich habe ich auch mal die "Holzhammer"-Methode umgesetzt die
über zwei for-Schleifen alle möglichen Teilstrings durchgeht.

Die ist natürlich erwartungsgemäß bei längeren Zeichenketten hoffnungslos überfordert, und braucht dann gerne mal ein paar Sekunden.

Jetzt bin ich noch neugierig wozu man das brauchen könnte.

Was mir einfiel sind "diff"-ähnliche Programme und Lehrer/ Dozenten
die gucken wollen wer bei wem wo wieviel abgeschrieben hat ;-)

Vielleicht liest der Visionmaster ja auch noch mit ?

Viele Grüße

lulu