Überprüfung: Wiederholung von Zeichenketten im String

[Scorpion]

Hallo,

ich muß einen String auf eine Wiederholung von Zeichenketten überprüfen. Das heisst in diesem Fall, eine Zeichenkette, darf nicht direkt nacheinander folgen, also

BB wäre falsch BAB ok
BABAB falsch und BABCAB ok
BANANE falsch, da ANAN vorkommt

habt ihr eine Idee, wie man das machen könnte ?

Vielen Dank

[Nikolas]

Leg für jede Zeichenfolge eine Liste an, in der du die Positionen des Substrings notierst. Dann schaust du in der Liste, ob zwei benachbarte Positionen weiter als die Länge des Substrings auseinanderliegen:
Bsp:
BlaBla

erster String: 'B' Positionen: 1,4; Länge des Strings: 1. 1+1<4 -> Treffer
n.ter string: 'Bla' Positionen: 1,4, Länge:3 . 1+3=4 -> Kein Treffer

[HERMES]

Überleg dir eine passende Grammatik dazu und dann überprüf (möglicherweise mit CYK) ob dein Wort mit der Grammatik dargestellt werden kann.

[Scorpion]

@Toxman: Aber das müsste ich ja mit allen Substring aller möglichen Längen machen, ist das nicht zu Speicheraufwändig?

@HERMES: Hättest du eine Idee, wie das aussehen könnte?

[HERMES]

Da musst du dir mal die Chomsky Hirachie ( / Formale Sprachen ) anschauen, und dann kannst du in Abhängigkeit der hirachischen Stufe deiner Grammatik eine passende Möglichkeit finden deinen Input zu überprüfen.

[Hawkeye219]

Hallo Nico,

hier ist mein Versuch:

Delphi-Quellcode:

function CheckString (const s: string): Boolean;
var
  idx, len: Integer;
begin
  Result := False;
  for idx := 1 to Length(s) - 1 do
    for len := 1 to (Length(s) + 1 - idx) div 2 do
      if CompareMem(@s[idx], @s[idx + len], len) then
        Exit;
  Result := True;
end;

Gruß Hawkeye

[Scorpion]

@Hawkeye219: Ja, vielen Dank, der Code funktioniert super...

An alle anderen trotzdem auch vielen Dank für die Tips :)