Algorithmus zum Vergleich von Arrays

Hallo,

ich habe 2 Arrays mit beispielsweise folgendem Inhalt

1 = [A,B,C]

und

2 = [A,B,X,C]

Diese sollen als gleich eingestuft werden, da bis auf ein
eingefügtes Element die Reihenfolge stimmt und alle in 1 vorhandenen
Elemente auch in 2 vorhanden sind.

3 = [A,B] soll aber nicht mit 1 übereinstimmen, da dort
ein Element aus 1 fehlt.

auch

4 = [A,C,B] ist falsch, weil dort die Reihenfolge durcheinander ist.

Ich hoffe mal das Prinzip ist klar - wer kennt nen einfachen (soll gut
nachvollziehbar sein, egal ob effizient) Algorithmus, der sowas kann?

Danke und Gruss,

ArrayVergleicher

MFK

Wirf aus dem zweiten Array alle Elemente raus, die im ersten nicht vorkommen, und prüf danach die Arrays auf Gleichheit.

Ponto

bool comapare(std::vector<T> const & a, std::vector<T> const & b) {
  std::size_t ia = 0;
  std::size_t ib = 0;

  while (ia < a.size() and ib < b.size()) {
    if (a[ia] == b[ib]) ++ia;
    ++ib;
  }

  return ia == a.size();
}

groovemaster

Ich würde es wie folgt machen: iteriere durch das Array 1 und schau, ob das aktuelle Element in Array 2 vorkommt. Zusätzlich merkst du dir immer den Index des gefundenen Elements in Array 2. Sollte kein Element in Array 2 vorhanden sein oder der aktuelle Index in Array 2 nicht grösser wie der aktuelle sein, liefert der Vergleich false. Zu beachten sind Sonderfälle, wie zB

1 = [A,B,C]
2 = [A,C,B,C]

Da weisst nur du, ob das als gleich oder ungleich betrachtet werden soll. Dementsprechend musst du die Vergleichslogik anpassen, dass zB das erste oder letzte gefundene Element in Array 2 ausschlaggebend ist (hier im Beispiel Element C). Dann kannst du uU auch den Algorithmus vereinfachen, indem du zB bei der Suche in Array 2 nicht immer vom Anfang ausgehend suchst, sondern ab dem Index der letzten Fundstelle.