gleiche Zahlenfolgen im Array untersuchen

[Medium]

Noch ein netter Fall: 1 2 3 1 2 3 1

Ist das 2x 1 2 3 und 1x 1
oder 2x 1 2 3 1 wobei die mittlere 1 2-fach verwendet wird?

Die Frage ist also: Darf mehrfach verwendet werden? Kommt auf den Einsatzzweck an, aber das Problem sollte einem bewusst sein.

[Sir Rufo]

Zitat von Medium:

Noch ein netter Fall: 1 2 3 1 2 3 1

Ist das 2x 1 2 3 und 1x 1
oder 2x 1 2 3 1 wobei die mittlere 1 2-fach verwendet wird?

Die Frage ist also: Darf mehrfach verwendet werden? Kommt auf den Einsatzzweck an, aber das Problem sollte einem bewusst sein.

Ja gute Frage

Um das zu finden muss der Start-Index für das lSearchIn geändert werden, dann werden die auch gefunden.

Delphi-Quellcode:

// statt
lSearchIn := Copy( AByteArray, lSearchIndex + ADepth );
// muss dann das genommen werden
lSearchIn := Copy( AByteArray, lSearchIndex + 1 );

[UliBru]

Wie wäre es mit einem etwas anderen Ansatz?
Bei einem Array der Länge n (n sei als gerade Zahl angenommen) könnte es maximal 2 Sequenzen der Länge n/2 geben. Wenn die Sequenzen gleich sind ist auch die Summe gleich.
Um nun die maximale Tiefe festzustellen bildet man ausgehend von n/2 Summanden bis runter zu 2 Summanden die jeweilige Summe. Man muss dann anschliessend nur die Sequenzen vergleichen, die eine gleiche Summe aufweisen.
Bei einer vorgegebenen gewünschten Tiefe x bildet man eben eben gleitend die Summen über x Werte.

Beispiel: Array = 1, 2, 3, 4, 5, 9, 2, 3, 5, 9
Tiefe x = 3
Summenwerte = 6, 9, 12, 18, 16, 14, 10, 17 => alle Werte unterschiedlich, damit x <> 3
Tiefe x = 2
Summenwerte = 3, 5, 7, 9, 14, 11, 5, 8, 14
Es zeigen sich mit 5 und 14 jeweils zwei identische Summen. Die weitere Untersuchung ergibt die Sequenzen 2, 3 und 5, 9.

Es müssen also nur Sequenzen mit gleichen Summen untersucht werden. Natürlich fallen dann Sequenzen mit veränderter Reihenfolge aber gleicher Summe dabei raus.