Manchmal ist es so, dass ich beim Schreiben eines Satzes abgelenkt bin und am Ende zweimal zweimal hintereinander die gleichen Wörter tippe.
Um sicherzustellen , dass andere Menschen davon nicht gestört werden, müssen Sie ein Programm schreiben, das dieses Problem behebt!
Aufgabe
Wenn Sie eine Eingabezeichenfolge angegeben haben (falls dies für Ihre Sprache von Bedeutung ist, können Sie eine reine ASCII-Eingabe ohne Zeilenvorschub annehmen) str
, die irgendwo in der Mitte eine Teilzeichenfolge enthält, die zweimal unmittelbar hintereinander auftritt, geben Sie die Zeichenfolge mit einer Instanz davon zurück Teilzeichenfolge entfernt.
Geben Sie bei mehreren Möglichkeiten die kürzestmögliche Antwort zurück (dh wählen Sie die längste aufeinanderfolgende wiederholte Teilzeichenfolge aus und entfernen Sie diese).
Entfernen Sie bei mehreren gleich langen, sich wiederholenden Teilzeichenfolgen die erste (d. H. Die erste, die beim Lesen der Zeichenfolge von vorne nach hinten auftritt).
Sie können davon ausgehen, dass die Eingabe korrekt ist (dh immer eine sich wiederholende Teilzeichenfolge enthält), was dazu beitragen kann, die Eingabe zu verbessern.
Beispiele
- Eingang:
hello hello world
-> Ausgang:hello world
. - Eingang:
foofoo
-> Ausgang:foo
. (Also: Ja, die Zeichenfolge besteht möglicherweise nur zweimal aus dem sich wiederholenden Teil.) - Eingabe:
aaaaa
-> Ausgabeaaa
:, da hier die am längsten wiederholte aufeinanderfolgende Teilzeichenfolge stehtaa
. - Eingabe:
Slartibartfast
-> Dies ist keine gültige Eingabe, da sie keine aufeinanderfolgende wiederholte Teilzeichenfolge enthält, sodass Sie diesen Fall nicht behandeln müssen. - Eingabe:
the few the bar
-> Dies ist eine weitere ungültige Eingabe, da der Wiederholungsteil unmittelbar auf den Originalteil folgen soll. In diesem Fallthe
undthe
durch etwas anderes dazwischen getrennt, ist diese Eingabe ungültig. - Eingang:
ababcbc
-> Ausgang:abcbc
. Die zwei möglicherweise am längsten hintereinander wiederholten Teilzeichenfolgen sindab
undbc
. Wie bereits erwähnt,ab
ist dies die richtige Antwort. - Input:
Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo
. Ausgang:Buffalo buffalo buffalo buffalo Buffalo buffalo
. (Beim durchgeführten Austausch muss die Groß- und Kleinschreibung beachtet werden.) - Eingang:
Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.
-> Ausgang:Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.
. Es wird nur die längste hintereinander wiederholte Teilzeichenfolge entfernt.
Ihr Code sollte so kurz wie möglich sein, da dies Code-Golf ist , damit die kürzeste Antwort in Bytes gewinnt. Viel Glück!
Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.
als Eingabe nehmen, sollte die Ausgabe seinSometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.
. Nur die am längsten gefundene Duplikation wird entfernt.p
inhappens
Antworten:
Perl 6 , 40 Bytes
Versuch es
quelle
Retina ,
3533 BytesDie Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.
Probieren Sie es online!
Erläuterung
Da Regex-Engines nach Übereinstimmungen von links nach rechts suchen, ist es nicht trivial, die längste Übereinstimmung zu finden, unabhängig von der Position. Dies kann mit den .NET-Bilanzkreisen durchgeführt werden, aber das Ergebnis ist ziemlich unangenehm lang:
Also nahm ich an, dass ich versuchen würde, dies zu vermeiden, indem ich einige andere Retina-Funktionen nutzte.
Zunächst wenden wir im Wesentlichen alle möglichen Substitutionen an, eine in jeder Zeile. Dazu passen wir die Position vor einem Match an (anstelle des Matches selbst), um überlappende Matches zuzulassen. Dies geschieht, indem der echte Regex in einen Lookahead eingefügt wird. Dieser Lookahead erfasst dann den Rest mit Ausnahme des Duplikats, das in Gruppe 2 entfernt werden soll. Wir schreiben Gruppe 2 (Löschen des Duplikats), einen Zeilenvorschub und dann die gesamte Eingabe bis zum Match zurück, wodurch wir im Grunde eine neue Zeile erhalten ersetzt werden.
Am Ende haben wir eine Zeile für jede Übereinstimmung, wobei das entsprechende Duplikat entfernt wird. Am Ende gibt es auch wieder die volle Eingabe, ohne dass Ersetzungen vorgenommen werden.
Nachdem wir alle möglichen Substitutionen haben, wollen wir das kürzeste Ergebnis (das der längsten entfernten Wiederholung entspricht).
Also sortieren wir zuerst die Zeilen nach Länge.
Und dann behalten wir nur die erste Zeile.
quelle
Jelly ,
2219 Bytes-2 Bytes dank Dennis (Argumentumkehr vermeiden, subtil redundantes Inkrement entfernen)
Probieren Sie es online!
Volles Programm (Es wurde ein Fehler gefunden, der darin besteht, dass
ÐṀ
nicht mit der richtigen Arität gegenüber Dyaden vorgegangen wird. Dieser Fehler wird in Kürze behoben. Ich bin mir jedoch nicht sicher, ob hier ein kürzerer Code möglich ist).Wie?
Findet das erste der längsten Segmente der Eingabe, sodass eine Wiederholung in der Eingabe vorhanden ist, und entfernt es aus der Eingabe.
quelle
JavaScript (ES6),
81 bis74 ByteBearbeiten: 7 Bytes durch Stehlen von @ Arnauld's
m[r.length]
Trick gespeichert .quelle
PowerShell , 87 Byte
Probieren Sie es online! (alle Testfälle)
Erläuterung
Grundsätzlich starten wir von innen
Matches
mit dem(.+)\1
regulären Ausdruck, um alle Übereinstimmungsobjekte für die angegebene Zeichenfolge zurückzugeben. Der reguläre Ausdruck entspricht einer beliebigen Folge von Zeichen, die von ihm selbst gefolgt wird.Dann werden die resultierenden Übereinstimmungsobjekte weitergeleitet
sort
, um nach ihrerLength
Eigenschaft sortiert zu werden (abgekürzt als Platzhalter). Dies führt zu einem Array von Übereinstimmungen, die nach Länge aufsteigend sortiert sind. Indizieren Sie also mit[-1]
, um das letzte Element (das längste) zu erhalten. Der Wert dieser Übereinstimmung ist jedoch die Übereinstimmung, nicht die Gruppe, daher enthält sie die Wiederholung, sodass wir das Group-Objekt (|% Gr*
) und dann den Wert von that (|% V*
) abrufen , um die größte wiederholte Zeichenfolge zu erhalten. Das Gruppenobjekt ist eigentlich ein Array, weil Gruppe 0 immer die Übereinstimmung ist, aber ich möchte die tatsächliche Gruppe (1), also ist der resultierende Wert tatsächlich der Wert s , und daher wird indexiert, um das zweite Element zu erhalten[1]
. Dieser Wert wird in ein reguläres Objekt selbst umgewandelt und anschließend in dasReplace
Die Methode wird für die ursprüngliche Zeichenfolge aufgerufen und durch nichts ersetzt, und nur die erste Übereinstimmung wird ersetzt (|% Re* $s '' 1
).quelle
Haskell , 101 Bytes
Hauptfunktion ist
f
, es dauert und gibt a zurückString
.Probieren Sie es online!
Als ich das begann, habe ich importiert
Data.List
und verwendetmaximum
,tails
,inits
undisPrefixOf
. Irgendwie wurde das so. Aber ich habe es trotzdem geschafft, nur 11 Bytes zu entfernen ...Anmerkungen
splitAt
/a
teilt einen String an einem bestimmten Index.s
ist die Eingabezeichenfolge.i
Die folgenden Liste von Zahlen[0 .. length s - 1]
, die-1
sind um zu arbeiten , dasssplitAt
Splits am Ende , wenn ein zu großen Index gegeben.n
length s
Wenn das aktuelle Längenziel für den wiederholten Teil minus ist , wird es so gewählt, dass wir nicht zwei Zahlenlisten und / oder die Syntax mit abnehmender Wortzahl verwenden müssen.p
,r
Undt
sind ein Dreifach Splits
, wobeir
der Teil wiederholt vorgesehen. Dasfmap
dortige verwendet das(,) String
Functor
, um eine Variable für einen Zwischensplit zu vermeiden.!!0
Wählt das erste Element der Trefferliste aus.quelle
Jelly ,
2321 BytesVielen Dank an @ JonathanAllan für seine
Ṭœp
Idee, die 2 Bytes gespart hat.Probieren Sie es online!
quelle
Mathematica,
636059 Bytes4 Bytes gespart durch Martin Ender .
Anonyme Funktion. Nimmt einen String als Eingabe und gibt einen String als Ausgabe zurück.
quelle
~SortBy~StringLength
sortiert Strings alphabetisch, wenn ihre Längen gleich sind ...SortBy
and wrapStringLength
in einer Liste, um eine stabile Sortierung zu erhalten.JavaScript (ES6), 70 Byte
Testfälle
Code-Snippet anzeigen
quelle
aaaabaaab
aber schön anreduce
.Dies sollte ein Kommentar sein, aber ich habe nicht genug Ruf, um ihn zu kommentieren. Ich möchte @Neil nur mitteilen, dass sein Code auf 77 Byte reduziert werden kann. Sie müssen keine Forward-Assertion in regulären Ausdrücken verwenden. Hier ist die reduzierte Version:
quelle
aabab
ist das kürzeste Beispiel dafür, wo Ihr Vorschlag fehlschlägt.C # 169 Bytes
Erläuterung
Dies ist der Brute-Force-Ansatz: Probieren Sie alle möglichen Teilzeichenfolgen aus, bis Sie die längste sich wiederholende Teilzeichenfolge finden. Zweifellos ist Regex effizienter, aber der Umgang mit Regex in C # ist in der Regel recht ausführlich.
quelle
PHP,
8482 BytesAnmerkung: Verwendet die IBM-850-Codierung.
Laufen Sie wie folgt:
Erläuterung
Optimierungen
quelle