Finden Sie privilegierte Teilzeichenfolgen

8

Privilegierte Saiten

Der Satz privilegierter Zeichenfolgen wird wie folgt rekursiv definiert.

  • Alle Zeichenfolgen der Länge 0 oder 1 sind privilegiert.
  • Eine Zeichenfolge mit seiner Länge von mindestens 2 ist privilegiert, wenn eine kürzere privilegierte Zeichenfolge vorhanden ist t, die sgenau zweimal vorkommt, einmal als Präfix und einmal als Suffix. Überlappende Vorkommen werden als unterschiedlich gezählt.

Zum Beispiel sind die Saiten aa, aaaund abasind privilegiert, aber abund aabsind es nicht.

Eingang

Eine alphanumerische Zeichenfolge.

Ausgabe

Alle privilegierten Teilzeichenfolgen der Eingabezeichenfolge, jeweils genau einmal, in beliebiger Reihenfolge. Die Ausgabe kann im nativen Array-Format Ihrer Sprache (oder dem nächstgelegenen Äquivalent) erfolgen oder eine Teilzeichenfolge pro Zeile gedruckt werden.

Lustige Tatsache

Die Anzahl der Zeichenfolgen in der Ausgabe ist immer genau length(s) + 1( Quelle ).

Regeln

Sowohl Funktionen als auch vollständige Programme sind zulässig. Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.

Testfälle

Diese werden zuerst nach Länge und dann alphabetisch sortiert, aber jede Reihenfolge ist akzeptabel.

"" -> [""]
"a" -> ["","a"]
"abc" -> ["","a","b","c"]
"abcaaabccaba" -> ["","a","b","c","aa","cc","aaa","aba","abca","abcca","bccab","bcaaab","caaabc"]
"1010010110101010001101" -> ["","0","1","00","11","000","010","101","0110","1001","01010","10001","10101","010010","101101","0101010","1010101","01011010","10100101","1010001101","1101010100011","00101101010100","011010101000110"]
"CapsAndDigits111" -> ["","1","A","C","D","a","d","g","i","n","p","s","t","11","111","igi","sAndDigits"]

Bestenliste

Hier ist eine Rangliste nach Sprachen, mit freundlicher Genehmigung von Martin Büttner .

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift unter Verwendung der folgenden Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihrer Einreichung? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Code-Snippet anzeigen

code-golf string Zgarb
quelle
Kann die Ausgabe durch Leerzeichen getrennt werden oder muss sie durch Zeilenumbrüche getrennt werden? (wenn gedruckt)
Sp3000
@ Sp3000 Es müssen entweder Zeilenumbrüche sein, oder Ihre Sprache druckt eine Reihe von Zeichenfolgen.
Zgarb
2
Sie bitten uns also, Ihre privilegierten Zeichenfolgen zu überprüfen?
Imallett
warum so eine lange Definition? Könnten Sie nicht gleichbedeutend schreiben: "Eine privilegierte Zeichenfolge ist eine Zeichenfolge, die mit demselben Symbol beginnt und endet, wobei dieses Symbol nirgendwo anders in der Zeichenfolge vorkommt." =)
Mints97
1
@ Mints97 Die kürzere Zeichenfolge tdarf kein einzelnes Symbol sein. Beispielsweise aaahandelt es sich um eine privilegierte Zeichenfolge, da sie aaein Präfix und ein Suffix enthält und nur zweimal vorkommt. Ich habe es als Beispiel hinzugefügt.
Zgarb

Antworten:

4

.NET Regex, 31 Byte

(?=(((?<=(\3\2|)).+?(?<=\3))*))

Die Zeichenfolgen werden \1in jedem Spiel erfasst .

Erklärung

(?=                             # Lookahead. This makes it possible to catch overlapped
                                #   strings in \1.
    (                           # The captured group \1 for result.
        (                       # Match 0 or more occurrences.
            (?<=(\3\2|))        # Set \3 to the string from last \3 to the current position,
                                #   or an empty string for the first time.
            .+?(?<=\3)          # Match a shortest nonempty string so that the whole string
                                #   from the beginning to the current position ends with \3.
        )*
    )
)
jimmy23013
quelle
5

CJam, 33 45 39 38 Bytes

l_,,\f>{(0{:U2$>2$2$#):T<+UT+T}g;\;N}%

Angenommen, es wird ohne nachgestellte Zeilenumbruch gedruckt. Der nachfolgende Zeilenumbruch bedeutet also einen leeren Teilstring ...

Erklärung

l              " Read one line. ";
_,,            " Get an array of 0 to array length-1. ";
\f>            " Get all nonempty suffixes. ";
{              " For each suffix: ";
    (          " Extract the first character. Say the first character X and the rest Y. ";
    0          " Push U = 0. ";
    {          " Do: ";
        :U     " Set variable U. ";
        2$>    " Z = Y with first U characters removed. ";
        2$2$#  " Find X in Y, or return -1 if not found. ";
        ):T    " Increment and save it in T. ";
        <+     " Append the first T characters of Z to X. ";
        UT+    " U += T. ";
        T      " Push T. ";
    }g         " ...while T is nonzero. ";
    ;\;        " Discard U and Y. ";
    N          " Append a newline. ";
}%
jimmy23013
quelle
4

Python 2, 179 173 164 Bytes

exec"f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n%s);g=lambda s:filter(f,{''}|{s[i:j+1]for i%sfor j%s})"%((" in range(len(s))",)*3)

Derzeit ziemlich sperrig - ich frage mich, ob es möglich ist, den Check und die Teilstring-Generation irgendwie zu kombinieren ...

Das Lambda fist im Grunde eine is_privileged()Funktion, die die drei Bedingungen zu einem Vergleich kombiniert (Teilzeichenfolge ist privilegiert, erscheint zweimal, ist Suffix und Präfix).

Erweitert:

f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n in range(len(s)))
g=lambda s:filter(f,{''}|{s[i:j+1]for i in range(len(s))for j in range(len(s))})
Sp3000
quelle
3

Python 3, 131 129 Bytes

f=lambda s,p={''}:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)or list(p)

Dadurch werden rekursiv privilegierte Teilzeichenfolgen gefunden, beginnend mit den kürzesten und dem Hinzufügen zu einer Menge. Die Menge wird dann verwendet, um zu bestimmen, ob längere Teilzeichenfolgen privilegiert sind.

Leider handelt es sich um eine Einwegfunktion. Hier ist ein entsprechendes vollständiges Programm ( 145 Bytes ):

p={''}
f=lambda s:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)
f(input())
print(list(p))
grc
quelle
3

Python, 152 147 126 116 Bytes

def n(s):
 w='';t=[w]
 for a in s:w+=a;t+=[w[w.rfind(w[-max(len(q)for q in t if w.endswith(q)):],0,-1):]]
 return t

Wie im verlinkten Artikel gezeigt, gibt es für jedes Präfix einer Zeichenfolge ein eindeutiges privilegiertes Suffix. Dieses Suffix hat die Form, p·u·pin der psich die längste zuvor gefundene privilegierte Teilzeichenfolge befindet, die ein Suffix des Präfixes ist. (Die Suche ist das Argument für max, das tatsächlich die Länge von findet, pweil es einfacher war maxals longest.) Sobald pes gefunden wurde, wird das Suffix selbst gebildet, indem nach dem vorletzten Vorkommen von pim Präfix gesucht wird , wobei die rfindEinschränkung verwendet wird, das nicht zu verwenden letztes Zeichen. Wir wissen, dass dies funktionieren wird, da pes sich um ein zuvor gefundenes Suffix handelt. (Ein strengerer Beweis des Algorithmus kann aus dem Papier abgeleitet werden.)

Ich bin mir ziemlich sicher, dass dies in linearer Zeit unter Verwendung eines Suffixbaums anstelle des oben verwendeten quadratischen kubischen Algorithmus implementiert werden könnte , aber das obige Programm ist sicherlich in allen Testfällen schnell genug und verarbeitet eine Zeichenfolge von 2000 as in a etwas weniger als eine Sekunde auf meinem (nicht übermächtigen) Laptop.

Rici
quelle
2

Ruby, 87

Ich habe das Gefühl, dass es hier irgendwo eine rekursive Regex-Lösung gibt, aber ich bin nicht sehr gut darin, also hier eine sehr langsame und lange rekursive Funktion.

f=->s{s[/./]?(o=f[$']|f[s.chop];o.any?{|t|s[/^#{t}/]&&s[/.#{t}/]&&!$'[0]}&&o<<s;o):[s]}

Der Algorithmus ist ungefähr der gleiche wie der von grc und wird langsamer (aber kürzer), indem keine einzelnen Sonderzeichen verwendet werden. Eine Zeichenfolge mit einem Zeichen kann als privilegiert angesehen werden, da die leere Zeichenfolge als Präfix, Suffix und nirgendwo anders verwendet wird.

Der andere interessante Trick ist die Verwendung $'einer von Perl geerbten magischen Variablen, die den Wert der Zeichenfolge nach der letzten Übereinstimmung mit regulären Ausdrücken annimmt. Dies gibt mir eine kurze Möglichkeit, das erste Zeichen aus einer Zeichenfolge herauszuschneiden, obwohl ich fast alle diese Zeichen erhalte, indem ich es s[/./]anstelle von einrichten muss s[0]. Ich verwende es erneut, um zu überprüfen, ob die zweite Teilzeichenfolgenübereinstimmung am Ende der Zeichenfolge erfolgt.

Histokrat
quelle
1

J, 92 Bytes

Dauert bei der längsten Eingabe einige Sekunden.

pprüft, ob eine Zeichenfolge privilegiert ist (mit Rekursion), sprüft jeden Teilstring mit p.

   p=.1:`(+./@:(($:@>@{.*((2=+/)*1={:)@{.@=)@(<\))~i.@#)@.(1<#)
   s=.3 :'~.a:,,(<@#~p)\.\y'

Tests:

   s 'CapsAndDigits111'
┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬───┬─┬──────────┬─┬──┬───┐
││C│a│p│s│A│n│d│D│i│g│igi│t│sAndDigits│1│11│111│
└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴───┴─┴──────────┴─┴──┴───┘       

   input =. '';'a';'ab';'abc';'abcaaabccaba';'1010010110101010001101';'CapsAndDigits111'

   s each input
┌──┬────┬──────┬────────┬─────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────────────────...
│┌┐│┌┬─┐│┌┬─┬─┐│┌┬─┬─┬─┐│┌┬─┬─┬─┬────┬──┬───┬──────┬──────┬──┬─────┬─────┬───┐│┌┬─┬─┬───┬───┬──┬────┬──────┬────────┬──┬────┬──────┬────────┬─────┬─────┬───────┬───────┬──────────────┬───┬─────┬─────────────┬───────────────┬──────────┐│┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬...
││││││a││││a│b││││a│b│c││││a│b│c│abca│aa│aaa│bcaaab│caaabc│cc│abcca│bccab│aba││││1│0│101│010│00│1001│010010│10100101│11│0110│101101│01011010│10101│01010│1010101│0101010│00101101010100│000│10001│1101010100011│011010101000110│1010001101││││C│a│p│s│A│n│d│D│i│...
│└┘│└┴─┘│└┴─┴─┘│└┴─┴─┴─┘│└┴─┴─┴─┴────┴──┴───┴──────┴──────┴──┴─────┴─────┴───┘│└┴─┴─┴───┴───┴──┴────┴──────┴────────┴──┴────┴──────┴────────┴─────┴─────┴───────┴───────┴──────────────┴───┴─────┴─────────────┴───────────────┴──────────┘│└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴...
└──┴────┴──────┴────────┴─────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────────────────...

   #@s each input NB. number of strings in outputs
┌─┬─┬─┬─┬──┬──┬──┐
│1│2│3│4│13│23│17│
└─┴─┴─┴─┴──┴──┴──┘

   # each input NB. input lengths
┌─┬─┬─┬─┬──┬──┬──┐
│0│1│2│3│12│22│16│
└─┴─┴─┴─┴──┴──┴──┘
randomra
quelle
1

JavaScript (ES6) 195

Die P-Funktion überprüft rekursiv, ob eine Zeichenfolge privilegiert ist.
Die F-Funktion versucht jeden Teilstring, der in der angegebenen Zeichenfolge enthalten ist. Gefundene Zeichenfolgen werden als Schlüssel einer Hashtabelle gespeichert, um Duplikate zu vermeiden.
Zuletzt werden die Schlüssel als Ausgabe zurückgegeben.

F=a=>{
  P=(s,l=s.length,r=l<2,j=1)=>{
    for(;!r&&j<l;j++)s.indexOf(x=s.slice(0,j),1)+j-l||(r=P(x));
      return r
  };      
  for(o={'':l=i=0};a[i+l]||a[i=0,++l];)
    if(P(p=a.slice(i++,i+l)))
      o[p]=0;
  return[a for(a in o)]
}
edc65
quelle