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":

markieren

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.

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

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.

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.

markieren

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

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?

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

Irgendwie so?

markieren

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.

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.