Längste sich wiederholende Sequenz im String finden

[x000x]

Moin moin,

ich stehe gerade auf dem Schlauch... Ich brauche einen Lösungsvorschlag/Algorithmus um in einem langem String/Text (> 10000 Zeichen)
die längste sich wiederholende Sequenz zu finden.
Also, wenn z.B. der String wie folgt aussieht:

Code:

B01AF4516495401AF4564571

dann ist hier die längste sich wiederholende Zeichenkette:

Code:

01AF45

Evtl. noch als Hinweis: in dem Text stehen nur HEX-Zeichen ([0..9],A,B,C,D,E,F)

Ich habe im Moment leider keine Ideen, wie ich dies lösen bzw. wie man das performant lösen könnte.
Eventuell habt ihr Ideen?

[Satty67]

ich hab' noch keine Idee, aber spontan ist mir eingefallen, das man es von hinten aufzäumen könnte. Da dort die Grenzen noch offensichtlicher sind, ist ein Code leichter gefunden

Man holt sich also den größt möglichen Ausschnitt, der doppelt vorkommen kann (length div 2) und vergleicht den mit dem Rest.

Gleich, dann gefunden

Ungleich, dann Ausschnitt ein Wert (Byte/Zeichen) kürzer. Ab jetzt muss man die aktuelle Ausschnitt-Länge im Offset verschieben, bis Restzeichen weniger als Ausschnitt-Länge sind.

Jetzt kommt sicher gleich jemand, der Algorithmus XYZ präsentiert, der die Aufgabe elegant und schnell löst ;)

[mkinzler]

0.)Startkenner auf 1. Buchtaben
1.)die Positionen aller mit Buchstaben am Startkenner identische Buchstaben im Text suchen
2.)deren Folgebucnstaben mit denen des Startkenners vergleichen, bis nicht mehr identisch
3.)Folge mit bisher längster Folge vergleichen, wenn Länger, aktuelle als längste merken
4.)Wenn Buchstabe nicht mehr gefunden wird Startkenner um Startkenner + Länge gefundene Sequenz inkrementieren
5.) wenn das Ende noch nicht erreicht bzw. Restlänge kleiner längstes Wort ist -> 1.)

[jfheins]

Quick 'n Dirty:

Nimm 2 Indizes: Start und Länge. (beide am Anfang gleich 1)
Außerdem 2 Variablen MaxLänge und MaxStart;

1) Nimm bei der Position Start Länge Zeichen und suche im Rest des Strings danach. (Wenn gefunden speichere Start und Länge)

2a) Wenn Länge = Stringlänge/2 ==> Länge = MaxLänge; Start = Start + 1; Wenn Start+2*Länge > Stringlänge beenden, sonst weiter bei 1)
2b) sonst Länge = Länge + 1; Weiter bei 1)

Könnte klappen :gruebel:

[Satty67]

Könnte noch fehlerhaft sein, die Beispielzeichenkette aus dem Startpost findet der Code aber:

Delphi-Quellcode:

function GetBiggestTwin(aText : String) : String;
var
  window, offset, TextLen : Integer;
  TestText, RestText : String;
begin
  TextLen := Length(aText);
  Result := '';

  for window := (TextLen div 2) downto 1 do begin

    offset := 1;
    while window <= (TextLen - ((offset-1)+window)) do begin

      TestText := Copy(aText, offset, window);
      RestText := Copy(aText, offset+window, Textlen);

      if Pos(TestText, RestText) > 0 then begin
        Result := TestText;
        Exit;
      end;
      inc(offset);
    end;
  end;
end;