Muster in String

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