gleiche Zahlenfolgen im Array untersuchen

[Sendrix]

Hallo Bjoerk,

Danke für den Source. Probleme hab ich mit dem Verständnis, dem Nachvollziehen der Funktion FindSubList. Wie kommt man auf sowas ? Mir ist das bisher nicht gelungen gedanklich nachzubauen. Funktionieren tut's sehr gut nur kapier ich es nicht ganz und frage mich wie man auf so einen Algorithmus kommt.
Kannst Du mir dazu eventuell ein paar Zeilen zum besseren Verständnis schreiben ?

Danke,

Viele Grüße,
Sendrix

Noch was anderes:
Immer wenn ich mich im Forum anmelde und auf einen Beitrag antworten möchte lande ich wieder bei der Anmeldung obwohl ich bereits in der OnlineListe zu sehn bin. Irgendwann wenn ich dann zum x ten mal auf Anmelden geklickt hab klappts dann.

[BUG]

Zitat:

Zitat von negaH (Beitrag 1129132)

NP-vollständigen Algorithmen umgesetzt

Eine der seltenen Gelegenheiten Hagen mal zu korrigieren :wink:
Entscheidungsprobleme können in NPC sein.
Für Algorithmen gibt es nur Laufzeiten.

Zitat:

Zitat von Sendrix (Beitrag 1130335)

Noch was anderes:
Immer wenn ich mich im Forum anmelde und auf einen Beitrag antworten möchte lande ich wieder bei der Anmeldung obwohl ich bereits in der OnlineListe zu sehn bin. Irgendwann wenn ich dann zum x ten mal auf Anmelden geklickt hab klappts dann.

Cookies an? Evtl. mal das "angemeldet bleiben" Kästchen aktivieren.

[Bjoerk]

Zitat:

Zitat von Sendrix (Beitrag 1130335)

Hallo Bjoerk,

Danke für den Source. Probleme hab ich mit dem Verständnis, dem Nachvollziehen der Funktion FindSubList. Wie kommt man auf sowas ? Mir ist das bisher nicht gelungen gedanklich nachzubauen. Funktionieren tut's sehr gut nur kapier ich es nicht ganz und frage mich wie man auf so einen Algorithmus kommt.
Kannst Du mir dazu eventuell ein paar Zeilen zum besseren Verständnis schreiben ?

Danke,

Viele Grüße,
Sendrix

Ist nichts anders als PosEx, jedoch bei 0 statt 1 beginnend und für Stringlisten statt für Strings .

Versuche vielleicht deshalb erst die normale PosEx zu verstehen (ist etwas anschaulicher und fast das gleiche).

Delphi-Quellcode:

function PosEx (const Substr, S: string; const Index: integer): integer;
var
  I, J, A, B: integer;
begin
  Result:= 0;
  A:= Length(S);
  B:= Length(Substr);
  I:= Index;
  if I < 1 then Exit;
  if B = 0 then Exit;
  if B > A then Exit;
  while (Result = 0) and (I <= A-B+1) do
  begin
    J:= 1;
    if S[I] = Substr[J] then
    begin
      while (J < B) and (S[I+J] = Substr[J+1]) do Inc(J);
      if J = B then Result:= I;
    end;
    Inc(I);
  end;
end;

Fange bei I an. J ist zunächst 1. Wenn das I. Zeichen von S mit dem (immer) 1. Zeichen von Substr übereinstimmt, dann hast du eine Chance, Substr zu finden [if S[I] = Substr[J] then]. Probiere dann, ob weitere Zeichen von S und Substr auch übereistimmen. Ansonsten mache an der I+1. Position von S weiter und probiere das selbe, solange, bis Substr nicht mehr in S reinpasst oder du ein Ergebnis ungleich Null hast [while (Result = 0) and (I <= A-B+1) do]. Wenn das Ergebnis Null ist, konnte der Sustr nicht gefunden werden. (Man setzt in der Regel Result vorab auf Null, wenn mögliche Ergebnisse bei 1 beginnen, auf -1, wenn mögliche Ergebnisse ab 0 möglich sind.)

Wenn also das I. Zeichen von S mit dem 1. Zeichen von Substr übereinstimmt, dann mache folgendes (J ist immer noch 1): Ist das I+J. Zeichen von S mit dem J+1. Zeichen von Substr identisch, dann erhöhe J um eins. J ist dann also J+1. Mache das ganze solange, wie dieser Vergleich gelingt oder das letzte Zeichen von Substr erreicht ist [while (J < B) and (S[I+J] = Substr[J+1]) do Inc(J)]. Ist diese Bedingung B-1 mal erfüllt, das erste Zeichen haben wir bereits vorher abgefragt, dann ist J gleich B (Länge von Substr). In diesem Falle hast du Substr gefunden. Gib als Ergebnis die Stelle zurück, wo die erfolgreiche Suche begonnen hat [if J = B then Result:= I]. Result ist jetzt nicht mehr Null und die function wird beendet.

[Sendrix]

Hallo Bjoerk,

jetzt hab ich es kapiert. Der hinweis auf PosEx war wirklich hilfreich. Das hab ich mir genau angesehn und konnte es dann mit Deiner beschreibung gut auf Deinen Sourcecode übertragen und verstehn. So langsam komme ich weiter. Danke für Deine / Eure Tips und Hilfe.

Sendrix