Erstellen Sie ein Programm oder eine Funktion, die eine Liste von Zeichenfolgen als Eingabe verwendet und die längste Zeichenfolge ausgibt, die eine Teilzeichenfolge aller Eingabezeichenfolgen ist. Wenn es mehrere gleich lange Teilzeichenfolgen gibt, die nicht mehr Teilzeichenfolgen sind, geben Sie eine davon aus.
- Dies kann bedeuten, dass der leere String ausgegeben wird.
- Wenn es mehrere gültige Ausgaben gibt, können Sie eine davon ausgeben. Sie müssen für eine bestimmte Eingabe keine konsistente Ausgabe angeben, solange die Ausgabe immer gültig ist.
- In der Eingabe ist immer mindestens eine Zeichenfolge enthalten, es ist jedoch möglicherweise keine nicht leere Zeichenfolge vorhanden.
- Alle druckbaren ASCII-Zeichen werden möglicherweise in der Eingabe angezeigt. Sie können davon ausgehen, dass dies die einzigen Zeichen sind, die angezeigt werden.
- Sie können die Eingabe oder Ausgabe mit einer der Standardmethoden erstellen .
- Standardlücken sind nicht erlaubt.
- Das ist Code-Golf - je weniger Bytes Code, desto besser.
Testfälle:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf
string
subsequence
Sara J
quelle
quelle
undefined
bedeutet dies, dass es keine gültige Ausgabezeichenfolge gibt. Wenn die leere Zeichenfolge (oder eine andere Zeichenfolge) eine gültige Ausgabe ist, ist die Behauptung, dass keine gültige Ausgabe vorhanden ist, falsch.Antworten:
Python 2 , 82 Bytes
Probieren Sie es online!
Nimmt eingegebenen splatted. Zeitüberschreitung bei Eingaben, bei denen die erste Zeichenfolge lang ist.
Die Idee ist, Teilzeichenfolgen der ersten Zeichenfolgen
h
zu verwenden, um die längste zu finden, die in allen verbleibenden Zeichenfolgen enthalten istt
. Dazu verzweigen wir beim Entfernen des ersten oder letzten Zeichens von rekursivh
.Python 2 , 94 Bytes
Probieren Sie es online!
Eine direktere Methode. Die Hilfsfunktion
g
generiert die Menge aller Teilzeichenfolgen vons
, und die Hauptfunktion nimmt die längste in ihrer Schnittmenge ein.quelle
Brachylog (v2),
39 BytesProbieren Sie es online!
Volles Programm. Eingabe von der Standardeingabe (als JSON-artige Liste von Zeichenfolgen), Ausgabe in die Standardausgabe.
Erläuterung
Anscheinend ist die Tiebreak-Reihenfolge
s
in Brachylog anders als in fast allen anderen Fällen. Wir müssen sie daher manuell überschreiben, um die längste Ausgabe zu erzielen. (Das ist ein bisschen frustrierend: vier zusätzliche Zeichen für die Außerkraftsetzung plus zwei Gruppierungszeichen, da Brachylog nicht zwei Metapredicates hintereinander analysiert.)Brachylogs
s
gibt keine leeren Teilzeichenfolgen zurück, daher brauchen wir einen kleinen Trick, um das zu umgehen: Anstatt eine Funktionsübergabe (was normalerweise der Fall ist) zu erstellen, schreiben wir ein vollständiges Programm und geben es auf die Standardausgabe aus. Auf diese Weise geben wir eine gemeinsame Teilzeichenfolge einfach aus und sind fertig. Wenn es keinen gemeinsamen Teilstring gibt, gibt das Programm einen Fehler aus, druckt aber trotzdem nichts auf die Standardausgabe und gibt daher den Null-String wie vorgesehen aus.quelle
s
falsch an die Tiebreak-Reihenfolge erinnert , und das Überschreiben der Tiebreak-Reihenfolge ist byteweise ziemlich teuer. Tun Sie das jetzt trotzdem, denn es ist wichtig, dass die Antwort richtig ist. Irgendwie bemerkte keiner der Testfälle, die ich ausprobiert hatte, den Unterschied.s
besteht darin, zuerst alle Präfixe der Eingabe (längste zuerst), dann die erste zuGelee ,
126 BytesProbieren Sie es online!
Vielen Dank an @ JonathanAllan für das Speichern von 6 Bytes!
quelle
Ẇ€œ&/Ṫḟ0
würde die Arbeit erledigen und vier Bytes einsparen, da die Unterzeichenfolgen bereits nach Länge geordnet sind, daher wird das gefilterte Ergebnis sein; dann bleibt nur, dass wenn es keine Übereinstimmungen gibt, der Schwanz eine Null erzeugt, und da wir garantierte Listen von Zeichen sind, können wir diese einfach herausfiltern.œ&/
kann durchf/
hier sparen eine andere ersetzt werdenẆ€f/ṛ/
.Ruby 2.6,
76 5954 BytesProbieren Sie es online!- Ruby 2.5 Version (56 Bytes)
Wie?
Erstellen Sie eine Liste möglicher Übereinstimmungen, die zunächst auf das ursprüngliche Array festgelegt wurde. Durchlaufen Sie die Liste, und fügen Sie dem Ende der Liste zwei neue Zeichenfolgen hinzu, wenn eine Zeichenfolge nicht übereinstimmt, und kürzen Sie dabei das erste oder das letzte Zeichen ab. Am Ende wird eine Übereinstimmung (eventuell eine leere Zeichenfolge) gefunden.
Danke Kirill L für -2 Bytes und Histokrat für weitere -2
quelle
R ,
119116108106 BytesProbieren Sie es online!
Suchen Sie alle Teilzeichenfolgen jeder Zeichenfolge, suchen Sie die Schnittmenge jeder Teilzeichenfolgenliste und geben Sie schließlich eine der längsten zurück.
-3 Bytes dank Kirill L.
-8 Bytes mit
lapply
anstelle vonMap
Nochmals -2 Bytes dank Kirill L., der Klammern entfernt
quelle
nchar
reichen 2 Vorkommen aus, um etwas zu retten, indem ich michnchar
als unärer Operator anmelde.list
wir ebenfalls -3 Bytes.05AB1E ,
1498 Bytes-6 Bytes dank @Adnan .
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
quelle
€Œ.«Ãõªéθ
sollte für 9 Bytes arbeiten.Å«Ã
, aber wusste nicht, dass ich.«Ã
stattdessen hätte verwenden sollen .. Danke!€Œ.«ÃéθJ
für 8 arbeiten.Zsh ,
126 ...96 Bytes-3 Bytes aus der Arithmetik für, -6 Bytes aus der impliziten
"$@"
(danke roblogic), -5 Bytes aus dem Entfernen nicht benötigter{
}
, -1 Bytes aus der Kurzform vonfor
, -1 Bytes durch Verwenden vonrepeat
, -1 Bytes durch Verkettenfor s ($b)
mit seinem Hauptteil, -13 Bytes durch Ändern der Wiederholungsschleife für einen bestimmten Wert.Probieren Sie es online! Probieren Sie es online!Probieren Sie es online!Wir lesen alle möglichen Teilzeichenfolgen in das Array ein
a
und stellen dannb
den Schnittpunkt der Arraysa
und einb
. Das Konstrukt${b-$a}
wird nur$a
bei der ersten Iteration ersetzt: Im Gegensatz zu seiner Geschwistererweiterung${b:-$a}
wird es nicht ersetzt, wennb
gesetzt, sondern leer.quelle
a+=( $l[1+i/$#l,1+i%$#l] )
for
for l in "$@"
einfach zu schneidenfor l;
- es ist ein Bash-Trickb=(${${b-$a}:*a})}
man zshexpn
und vorman zshparam
allem. Ich habe sie immer offen, wenn ich eine Antwort schreibe.Haskell , 80 Bytes
Probieren Sie es online!
Holen Sie sich alle Suffixe (
tails
) des ersten Wortesx
in der Liste und nehmen Sie alle Präfixe (inits
) dieser Suffixe, um alle Teilzeichenfolgens
von zu bekommenx
. Halten Sie jeweils :s
zuisInfixOf
all
Strings in der verbleibenden Lister
. Sortieren Sie diese Teilzeichenfolgen nach Länge (mit dem(0<$)
Trick ) und geben Sie die letzte zurück.quelle
Retina 0.8.2 , 48 Bytes
Probieren Sie es online! Erläuterung:
Suchen Sie für jedes Suffix der ersten Zeichenfolge das längste Präfix, das auch eine Teilzeichenfolge aller anderen Zeichenfolgen ist. Listen Sie alle diese Suffix-Präfixe (dh Teilzeichenfolgen) auf. Wenn es keine passenden Teilzeichenfolgen gibt, erhalten wir nur die leere Zeichenfolge, die wir sowieso wollen.
Sortieren Sie die Teilzeichenfolgen in umgekehrter Reihenfolge der Länge.
Behalten Sie nur die erste, dh die längste Teilzeichenfolge.
quelle
n
sei die Anzahl der Argumente. Dann(?=(.*\n.*\1)*.*$)
sollte es sein(?=(.*\n.*\1){n-1}.*$)
, nicht wahr? Testfall:["very", "different", "much"] -> [""]
{n}
könnten Sie Start- und(.+)(?=(.*\n.*\1){n}
n
(?<=^.*).*$
TSQL-Abfrage, 154 Byte
Probieren Sie es online aus
Die Groß- und Kleinschreibung wird beachtet, indem die Spalte 'a' mit einer Sortierung deklariert wird, die CS enthält (Groß- und Kleinschreibung beachten).
Wenn alle Zeichenfolgen von 2540 Startpositionen (viele identisch) getrennt werden, die nützlichen Werte jedoch zwischen 1 und 2070 liegen und 0 bis 22 Zeichen nach der Startposition enden, kann die Endposition länger sein, indem der Typ auf 'P' anstelle von 'L' geändert wird. würde aber die leistung lähmen.
Diese eindeutigen Zeichenfolgen innerhalb jeder Rownumber werden gezählt. Die höchste Anzahl entspricht immer der Anzahl der Zeilen in der Tabellenvariablen '@'. Wenn Sie die Reihenfolge bei gleicher Anzahl umkehren, bleibt der Teilstring mit den meisten Übereinstimmungen über den Ergebnissen, gefolgt von der umgekehrten Länge des Teilstrings, und der längsten Übereinstimmung mit den meisten Übereinstimmungen oben. Die Abfrage wählt nur die oberste Zeile aus.
Ändern Sie den ersten Teil der Abfrage in, um alle Antworten zu erhalten
quelle
C # (Visual C # Interactive Compiler),
320 bis257 ByteProbieren Sie es online!
Requisiten zu @Expired Data und @dana
quelle
Perl 6 ,
6260 BytesProbieren Sie es online!
Ich ärgere mich ein wenig, dass Perl 6 keine Einstellungsoperationen für Listen von Listen ausführen kann, weshalb es ein zusätzliches
.comb
und gibt>>
dort.Eine weitere ärgerliche Sache ist, dassWie in den Kommentaren ausgeführt,max
ich keine Funktion zum Vergleichen von Artikeln verwenden kann,sort
sondern stattdessen verwenden muss.max
kann man ein Argument nehmen, es endet jedoch länger, da ich diemax
Rückgabe einer negativen Unendlichkeit berücksichtigen muss , wenn es gemeinsame Teilzeichenfolgen gibt ( online ausprobieren ! ).quelle
max
kann eine solche Funktion übernehmen (Arity 1), entweder nach Position, wenn sie im OO-Modus aufgerufen wird, oder nach einem benannten:by
Argument im prozeduralen Modus.Japt v2.0a0
-hF
, 8 BytesDanke an Shaggy für das Speichern von 3 Bytes
Versuch es
quelle
-F
standardmäßig auf den leeren String.Japt
-h
, 8 Bytes(Ich könnte die letzten 3 Bytes abschneiden und
-Fh
stattdessen das Flag verwenden, aber ich bin kein Fan von using-F
)Probieren Sie es aus oder führen Sie alle Testfälle aus
quelle
Python 3 , 137 Bytes
Probieren Sie es online!
quelle
Python 2 , 103 Bytes
Probieren Sie es online!
Dies ist ein anonymes Lambda, das jedes Element in die Menge aller Teilzeichenfolgen umwandelt, dann
reduce
nach set intersection (set.__and__
) und dann dasmax
Element nachlen
gth zurückgibt.quelle
set.intersection
.C # (Visual C # Interactive Compiler) ,
147 -145 ByteProbieren Sie es online!
quelle
Perl 5 (
-aln0777F/\n/
-M5.01
-MList::util=max
), 99 Byteskann sicherer golfen werden
TIO
quelle
JavaScript (ES6),
98 bis92 ByteProbieren Sie es online!
quelle
Kohle , 30 Bytes
Probieren Sie es online! Link ist eine ausführliche Version des Codes. Dieser Algorithmus ist effizienter und kürzer als das Generieren aller Teilzeichenfolgen. Erläuterung:
Füge den letzten String aus der Eingabeliste in eine Variable ein.
Nullen Sie den Teilstring-Startindex.
Durchlaufen Sie alle möglichen Teilzeichenfolgen-Endindizes. (Tatsächlich geht dies ohne die Länge von 0 aus, sodass der Wert später angepasst wird.)
Beziehen Sie den aktuellen Teilstring.
Überprüfen Sie, ob diese Teilzeichenfolge in allen anderen Eingabezeichenfolgen enthalten ist.
Wenn dies der Fall ist, überdrucken Sie einen zuvor ausgegebenen Teilstring.
Andernfalls versuchen Sie, den Teilzeichenfolgen-Startindex zu erhöhen.
quelle
Bash ,
295.. 175 BytesNicht schön, aber immerhin funktioniert es. Probieren Sie es online
-37 durch allgemeine Reinigung ; -52 durch Plagiieren aus der Antwort von zsh ; -26 durch Ersetzen des Arrays durch eine Schleife ; -2 dank GammaFunction ; -3 entfernt
i=0
vonfor
SchleifenHier ist das originale ungolfed-Skript mit Kommentaren
quelle
((k==$#))&&
mit((k-$#))||
. Damit können Sie auch verwenden,k=
anstatt es auf 0 zu setzen.Rot ,
266174 BytesProbieren Sie es online!
Die Rekursion wurde in Iteration geändert und die Sortierung wurde entfernt.
quelle
Perl 5 , 87 Bytes
Probieren Sie es online!
quelle
JavaScript (Node.js) , 106 Byte
Probieren Sie es online!
quelle
Gaia , 15 Bytes
Probieren Sie es online!
quelle
PowerShell ,
16516387 Byte-76 Bytes dank Nail für die großartige Regexp .
Probieren Sie es online!
Weniger golfen:
quelle
JavaScript (Node.js) , 90 Byte
Probieren Sie es online! Schamlos gestohlene Testfälle von @Arnauld. Port meiner Charcoal-Antwort.
quelle
Java (JDK) , 158 Byte
Probieren Sie es online!
Credits
quelle
Perl 5 , 86 Bytes
Probieren Sie es online!
quelle
Pyth , 16 Bytes
Probieren Sie es online!
quelle