Muster in String

[Monday]

Hallo,

ich möchte ein Muster in zwei Strings herausfinden.

Ich habe zwei Strings: Beispiel:
A) a123bcdef
B) ghij123kl

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

usw.

Ich weiß nicht, welches Muster es ist oder wie lange, ich weiß nur das in beiden Strings eine Zeichenfolge/Muster (im Beispiel 123) gleich sind. Und möchte herausfinden, welcher es ist.

Gibt es hierfür eine Funktion? Und falls nicht, welcher Weg ist hierfür am geschicktesten für die Lösung?

Was ich sicher weiß, das die Strings immer 100 Zeichen lang sind.

Ich habe erst gedacht, das ich String A mittels Bruteforce aufteile und dann die einzelnen Elemente mit String B vergleiche. Aber hab festgestellt dass das er ein laaangwieriger Weg ist,...
gibt es einen einfacheren Weg?

LG
Monday

[BUG]

In 100 Zeichen langen Strings gibt es potenziell Unmengen an gemeinsamen Teilzeichenketten. Man denke nur an die einzelnen Zeichen.

Suchst du nur die längste gemeinsame Teilzeichenkette?


EDIT: Ok, ich hatte das Problem falsch verstanden
Als erstes könntest du alle Zeichen entfernen, die nicht in beiden Zeichenketten vorkommen.

[Sir Rufo]

Das Zauberwort heißt hier Permutation.

Dazu brauchst einen Algorithmus, der die alle möglichen Muster aus einem String generiert.

Die Muster kann man ja als Zeichen und ein Array darstellen.

Delphi-Quellcode:

TFollower = record
  Character: Char;
  Offset: Integer;
end;

TPattern = record
  First: Char;
  Followers: array of TFollower;
end;

Das Muster '123' aus 'a123bcdef' würde dann z.B. so aussehen:

Code:

{ 
  "First": "1",
  "Follower": [
    { 
      "Character": "2",
      "Offset": 1 
    },
    { 
      "Character": "3",
      "Offset": 2 
    } 
  ] 
}

Das Muster '123' aus 'a1b2cd3ef' würde dann z.B. so aussehen:

Code:

{ 
  "First": "1",
  "Follower": [
    { 
      "Character": "2",
      "Offset": 2 
    },
    { 
      "Character": "3",
      "Offset": 5 
    } 
  ] 
}

Die Suche in den anderen Strings ist dann relativ einfach. Man sucht nach der Position von First . Wenn es da eine gibt, dann schaut man, ob es am Offset des ersten Followers diesen Character gibt, usw.

Findet man alle Follower , dann hat man einen Match.

Auch wenn es nur 100 Zeichen in einem String sind, die Anzahl der Permutationen in der Breite von 1 bis 100 wird da schon gewaltig werden. Die sollte man versuchen sinnvoll einzuschränken.

z.B. Die gesuchten Muster sind zwischen 3 und 5 Zeichen lang. Das würde die Verarbeitungsgeschwindigkeit dramatisch verkürzen (man findet aber auch nur diese Muster).

[Dejan Vu]

Ich glaube, das sind keine Permutationen, sondern Kombinationen (oder Variationen, irgendwie so)
Auf jeden Fall gibt es in einer Zeichenkette der Länge n so ziemlich n!/(n-k)! Muster der Länge k.
Das ist ne Menge, aber machbar.

Oder irre ich?

[Sir Rufo]

Zitat von Dejan Vu:

Ich glaube, das sind keine Permutationen, sondern Kombinationen (oder Variationen, irgendwie so)
Auf jeden Fall gibt es in einer Zeichenkette der Länge n so ziemlich n!/(n-k)! Muster der Länge k.
Das ist ne Menge, aber machbar.

Oder irre ich?

Da kannst durchaus Recht haben ... (ich sollte da mal eine Autokorrektur eintragen )

[Luckie]

Würde da nicht auch ein pos bzw. posex reichen?

[jobo]

Zitat von Monday:

ich möchte ein Muster in zwei Strings herausfinden.

Ich habe zwei Strings: Beispiel:
A) a123bcdef
B) ghij123kl

Möglich wäre auch
A) a1b2cd3ef
B) ghi1j2kl3

usw.

Ich weiß nicht, welches Muster es ist oder wie lange, ich weiß nur das in beiden Strings eine Zeichenfolge/Muster (im Beispiel 123) gleich sind.

"usw." finde ich nicht sehr erschöpfend in der Beschreibung. Klar scheint ja die feste Zeichenfolge zu sein, was aber gilt als Muster? Geht das genauer?

[Sir Rufo]

Mit meinem Mustererkennungblick sehe ich *123*

• a123bcdef
• ghij123kl

und *1?2??3*

• a1b2cd3ef
• ghi1j2kl3

oder als weiteres Beispiel *AA??A*

• lkrAAkfAj
• kAA34Appp

[jobo]

Klar, mit einer gewissen Empathie oder musterhaften analytischen Fähigkeiten kann man da schon Muster erkennen.
Aber ist das mustergültig?

Vor allem das "usw." schwächt die Aussagekraft der beiden Beispiele.
Auch eine steigende oder fallende Anzahl von Zeichen ergibt bspw. bei Wiederholung ein Muster, da sind der Fantasie wenig Grenzen gesetzt.

Außerdem finde ich meine Frage pädagogisch wertvoll.

Oder ist das Muster gültig?

• a1b2cd3ef
• ghi1j2kl3

Vielleicht sogar, ohne dass die darin enthaltenen nummerischen Zeichen für sich bereits ein Muster ergeben?

[BUG]

Wenn jemand genau 100 Zeichen lange Strings hat und solche Beispiele gibt, hoffe ich doch sehr auf einen einigermaßen durchdachten Anwendungsfall beim TE.
Es würde vielleicht helfen, wenn er sich wieder melden würde