"Überlappungen" zwischen zwei Strings

[Der schöne Günther]

Mein Covfefe ☕ scheint heute noch nicht zu wirken.

Angenommen ich habe zwei Strings Eins Zwo Hallo Welt und Hallo Welt Guten Tag . Ich möchte die zwei Strings konkatenieren, allerdings "ohne das doppelte mittendrin":

Code:

Eins Zwo Hallo Welt
         Hallo Welt Guten Tag

=>

Eins Zwo Hallo Welt Guten Tag

Gibt es da einen trivialen Lösungsansatz? Schwere Geschütze mit Queues/Stacks oder regulären Ausdrücken wollte ich vermeiden.

[DieDolly]

Ohne das doppelte mitten drin oder allgemein doppelte Wörter?

[Gausi]

Auf Anhieb fällt mir nur das naive Vorgehen ein:

• Suche das erste Zeichen des zweiten Strings im ersten Strings (also im Beispiel "H")
• Überprüfe, ob ab dieser Stelle der Rest des ersten Strings mit dem Anfang des zweiten übereinstimmt
• Falls nicht, suche das nächste Vorkommen des ersten Zeichens im zweiten Strings. (*)
• Falls ja, hat man die Überlappung gefunden und kann die Strings zusammenbauen

(*) diese Stelle kann man ggf. beschleunigen, wenn man ähnliche Tricks anwendet wie bei Knuth-Morris-Pratt. Damit sollte man dann auf eine lineare Worst-Case-Laufzeit kommen, die so erstmal nicht garantiert ist.

[Nersgatt]

Wie wäre es, wenn man die Strings übereinander legt und prüft, ob die überlappenden Buchstaben/Teilstring gleich sind. Wenn ja, hat man die Überschneidung. Wenn nein, verschiebt man den 2. String um eine Stelle und prüft wieder. Da böte sich vielleicht eine rekursive Lösung an.

Code:

Eins Zwo Hallo Welt
Hallo Welt Guten Tag

Eins Zwo Hallo Welt
 Hallo Welt Guten Tag

Eins Zwo Hallo Welt
  Hallo Welt Guten Tag

...

Eins Zwo Hallo Welt
         Hallo Welt Guten Tag

[Moombas]

Vorab eine blöde Frage:

Kann auch folgendes vorkommen:

1. Eins Zwo Hallo Welt
2. Drei Hallo Guten Tag
= keine Überlappung.

Oder:

1. Eins Zwo Hallo Welt Drei
2. Hallo Welt Guten Tag
= Eins Zwo Hallo Welt Guten Tag Drei

Oder ist es immer so, das der Beginn der möglichen Überlappung am Anfang des zweiten Strings definiert ist?

[Der schöne Günther]

Zitat von Moombas:

Oder ist es immer so, dass der Beginn der möglichen Überlappung am Anfang des zweiten Strings definiert ist?

Ganz genau: Ende von 1 = Anfang 2

[Redeemer]

Irgendwie so?

Delphi-Quellcode:

uses Math, StrUtils;

Length1 := Length(Text1); // man sollte LeftStr und RightStr unten ersetzen durch das wesentlich effizientere Copy, wofür man das hier braucht, dafür bin ich aber zu faul
for i := 1 to Min(Length(Text2), Length1) do
if RightStr(Text1, i) = LeftStr(Text2, i) then
Exit(Text1, Copy(Text2, i, High(Integer)));
raise Exception.Create('geht nicht');

Je nach Anforderung muss man die Schleife umdrehen.

[Gausi]

Dann würde ich erstmal die Methode von mir (bzw. die von Nersgatt, das ist ja identisch) nehmen. Kann man natürlich in der Hinsicht optimieren, dass das erste "Übereinanderlegen" so anfängt, dass der untere String rechtsbündig mit dem ersten ist. Vorher ergibt die Suche ja keinen Sinn.

Und wenn eine gute (d.h. lineare) Worst-Case-Laufzeit wichtig ist (Probleme machen bei solchen Ansätzen Strings wie "abababababaC"), dann schau dir Knuth-Morris-Pratt an und modifiere den etwas. Das "Muster" wäre dann der zweite String, und die Modifikation muss so sein, dass das Muster auch als "gefunden" gilt, wenn es nach rechts über den "Text" (also der String in dem gesucht wird) herausragt.

"Bruteforce" wäre natürlich eine Schleife mit AnsiStartStr und AnsiEndStr (oder vergleichbaren Ansätzen, siehe Beitrag von Redeemer). Bei kurzen Strings ist das aber sicherlich vertretbar, d.h. wenn die Programmierkosten hier relevanter sind als eine gute Laufzeit.

[Der schöne Günther]

Zitat von Gausi:

schau dir Knuth-Morris-Pratt an

Vielen Dank an alle, das werde ich tun.

Vorher schaue ich aber ob ich nicht vielleicht doch um den Abgleich drum herum komme 😎

[Gausi]

Zitat von Der schöne Günther:

Vielen Dank an alle, das werde ich tun.

Vielleicht, um das klar zu stellen: KMP ist theoretisch interessant, in der Praxis ist das bei "normalen" Texten eher nicht so wichtig. Diesen Programmieraufwand kann man sich in der Regel sparen, da die problematischen Muster praktisch nie auftreten. Relevant wird das ggf., wenn deine Strings DNA-Sequenzen sind (und somit die Anzahl der verschiedenen Buchstaben sehr gering ist), aber sonst eher nicht.

Habe damals meine Diplomarbeit darüber geschrieben, daher reite ich da manchmal gerne drauf rum.
Ein kleines Animationsprogramm, was z.B. auch die Anzahl der Vergleiche bei verschiedenen Verfahren ausgibt, gibt es auf meiner Webseite.

Aber wenn ich das nochmal überdenke: Der Boyer-Moore-Ansatz könnte hier (wieder etwas modifiziert) auch funktionieren ... (und der ist leichter zu implementieren, imho).