Aufgabenstellung:

Gegeben sei ein Textfile. Gesucht ist die längste Zeichenkette, die sich in dem Text wiederholt. (Im ersten Satz auf dieser Seite wäre das z.B. "r Software").

Gesucht ist ein möglichst einfacher und effizienter Algorithmus dafür (logo). Textgröße für den Effizienzvergleich: 300 KB.

• Anonym. Sich hinsetzen, überlegen, eine Lösungsweg skizzieren, nach 1-2 Wochen vergleichen mit hier gegebenen Auflösung.
• Angemeldet. Man trägt sich unten in die Teilnehmerliste ein. Schickt eine Lösung via E-mail an den Aufgabensteller. Dieser postet nach 1-2 Wochen die Lösungen und verteilt die virtuellen Preise.
• Kommunikativ. Man hat eine Lösung, ist sich aber nicht sicher, ob sie optimal ist (sie ist es wahrscheinlich nicht) und postet sie unten im Diskussionsbereich. Man kooperiert bis die Erleuchtung kommt.
• Unfair. Man postet als Genie die perfekte Lösung sofort hier, erklärt das Problem für trivial und qualifiziert sich somit als Aufgabensteller für die nächste Runde.

• IljaPreuß (Java)
• ChristianDühl (abstrakt, C oder C++, mal sehen)
• ...... <== hier eintragen

• HelmutLeitner ( MAIL helmut.leitner (AT) chello.at)
• (Lief bis: Montag, 2. April 2001 6:00)

Ich danke den Teilnehmern. Die Auswertung wird bis ca. 11. April dauern.

Die Auflösung: SoftwareDenkSport 1 Auflösung

Sieger:

• IljaPreuß gewinnt mit einer Java-Einsendung den silbernen Zylinder.

Ist hier wirklich nur ein Algorithmus (in einer abstrakten Beschreibung) gesucht oder eine konkrete Implementierung in einer Programmiersprache nach Wahl? Wie wird dann der Geschwindigkeitsvergleich vorgenommen? Darf man im Extremfall Compiler sowie dessen Optionen angeben? Fragen über Fragen :-) -- ChristianDühl

• Beides wäre akzeptabel. Wenn du sagst: das geht so und so (in natürlicher Sprache oder PseudoCode) wäre das ok. Wenn du dein Programm sicherheitshalber ohnehin austesten willst, ist ein Code in einer Sprache deiner Wahl auch ok (für mich muss er auch nicht kommentiert sein). Es soll aber weniger um die MicroOptimierung?, die Compilerauswahl oder um die richtigen Optionen gehen, als um den besten Algorithmus. Wenn ihr komplette Laufzeitwerte vergleichen wollt, dann stelle ich einen Test-Textfile zur Verfügung. -- hl

• Zeilenumbrüche würden mögliche Übereinstimmungen reduzieren, haben aber keinen Einfluß auf den Algorithmus. Die Verantwortung liegt bei dem, der die Inputdaten produziert.
• Ups, ich dachte WhiteSpace würde gleich behandelt, es kommt also auf die Anzahl Leerzeichen, Tabs und Zeilenumbrüche an, der Text soll also "Byte für Byte" untersucht werden und nicht "Wort für Wort"? (Beides ist interessant, man muss ja nur genau wissen, wie es sein soll...) -- ChristianDühl
• So ist es auch gedacht. Es soll Byte für Byte durchsucht werden, egal welche Zeichen sich im Inputfile befinden. --hl

• 'da da'. Beginnt einmal in Position 0, einmal in Position 3.
• Dann ist in 'da__da_da' also 'da_' die längste Zeichenkette, wobei '_' für ein Leerzeichen steht (zwei werden hier zu einem zusammengezogen) und in 'da_da\tda\nda' 'da'?!

• 'da_' bzw. '_da' sind die längsten Zeichenketten, aber es wird nichts zusammengezogen. Leerzeichen, TABs und Zeilenendezeichen werden wie andere Buchstaben auch behandelt. --hl
• Was ich meinte ist folgendes: Wenn jemand einen realen Text (z.B. ein Buch von Thomas Bernhard) auf die längste sich wiederholende Zeichenkette untersuchen will, *dann* muss er sich überlegen, wie er mit WhiteSpace umgehen will und die Inputdaten für den Algorithmus entsprechend aufbereiten. Sonst würden seine Ergebnisse vom Umbruch abhängen. Er könnte das aber leicht tun, z.B. indem er TAB, CR und LF in Leerzeichen verwandelt und danach alle mehrfach-Leerzeichen auf eines reduziert. Aber das ist trivial und hat nichts mit der vorliegende Aufgabe zu tun. --hl
• Entschuldige, ich habe mich unklar ausgedrückt. Hier im Wiki werden zwei Leerzeichen zu einem zusammengezogen, deshalb habe ich sie im Beispiel durch Unterstriche ersetzt. Ich denke, jetzt ist alles klar (hoffe ich mal). Dann kann ich mir ja endlich Gedanken über den eigentlichen Algorithmus machen :-) -- ChristianDühl

Die Zeichenketten dürfen sich überlappen, ich denke nirgendwo steht das Gegenteil. In realen natürlichsprachigen Texten wird so eine Überlappungslösung extrem unwahrscheinlich sein. -- HelmutLeitner