Alle Wiederholungen in einem String suchen(Vegenére-Chiffre)

[Nikolas]

Ich schreibe grad an einem Programm um die Vegenére-Chiffre bequem entschlüsseln zu können. Jetzt bin ich grad dabei ein Funktion zu schreiben, die mir innerhalb eines langen Strings [die verschlüsselte Nachricht] Buchstabenfolgen findet, die mehrmals vorkommen. Da ich nicht damit rechne, dass jemand so was rumliegen hat (?), wollt ich mal fragen, wie ihr so was angehen würdet. Vor allem bei der Speicherung tu ich mich noch etwas schwer. Ich hatte mal an so was gedacht:

Delphi-Quellcode:

type
repeats = record
Items: string;        // Wiederholte Buchstaben
habitat: TStringlist; // Fundorte
end;

In die Stringlist wollte ich dann nacheinander die Fundstellen eintragen und dann in meiner Klasse ein array of repeats einsetzen. Sieht da jemand Probleme oder eine bessere Idee? :gruebel:

Danke schonmal

Tox

[alcaeus]

Hi toxman,

das mit dem record ist schon mal ein guter Ansatz. Das Suchen ist noch ein bisschen komplizierter.
Du musst Strings rauskopieren und dann Wiederholungen des Strings suchen. Wenn jetzt n die Länge des gesamten Strings ist, dann ist das erste Teilstück n/2 Buchstaben lang. Anschließend musst du die Stringlänge runtergehen lassen und alle Kombinationen suchen. Hier ein Beispiel:
Der String sei

Code:

abcabcdabcde

Die Teilstrings wären dann:

Code:

Länge 6: abcabc, dabcde
Länge 5: abcab, cdabc, bcabc, dabcd, cabcd, abcde, bcdab
Länge 4: abca, bcda, bcde, bcab, cdab, abcd
usw.

Dabei ist aber auch zu berücksichtigen, dass ein String der Länge 4 auch in einer bereits gefundenen Wiederholung der Länge 5 vorkommen kann (also wenn abcab gefunden wurde, darfst du nicht mehr nach abca suchen). Da wirds dann auch richtig kompliziert ;)

Greetz
alcaeus

[Nikolas]

Hat da vielleicht jemand so was (ähnliches) geschrieben? :gruebel: