Muster in einem Array erkennen

[unwissend123098]

Hallo,
ich bin momentan am Experimentieren mit Arrays und ich habe dabei eine interessante Aufgabe gefunden.
Nämlich ich will in einem Array ein wiederkehrendes Muster erkennen und die Methode soll die Länge des Musters angeben.
z.B.: {1,2,3,1,2,3,1,2,3} --> 3
{1,2,1,2,1,2,1,2,1,2} --> 2

Nun habe ich nach etlichen Versuchen keinen richtigen Ansatz zum Lösen dieser Aufgabe gefunden.
Wäre nett, wenn ihr mir dabei helfen könntet.

Danke im Voraus

 

[Kirby.exe]

Was hast du denn bis jetzt auf die Beine gestellt?

 

[mihe7]

Nämlich ich will in einem Array ein wiederkehrendes Muster erkennen und die Methode soll die Länge des Musters angeben.

Dazu mal zwei erste Tipps:
1. Vergiss erstmal Code. Probleme löst man nicht im Editor.
2. Wie lange kann denn ein wiederkehrendes Muster maximal sein?

 

[Ubk0]

Das ist doch typisches, Los macht gefälligst die Aufgabe für mich. Wasch mir den Pelz, aber mach mich nicht nass

 

[unwissend123098]

Was hast du denn bis jetzt auf die Beine gestellt?

Ich hab eine for-Schleife, mit der ich die Anzahl der Elemente zähle. Wenn ein irgend ein Wert a[0]==a ist, dann wollte ich folgendes machen: der Code soll das zweite Element also a[1] mit a[i+1] vergleichen und das selbe Vorgehen wird dann für die darauffolgenden Elemente angewendet. Wenn die Elemente gleich sind, so soll ein Zähler mitzählen, wie viele gleiche Elemente der erste Teil und der zweite Teil besitzen. Jedoch kommt bei mir bei der Implementierung eine unsinnige Zahl immer raus.

 

[unwissend123098]

Was hast du denn bis jetzt auf die Beine gestellt?

Ich hab eine for-Schleife, mit der ich die Anzahl der Elemente zähle. Wenn ein irgend ein Wert a[0]==a ist, dann wollte ich folgendes machen: der Code soll das zweite Element also a[1] mit a[i+1] vergleichen und das selbe Vorgehen wird dann für die darauffolgenden Elemente angewendet. Wenn die Elemente gleich sind, so soll ein Zähler mitzählen, wie viele gleiche Elemente der erste Teil und der zweite Teil besitzen. Jedoch kommt bei mir bei der Implementierung eine unsinnige Zahl immer raus.

 

[unwissend123098]

Dazu mal zwei erste Tipps:
1. Vergiss erstmal Code. Probleme löst man nicht im Editor.
2. Wie lange kann denn ein wiederkehrendes Muster maximal sein?

Das wiederkehrende Muster sollte kleiner als array.length/2 sein

 

[unwissend123098]

Das ist doch typisches, Los macht gefälligst die Aufgabe für mich. Wasch mir den Pelz, aber mach mich nicht nass

Ich habe meinen Ansatz oben beschrieben 🙂

 

[mihe7]

Das wiederkehrende Muster sollte kleiner als array.length/2 sein

Es darf auch genau halb so groß sein. Ein Muster der Länge m passt genau zweimal in ein Array der Länge l, wenn l = 2*m gilt.

Daraus ergeben sich weitere Überlegungen, die aus Deiner Aufgabenbeschreibung nicht eindeutig hervorgehen:

1. Darf das Array, wie in Deinen Beispielen, ausschließlich aus vollständigen Wiederholungen des Musters bestehen? Soll z. B. bei ABCABCX kein Muster erkannt werden oder eine zweimalige Wiederholung des Musters ABC?
2. Muss das Array mit dem Muster beginnen? Wird also in XABCABC kein Muster erkannt, weil X sich nicht wiederholt oder soll eine zweimalige Wiederholung des Musters ABC erkannt werden?

Unabhängig davon: wenn Du ein Array der Länge l = 2*m hast, dann kann das Muster der Länge m an zwei Stellen im Array auftreten. Das erste Mal natürlich am Anfang des Arrays (Index 0).

1. Wo im Array beginnt die Wiederholung?
2. Was gilt für l = 3*m, l = 4*m usw.?