Enthält Array1 das Array2?

[Kinimod8]

Hallo,

ich stehe gerade etwas auf dem Schlauch.

Ich möchte überprüfen, ob alle Elemente eines Arrays in genau dieser Reihenfolge in einem anderen, größeren Array vorkommen. Beispiel:

Code:

Großes Array:
[A, B, C, D, E, F]

Kleines Array (1):
[C, D, E] => true

Kleines Array (2):
[C, D, F] => false

Kleines Array (3):
[E, F, G] => false

Wie geht das?

Danke,
Dominik

[Der_Unwissende]

Zitat:

Zitat von Kinimod8

Ich möchte überprüfen, ob alle Elemente eines Arrays in genau dieser Reihenfolge in einem anderen, größeren Array vorkommen.

Hi,
da kannst Du auf verschiedene Ansätze zurück greifen. Als erstes (am wenigsten Elegant, nicht gerade schnell, aber sehr einfach) könntest Du die Arrays in Strings umwandeln und auf die Funktion Pos zurückgreifen. Diese sucht einen Teilstring in einem anderen String.
Besser ist es wenn Du auf einen String-Matching-Algorithmus zurückgreifst. String-Matching ist hier zwar nicht das was Du suchst, aber die Idee lässt sich eigentlich leicht auf andere Datentypen übertragen. Schau einfach mal nach Rabin Karp oder noch besser Knuth Morris Pratt

Gruß Der Unwissende

[Gausi]

Oder Boyer Moore, wobei man sich auch gut auf die (leichter zu implementierende) Bad-Character-Regel beschränken kann.

[DBR]

Delphi-Quellcode:

var
  Grosses: array[0..5] of char = ('A', 'B', 'C', 'D', 'E', 'F');
  Kleines1: array[0..2] of char = ('C', 'D', 'E');
  Kleines2: array[0..2] of char = ('C', 'D', 'F');
  Kleines3: array[0..2] of char = ('E', 'F', 'G');

function KinG(K, G: array of char): boolean;
begin
  result := pos(K, G) > 0;
end;

procedure TForm2.Button3Click(Sender: TObject);
begin
  if KinG(Kleines2, Grosses) then showmessage('Gross enthält Klein1')
  else showmessage('nicht gefunden');
end;


//--------------------- Allgemein --------------------

type
  art = Integer; // für diesen Fall

var
  Grss: array[0..5] of art = (1, 13, 33, 125, 2, 77);
  Kl1: array[0..2] of art = (33, 125, 2);
  Kl2: array[0..2] of art = (33, 125, 77);
  Kl3: array[0..2] of art = (2, 77, 444);

function KinGx(K, G: array of art): boolean;
var
  se, sg, sk: integer;
  A, P: PChar;
begin
  sg := sizeof(G);
  sk := sizeof(K);
  se := sizeof(G[0]);
  P := @G;
  A := P;
  repeat
    result := comparemem(@K, P, sk);
    if result then break;
    inc(P, se);
  until P - A > sg - sk;
end;

procedure TForm2.Button4Click(Sender: TObject);
begin
  if KinGx(Kl2, Grss) then showmessage('Gross enthält Klein1')
  else showmessage('nicht gefunden');
end;

[Kinimod8]

Vielen Dank schon mal an alle, insbesondere an DBR für das Codebeispiel. Muss das jetzt erstmal verdauen :wink: