Größter gemeinsamer Teilstring

Zwei Strings seien gegeben, z.B.

„Pfälzer Saumagen“ und „pfaelzer saumagen“

Der größte gemeinsame Teilstring waere dann „aumagen“

Bei kurzen Strings kann man einfach alles durchprobieren,
für große Strings wächst die Komplexität zumindest bei
meinem Algorithmus wie O(n^4).

Gibt es ein Schlagwort, unter dem ich bei Google nach
so einem Algorithmus suchen könnte?

Gruss, Marco

Englisch: „longest common substring“ (ohne Anführungszeichen reicht). Da fallen ein paar ganz nette Sachen raus, unter Anderem das:
http://www.ics.uci.edu/~eppstein/161/960229.html

Zusammenhängend.

Englisch: „longest common substring“ (ohne Anführungszeichen
reicht). Da fallen ein paar ganz nette Sachen raus, unter
Anderem das:
http://www.ics.uci.edu/~eppstein/161/960229.html

Die definieren „Substring“ mit etwas, das mathematisch
als Teilfolge beschrieben werden kann.

Das ist ein viel weniger komplexes Problem, als
einen „Teilstring“, den ich suche. Ich meine
mit Teilstring einen zusammenhängenden String

  1. Methode: „abababababa“ --> „aaa“ ist ein Teilstring.
  2. Methode: „abababababa“ --> „aaa“ ist kein Teilstring,
    aber „baba“ wäre einer.

Ich suche nach einem Algorithmus fuer den groeßten
*zusammenhaengenden* Teilstring. (bzw. für die korrekte
Bezeichnung dafür, damit ich selber suchen kann)

Gruss, Marco

schnelle Lösung mit Excel-VBA

Zwei Strings seien gegeben, z.B.
„Pfälzer Saumagen“ und „pfaelzer saumagen“
Der größte gemeinsame Teilstring waere dann „aumagen“
Bei kurzen Strings kann man einfach alles durchprobieren,
für große Strings wächst die Komplexität zumindest bei
meinem Algorithmus wie O(n^4).

Hi Marco,
C kann ich nicht, deshalb nützt mir der genannte Link nichts.
Wenn du Excel hast:

Option Base 1
Sub teil()
Application.ScreenUpdating = False
Dim x()
WortA = "PfälzerSaumagen"
WortB = "pfaelzersaumagen"
For n = 1 To Len(WortA)
 For nn = Len(WortA) To n Step -1
 If InStr(WortB, Mid(WortA, n, nn)) Then
 anz = anz + 1
 ReDim Preserve x(anz)
 x(anz) = Mid(WortA, n, nn)
 Exit For
 End If
 Next nn
Next n
For n = 1 To anz
 For nn = n + 1 To anz
 If Len(x(n)) 

Hi Marco,
C kann ich nicht, deshalb nützt mir der genannte Link nichts.
Wenn du Excel hast:

Option Base 1
Sub teil()
Application.ScreenUpdating = False
Dim x()
WortA = „PfälzerSaumagen“
WortB = „pfaelzersaumagen“
For n = 1 To Len(WortA)
For nn = Len(WortA) To n Step -1
If InStr(WortB, Mid(WortA, n, nn)) Then
anz = anz + 1
ReDim Preserve x(anz)
x(anz) = Mid(WortA, n, nn)
Exit For
End If
Next nn
Next n
For n = 1 To anz
For nn = n + 1 To anz
If Len(x(n))

Ich wiederum kann Excel nicht, Basic hab ich
früher mal programmiert :smile:, aber:

Du hast 1. Zwei verschachtelte schleifen --> Komplexität n^2
InStr sucht wiederum nach einem Teilstring der Länge NN,
d.h. nn char-vergleiche und das an m stellen des WortA

D.h. wir haben die Komplexität n^2*m*(n+1)/2, und das
ist, wenn m immer ungefähr so groß ist wie n
wieder eine Komplexität von n^4

Für den (unwahrscheinlichen) Fall, dass sich die
Excel-Programmierer die Mühe gemacht haben
die Fourier-Trafo in InStr zu packen, sind wir
immer noch bei einer Komplexität von n^3*log(n).

Ist mir immer noch zu viel, aber danke für den Tipp!!

Gruss, Marco

Ich wiederum kann Excel nicht, Basic hab ich
früher mal programmiert :smile:, aber:

Hallo Marco,
vba ist Basic, mit egal wann verschütt gegangenen Basicwissen liest du ein vba programm schon flüssig und verstehst die Grundabläufe, im Gegensatz zu C oder so, das ist zwar auch ähnlich, aber schwieriger, weil Systemnaher.
Okay, meine Lösung nutzt dir irgendwie nichts , kannste mir mal bitte sagen was genau dein Anliegen ist?
Weil, eine programmteschnische Lösung um aumagen aus 2 Strings herauszufinden suchst du anscheinend nicht. Die Anzahl der Möglichkeiten ist fest vorgegeben, du rechnest es ja laufend vor. Um die zu bergrenzen, könnte man m.E. nur so vorgehen dass amn nicht nach einzelnen Buchstaben fahndet, sondern gleich nach 2er zeichenfolgen, oder nach dreistelligen Zeichnefolegn, also das Einzelzeichenüberprüfen gleich sein lässt.
Aber wie gesagt, nix genaues weiss man nicht, ich zumindest nicht, was du möchtest.
Gruß
Reinhard

Doch, schon richtig verstanden…

Ich wiederum kann Excel nicht, Basic hab ich
früher mal programmiert :smile:, aber:

Hallo Marco,
vba ist Basic, mit egal wann verschütt gegangenen Basicwissen
liest du ein vba programm schon flüssig und verstehst die
Grundabläufe, im Gegensatz zu C oder so, das ist zwar auch
ähnlich, aber schwieriger, weil Systemnaher.

Kein Problem. Nur die Funktion Is-drin(Wort1,wort2)
oder so ähnlich kannte ich nicht.

Okay, meine Lösung nutzt dir irgendwie nichts , kannste mir
mal bitte sagen was genau dein Anliegen ist?
Weil, eine programmteschnische Lösung um aumagen aus 2 Strings
herauszufinden suchst du anscheinend nicht. Die Anzahl der
Möglichkeiten ist fest vorgegeben, du rechnest es ja laufend
vor.

Doch, genau das suche ich. Es gibt zwar eine
feste Anzahl, aber z.B. mit geschicktem Algorithmus
für diese Feste Wortsuche, die Du verwendet hat,
könnte man schon mal nur noch n^3*log(n) von den
n^4 notwendigen Vergleichen durchfuehren muessen.

Ich suche also etwas, das *alle* Möglichkeiten
testet, aber so effizient programmiert, dass
man eben deutlich *weniger* als n^4 einfache
Operationen braucht.

Um die zu bergrenzen, könnte man m.E. nur so vorgehen

dass amn nicht nach einzelnen Buchstaben fahndet, sondern
gleich nach 2er zeichenfolgen, oder nach dreistelligen
Zeichnefolegn, also das Einzelzeichenüberprüfen gleich sein
lässt.

Diese Technik würde nur einen festen, bzw. von
der Entropie der Zeichenverteilung abhängenden
Faktor, jedoch von der Stringlänge unabhängigen,
bringen.

Gruss, Marco