Hintergrund
Incident ist eine ziemlich ungewöhnliche Programmiersprache, da die Liste der Token nicht vorbestimmt ist, sondern aus der Eingabe abgeleitet wird. Daher kann das Tokenisieren eines Incident-Programms ziemlich schwierig sein, insbesondere wenn Sie dies effizient tun möchten. Bei dieser Aufgabe geht es darum, das selbst zu tun.
Die Aufgabe
Ihr Programm erhält als Eingabe einen String. Hier ist der Algorithmus, den Incident verwendet, um es zu kennzeichnen:
- Identifizieren Sie alle Zeichenfolgen, die als Teilzeichenfolge der Eingabe vorkommen, auf genau drei Arten (dh, die Zeichenfolge kommt in der Eingabe genau dreimal vor).
- Verwerfen Sie alle diese Zeichenfolgen, die eine Teilzeichenfolge einer anderen solchen Zeichenfolge sind (z. B. für die Eingabe wäre
ababab
die einzige verbleibende Zeichenfolgeab
, nichta
oderb
, weila
undb
beide Teilzeichenfolgen vonab
). - Verwerfen Sie alle Zeichenfolgen, die sich in der Eingabe überschneiden. (
aaaa
Enthält z. B. genau drei Kopien vonaa
, aber diese Kopien überlappen sich beim zweiten und dritten Zeichen, sodass sie verworfen werden. In ähnlicher Weiseabababa
gibt es drei Kopien vonab
und drei Kopien vonba
, aber das zweite bis sechste Zeichen befinden sich jeweils beim Überlappung von aab
und aba
, also beideab
undba
würden verworfen). - Alle Zeichenfolgen, die an diesem Punkt verbleiben, sind die vom Programm verwendeten Token. Unterteilen Sie die ursprüngliche Eingabe in eine Sequenz dieser Token (aufgrund des Verwerfens im vorherigen Schritt gibt es nur eine Möglichkeit, dies zu tun). Alle Zeichen in der Eingabe, die nicht Teil eines Tokens sind, werden als Kommentare behandelt und verworfen.
Ihr Programm muss eine Zeichenfolge als Eingabe nehmen und die entsprechende Tokenisierung der Zeichenfolge (eine Liste von Token, die jeweils als Zeichenfolgen ausgedrückt werden) als Ausgabe zurückgeben. Darüber hinaus muss dies zumindest mäßig effizient erfolgen; Insbesondere muss das Programm in quadratischer Zeit ("O (n²)") oder besser ausgeführt werden. (Übrigens ist es mit ziemlicher Sicherheit möglich, schneller als quadratisch zu arbeiten, aber dies ist kein schneller Algorithmus. Verwenden Sie also den genauesten Algorithmus, der innerhalb der Komplexitätsgrenzen liegt.)
Klarstellungen
- Obwohl Incident-Programme theoretisch jedes der 256 Oktette enthalten können, ist es für den Zweck dieser Herausforderung für Ihr Programm akzeptabel, nur Eingaben zu verarbeiten, die aus druckbarem ASCII (einschließlich Leerzeichen) sowie Zeilenumbrüchen und Tabulatoren bestehen. (Alle bekannten Incident-Programme beschränken sich auf diese Untermenge.) Beachten Sie, dass Leerzeichen / Zeilenumbrüche / Tabulatoren nichts Besonderes sind und in der Mitte von Token angezeigt werden können. Incident behandelt alle 256 Oktette als undurchsichtig.
- Die Definition von "quadratischer Zeit" ist "wenn die Größe der Eingabe verdoppelt wird, läuft das Programm um nicht mehr als eine Konstante plus einen Faktor von 4 langsamer", dh wenn t ( x ) die maximale Zeit ist, die Ihr Programm benötigt Verarbeiten Sie eine Eingabe der Größe x , dann muss es eine Konstante k geben, so dass t (2 x ) <4 t ( x ) + k für alle x gilt . Beachten Sie, dass das Vergleichen von Zeichenfolgen eine Zeit benötigt, die proportional zur Länge der Zeichenfolgen ist.
- Ihr Programm sollte theoretisch in der Lage sein, Eingabeprogramme beliebiger Länge zu verarbeiten, wenn es in einer (möglicherweise hypothetischen) Variante Ihrer Sprache mit unbegrenztem Speicher und unbegrenzten Ganzzahlen ausgeführt wird (es ist in Ordnung, wenn das Programm dieses Ziel in der Praxis aufgrund von nicht erreicht die ganzen Zahlen oder das Gedächtnis der Sprache sind tatsächlich endlich groß). Sie können davon ausgehen (um die Komplexität zu berechnen), dass ganze Zahlen, die nicht länger als die Länge der Eingabe sind, in konstanter Zeit verglichen werden können (denken Sie jedoch daran, wenn Sie größere Werte verwenden, z. B. aufgrund der Konvertierung der Eingabe in a Bei einer einzelnen Ganzzahl dauert der Vergleich proportional zur Anzahl der Stellen länger.
- Sie können jeden Algorithmus verwenden, der innerhalb der Komplexitätsgrenzen liegt, auch wenn er nicht denselben Schritten wie der oben angegebene Algorithmus folgt, sofern er dieselben Ergebnisse liefert.
- In diesem Rätsel geht es darum, die Eingabe zu tokenisieren und nicht wirklich die Ausgabe zu formatieren. Wenn die natürlichste Art, eine Liste in Ihrer Sprache auszugeben, ein mehrdeutiges Format beinhaltet (z. B. durch Zeilenumbrüche getrennt, wenn die Zeichenfolgen wörtliche Zeilenumbrüche enthalten oder ohne Trennzeichen zwischen den Zeichenfolgen), machen Sie sich keine Sorgen darüber, dass die Ausgabe mehrdeutig wird ( solange die Liste tatsächlich aufgebaut ist). Möglicherweise möchten Sie eine zweite Version Ihrer Einreichung erstellen, die eine eindeutige Ausgabe liefert, um das Testen zu erleichtern. Die Originalversion ist jedoch die Version, die für die Bewertung zählt.
Testfall
Für die folgende Eingabezeichenfolge:
aaabcbcbcdefdfefedghijghighjkllkklmmmmonono-nonppqpq-pqprsrsrstststuvuvu
Ihr Programm sollte die folgende Ausgabeliste erzeugen:
a a a bc bc bc d e f d f e f e d gh gh gh k l l k k l pq pq pq u u u
Siegbedingung
Dies ist Code-Golf , daher gewinnt das kürzeste gültige (dh korrekte Eingabe- / Ausgabeverhalten und ausreichend schnell zum Ausführen) Programm, gemessen in Bytes.
Antworten:
C (gcc), 324 Bytes
Die Funktion verwendet
f
eine nullterminierte Zeichenfolge und druckt die Token nach stdout. Alle Zeilenumbrüche können aus dem nachfolgenden Code entfernt werden.Diese ältere 376-Byte-Version ist etwas einfacher zu lesen. Die unten stehende Erklärung gilt dafür.
k(0)
generiert diet
Mustertabellep
für den Knuth-Morris-Pratt-Algorithmus.K(c)
Verarbeiten des nächsten Zeichensc
der Suchzeichenfolge und Aktualisierenm
, wobei die Länge des größten Präfixes,p
das gefunden werden kann, auf das zuletzt verarbeitete Zeichen endet.In der ersten
for
Schleife wird für jeden Indexa
in der Zeichenfolge gezählt, wie oft jeder mögliche Wert vonm
auftritt, wenn in der gesamten Zeichenfolge nach der Teilzeichenfolge gesucht wird, die bei beginnta
. Dann suchen wir die größte,l
so dass die Längensubstringl
aba
genau dreimal vorkam. Wenn es kurz genug ist, um vollständig in einer Zeichenfolge enthalten zu sein, die für eine frühere Zeichenfolge gefunden wurdea
, ignorieren wir es. Wenn es sich überschneidet, löschen wir die vorherige Zeichenfolge ausz
dem Array und zeichnen auf, welche Token aufbewahrt werden. Andernfalls wird seine Länge in gespeichertz
.Anschließend verwenden wir KMP erneut, um die Zeichenfolge nach den in aufgezeichneten Token zu durchsuchen
z
. Wenn einer von ihnen an einem Ort mit einem Eintrag von 0 gefunden wirdz
, wissen wir, dass dieser Token wegen Überlappung gelöscht wurde. Wenn das Token nicht gelöscht wurde, wird es gedruckt.quelle
O(n^2)
oder schneller. Und warum ist da!!
bei!!z[x-m]
?*Z
ist die Länge des nächsten Tokens, die 0 werden muss, wenn eines der anderen Vorkommen des Tokens den Wert 0 an seinem Index im Array hat oder andernfalls den gleichen Wert!!z[x-m]
!!
ist.!!x
sollte es immer noch seinx
, oder ruft es einen Trick auf, von dem ich nichts weiß?!!x
machtx
einen Booleschen, der seine "Wahrhaftigkeit" darstellt. Also!!1 == true
und!!0 == false
. Ich kenne C nicht genau, aber so läuft es normalerweiseJavaScript,
878867842825775752717712704673664650641 BytesVielen Dank an @Kritixi Lithos für die Unterstützung beim Golfspielen.
Vielen Dank an @ User2428118 für das Golfspielen mit 14 Bytes
(Funktioniert nicht in IE7) (Zeilenumbrüche sollten als "
\n
" und Tabulator als "\t
" in der Eingabezeichenfolge eingegeben werden, alle Unicode-Zeichen sollten als " " eingegeben werden.\u####
)Probieren Sie es online
Erklärung der Funktionsweise und ungolfed Code
Zunächst generiert das Programm Knuth Morris Pratt-Arrays für jede mögliche Teilzeichenfolge.
Als nächstes ermittelt das Programm die maximale Übereinstimmungslänge für jeden einzelnen Index im Wort mit jeder Teilzeichenfolge. (Dies ist O (n ^ 2) Zeit)
Das Programm verwendet diese Daten, um die längsten Teilzeichenfolgen zu finden, die für jedes Anfangszeichen in der Zeichenfolge dreimal vorkommen.
Das Programm verwendet diese Daten, um alle Teilzeichenfolgen, die nicht genau dreimal vorkommen, und alle Teilzeichenfolgen der längsten gültigen Teilzeichenfolgen zu entfernen.
Als nächstes legt das Programm fest, dass alle überlappenden oder partiellen Teilzeichenfolgen entfernt werden sollen.
Für jeden zu entfernenden Wert werden auch alle entsprechenden Teilzeichenfolgen entfernt.
Schließlich fügt das Programm das Array von Teilzeichenfolgen zusammen und gibt es aus.
quelle
while
undif
Blöcke, in denen nur 1 Anweisung enthalten ist. Sie können die Klammern{}
um diese Anweisung entfernen . Zum Beispielif(word.charAt(index+i)==word.charAt(index+j)){j++;}
kann werdenif(word.charAt(index+i)==word.charAt(index+j))j++;
&&
s verwendet, umif
Anweisungen zu ersetzen . Ich habe Anweisungen in Schleifen verschoben, damit sie eine Anweisung unter sich haben, damit ich Klammern entfernen kann. Ich habe Ternaries verwendet, um einige if-Anweisungen zu ersetzen. Ich bewegte Sachen herum und landete bei 946 Bytes . Wenn Sie etwas nicht verstehen, was ich getan habe, können Sie mich