datei durchsuchen nach wiederholenden bytefolgen

[griever]

also ich will in einer datei nach sich wiederholenden bytefolgen beliebiger größe(außer vlt 1-2 bytes) suchen
habt ihr nen plan wie ich das am sinnvollsten mache?

das einfachste wäre ja die datei erstmal zu teilen und nachzusehen ob sich das wiederholt
danach zieht man das letze byte der ersten hälfte ab und sucht den neuen entstandenen teil danach im rest
dann verschiebt man das ganze um ein byte und sucht wieder im rest usw
wenn was gefunden wurde wird es von der weiteren suche ausgeschlossen.

bevor ich das so mach wollte ich fragen ob jmd ne bessere lösung kennt
es sollte also die längsten sich wiederholenden bytefolgen zuerst gefunden werden
die bytefolgen müssen sich nacheinadner wiederholen

also nach dem schema
abcdefghabcdefgh

und nicht nach schema
abcdefghiabcdefghz

gefundenes nicht nochmal benutzt werden
rechenaufwand so gering wie möglich gehalten werden

[alzaimar]

Such mal nach 'Greatest Common Subsequence'. Trifft es zwar nicht ganz, dürfte aber in die richtige Richtung gehen.

[marabu]

Moin,

die Aufgabe hat dir jemand gestellt?

Legitim ist sicher auch der Hinweis auf die Ähnlichkeit mit der Beispielaufgabe aus der ersten Runde dem 21. BWInf - die beiden Aufgabenstellungen gehören der gleichen Problemklasse an.

Grüße vom marabu

[griever]

also hab mal ein bisschen nach 'Greatest Common Subsequence' gegoogelt finde da aber nur mathematikwörterbücher,informatikaufgaben und noch ein paar sachen die damit eigentlich garnix zu tun haben
der tip mit der informatikolympiade hat mich auch nich wirklich weiter gebracht, mann kann da ja nur die fragen lesen(was haben summen der beiden größten werte mit meinen wiederholungen zu tun)?
trotzdem erstmal danke das überhaupt jmd das gelesen hat

das ganze ist aus eigenen antrieb entstanden

[marabu]

Hallo,

ich habe mir die Beispielaufgabe Ribo-Natter auf Seite 4 genauer angesehen und komme zu dem Schluss, dass deine Aufgabenstellung eine Vereinfachung des Beispiels darstellt. Bei dir entfallen die Invertierung der Zeichen und die Umkehr der Zeichenkette.

Keine Ahnung wo du nachgesehen hast, aber das muss an einer anderen Stelle gewesen sein.

Freundliche Grüße

[mkinzler]

Mich erinnert die Aufgabe an eine LISP-Aufgabe, allerdings war da die Länge der Zeichenketten beschränkt

[BrightAngel]

Hey!
Also rein technisch gesehen ist es ja so: wenn du davon ausgehen kannst, dass es immer mit dem ersten Byte losgeht - gut. Aber wenn nicht - was dann?
Was mein ich damit?
also deine methodde funktioniert bei:
abcdeabcdeabcdeabc...
aber was ist mit
eabcderabcdesabcde ?
wenn er immer eins abzieht, dann findet er ja trotzdem nichts, auch wenn ja im grunde eine abcde-kette zu finden wäre.
Aber auch die obige Kette ließe sich bestimmt noch weiter teilen. Deine methode teilt ja dann nur abcdeabcde-abcdeabcde aber vlt. nicht abcde-abcde-abcde-abcde oder?

Ich weis ich nehm hier grad alles auseinander (-verzeihung!) und habe ja in sowas auch nicht wirklich erfahrung. aber vlt. wäre eine iterative lösung einfacher?

Gruß und Wünsche zum Erfolg!
Brighty

[griever]

Zitat von BrightAngel:

Hey!
Also rein technisch gesehen ist es ja so: wenn du davon ausgehen kannst, dass es immer mit dem ersten Byte losgeht - gut. Aber wenn nicht - was dann?
Was mein ich damit?
also deine methodde funktioniert bei:
abcdeabcdeabcdeabc...
aber was ist mit
eabcderabcdesabcde ?

ist vlt nicht ganz rübergekommen aber das meinte ich mit ein byte verschieben und weitersuchen
wie gesagt ich will nur die größten wiederholungen finen
das aa ode cc das ein oder andere mal vorkommt will ich mal nicht berücksichtigen
(dann müsste ich ja wirklich jedes einzelne byte überprüfen und das ganze sollte schon noch im rahmen gehalten werden)

wenn ich die ribo natter richtig verstanden habe, ist die idee im prinzip die gleiche die ich hatte,
also halbieren und überprüfen dann verkleinen und alle möglichen positionen ausprobieren und im rest danach suchen dann wieder verkleinern usw.

ich bin mir sicher, das das auch geht aber bei eine datei, die zb 10MB groß ist, dürfte das wohl eine weile dauern bis das prog fertig ist mit suchen,
deswegen wollte ich nach ner besseren (effektiveren) lösung fragen.

[BrightAngel]

achso. ja gut, dann löst du es ja schon iterativ. Ich habe nichts gesagt. Ich trete mal wieder offene Türen ein...^^