"Überlappungen" zwischen zwei Strings

[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).