Wkład

Ciąg alfanumeryczny s.

Wydajność

Najkrótszy ciąg występujący dokładnie raz jako (ciągły) podciąg w s. Nakładające się wystąpienia są liczone jako odrębne. Jeśli jest kilku kandydatów o tej samej długości, musisz wydrukować wszystkie z nich w kolejności występowania. W tym wyzwaniu pusty ciąg występuje n + 1razy w ciągu długości n.

Przykład

Rozważ ciąg

"asdfasdfd"

Pusty ciąg występuje w nim 10 razy, więc nie jest kandydatem na wyjątkowe wystąpienie. Każda z liter "a", "s", "d", i "f"pojawia się co najmniej dwa razy, więc nie są oni kandydatami albo. Podciągów "fa"i "fd"występuje tylko raz, w tej kolejności, a wszystkie inne podrzędnymi długości 2 występują dwukrotnie. Zatem prawidłowe wyjście to

["fa","fd"]

Zasady

Zarówno funkcje, jak i pełne programy są dozwolone, a standardowe luki nie. Dokładne formatowanie danych wyjściowych jest elastyczne w granicach rozsądku. W szczególności niedozwolone jest wytwarzanie danych wyjściowych dla pustego ciągu znaków, ale nie jest zgłaszanie błędu. Wygrywa najniższa liczba bajtów.

Przypadki testowe

"" -> [""]
"abcaa" -> ["b","c"]
"rererere" -> ["ererer"]
"asdfasdfd" -> ["fa","fd"]
"ffffhhhhfffffhhhhhfffhhh" -> ["hffff","fffff","hhhhh","hfffh"]
"asdfdfasddfdfaddsasadsasadsddsddfdsasdf" -> ["fas","fad","add","fds"]

Tabela liderów

Oto obiecana przeze mnie tabela liderów według języków.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

<script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>site = 'meta.codegolf',postID = 5314,isAnswer = true,QUESTION_ID = 45056;jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)<\\/code><\/pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Pyth, 27 26 bajtów

&zhfTmf!/>zhxzYYm<>zkdUzUz

Wypróbuj tutaj.

Zauważ, że z powodu błędu w kompilatorze online pusta wielkość liter działa poprawnie tylko w wersji wiersza poleceń, którą można znaleźć tutaj.

Możesz także wyleczyć błąd, podając nowy wiersz jako dane wejściowe kompilatora online.

Wyjaśnienie:

                                   z = input(), implicit.
&z                                 Prints empty string if input is empty.
  hfT                              Take the first non-empty list from
     m                  Uz         A list of list of substrings of z, divided by length
                m<>zkdUz           with some shorter strings repeated later, to no effect.
      f                            Where the substrings are filtered on
       !/      Y                   There being 0 occurrences of the substring in
         >z                        The slice of z
           hxzY                    from the character after the first character
                                   of the first occurrence of the substring in z
                                   to the end of z.

Python 3, 124 123 111 96 bajtów

f=lambda s,n=1:[x for x in[s[i:i+n]for i in range(len(s)+1)]if s.find(x)==s.rfind(x)]or f(s,n+1)

Szuka ciągów znaków takich, że pierwsze wystąpienie od lewej jest takie samo jak pierwsze wystąpienie od prawej. Opcja „ +1in” rangema uwzględniać pustą wielkość ciągu.

Teraz, jeśli tylko Python miał .count()których liczy się nakładających się mecze, to byłoby w porządku trochę krótszy.

Mathematica, 95 94 79 bajtów

Cases[Tally@StringCases[#,___,Overlaps->All],{s_,1}:>s]~MinimalBy~StringLength&

StringCasesdostaje wszystkie możliwe podciągi Tallyi Casesodfiltrowuje te, które pojawiają się więcej niż jeden raz, i MinimalByznajduje te, które są najkrótsze.

GolfScript, 44 bajty

:S;-1:x{;S,x):x-),{S>x<}%:^1/{^\/,2=},.!}do`

Pobiera dane wejściowe jako ciąg na standardowym wyjściu i wypisuje je w składni z podwójną tablicą: np [["b"] ["c"]]. Demo online

Sekcja

:S;          # Store input in S and pop it
-1:x         # Store -1 in x
{            # do-while loop
  ;          #   Pop x the first time and [] every subsequent time
  S,x):x-),  #   Increment x and build an array [0 1 ... len(S)-x]
  {S>x<}%    #   Map that array to [substr(S,0,x) substr(S,1,x) ...]
  :^         #   Store in ^ (to avoid the token coalescing with the next char)
  1/         #   Split by length 1 to iterate over 1-elt arrays rather than strings
  {^\/,2=},  #   Filter to arrays which occur exactly once as a subarray of ^
  .!         #   Duplicate and test emptiness
}do          # end do-while loop: loop if the filtered array is empty
`            # Stringify for output

Jest to ustawione tak, że nie jest wymagany specjalny przypadek dla pustego ciągu (który umieściłem jako przypadek testowy w demo online, do którego link powyżej).

CJam, 52 43 40 bajtów

]]q:Q,,{)Q,1$-),f{Q><}:R{R\a/,2=},}%{}=p

Dane wejściowe to ciąg bez cudzysłowów

Objaśnienie :

]]                                       "For empty string input case";
  q:Q                                    "Read the input and store in Q";
     ,,                                  "Take length of input and 0 to length array";
       {                          }%     "Map the above array on this code block";
        )Q                               "Increment the number in the current iteration, L";
         Q,1$                            "Take input's length and copy the above number";
             -)                          "Get upper limit of next loop to get substrings";
               ,f{   }                   "Get 0 to above number array and for each";
                  Q><                    "Get the L length substring at Ith index where";
                                         "I loops from 0 to Q, - L + 1";
                      :R                 "Store this list of substring of length L in R";
                        {R\a/,2=},       "Filter to get unique substrings";
                                    {}=  "Get the first non empty substring array";
                                         "This leaves nothing on stack if all are empty";
                                       p "Print the top stack element. At this point, its";
                                         "Either the first non empty substring array or";
                                         "the ]] i.e. [""] which we added initially";

Przykład:

asdfdfasddfdfaddsasadsasadsddsddfdsasdf

Wydajność

["fas" "fad" "add" "fds"]

Wypróbuj online tutaj

Scala, 120 bajtów

readLine.inits.flatMap(_.tails).toList.groupBy(l=>l).filter(x=>x._2.length<2).map(_._1).groupBy(_.length).minBy(_._1)._2

Zacząłem od 140, które przynajmniej już mieszczą się w tweecie.

(                                        // added for comments
 readLine                                // input
.inits.flatMap(_.tails).toList           // get all substrings of that string
.groupBy(l=>l).filter(x=>x._2.length<2)  // remove substrings that occur more than once
.map(_._1).groupBy(_.length)             // take the substring and group by length
.minBy(_._1)._2                          // take the list of shortest substrings
)

JavaScript (ES6), 109 110

Edytuj wyszukiwanie zamiast indexOf, ponieważ ciąg wejściowy jest alfanumeryczny. Dzięki @IsmaelMiguel

Funkcja rekurencyjna, szukająca podciągów zaczynających się od długości 1 i rosnących.

F=(s,n=1,r)=>
s?[...s].map((a,i)=>~s.indexOf(a=s.substr(i,n),s.search(a)+1)?r:r=[...r||[],a])&&r||F(s,n+1):[s]

Nie golfił i wyjaśnił

 F = function(s, n=1) { // start with length 1
   var i, a, p, r;
   if (s == "") // special case for empty input string
     return [s];
   for (i = 0; i < s.length; i++) 
   // for each possibile substring of length n
   // (should stop at s.length-n+1 but going beyond is harmless)
   // Golfed: "[...s].map((a,i)" ... using i, a is overwrittem
   {
     a = s.substr(i, n); // substring at position i
     p = s.search(a); // p is the first position of substring found, can be i or less
     p = s.indexOf(a, p + 1) // p is now the position of a second instance of substring, or -1 if not found
     if (~p) // ~p is 0 if p is -1
     {
       ; // found more than once, do nothing
     }
     else
     {
       r = r || []; // if r is undefined, then it becomes an empty array
       r.push(a); // save substring 
       // Golfed: "r=[...r||[],a]"
     }
   }
   if (r) // if found some substring, saved in r
   {
     return r;
   }
   return F(s, n+1) // recursive retry for a bigger length
 }

Testuj w konsoli FireFox / FireBug

;["", "abcaa", "rererere", "asdfasdfd", "ffffhhhhfffffhhhhhfffhhh", 
 "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"]
.forEach(x=>console.log(x,F(x)))

Wydajność

 [""]
abcaa ["b", "c"]
rererere ["ererer"]
asdfasdfd ["fa", "fd"]
ffffhhhhfffffhhhhhfffhhh ["hffff", "fffff", "hhhhh", "hfffh"]
asdfdfasddfdfaddsasadsasadsddsddfdsasdf ["fas", "fad", "add", "fds"]

Java, 168 176 233

Oto całkiem prosty przykład zagnieżdżonej pętli.

void n(String s){for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)for(String b;i<=t-l;)if(s.indexOf(b=s.substring(i,i+++l),s.indexOf(b)+1)<0){System.out.println(b);q++;}}

Lub nieco bardziej czytelny:

void t(String s){
    for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)
        for(String b;i<=t-l;)
            if(s.indexOf(b=s.substring(i,i++ +l),s.indexOf(b)+1)<0){
                System.out.println(b);
                q++;
            }
}

Haskell, 169 162 155 153 151 138 120 115

import Data.List
l=length
q k=filter$(==)k.l
p y=q(minimum.map l$y)$y
f x=p$concat$q 1$group$sort$(tails x>>=inits)

Aby go użyć:

f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"

Co daje:

["add","fad","fas","fds"]

Btw. Nienawidzę ostatniego wiersza mojego kodu (powtórzenie h y). Czy ktoś chce się go pozbyć?

J, 61 58 44 42 40 38 37 bajtów

[:>@{.@(#~#@>)#\<@(~.#~1=#/.~)@(]\)]

Oto wersja podzielona na poszczególne składniki rozwiązania:

unqs =. ~. #~ 1 = #/.~               NB. uniques; items that appear exactly once
allsbsq =. #\ <@unqs@(]\) ]        NB. all unique subsequences
shrtsbsq =. [: >@{.@(#~ #@>) allsbsq NB. shortest unique subsequence

• x #/. yoblicza dla każdego odrębnego elementu xczęstość występowania w y. Jeśli użyjemy tego jako y #/. y, otrzymamy dla każdego odrębnego elementu yjego liczbę. Na przykład a #/. adla a =. 1 2 2 3 4 4plonów 1 2 1 2.
• 1 = ysprawdza, które elementy ysą równe 1. Na przykład 1 = a #/. adaje 1 0 1 0.
• u~jest zwrotna z monadycznej czasownika u. To jest u~ yto samo co y u y. Zatem #/.~ yjest taki sam jak #/.~ y. Przy stosowaniu na diadycznej czasownik u~jest bierny w u. Oznacza to, że x u~ yjest taki sam jak y u x. Są one używane w kilku innych miejscach, o których wyraźnie nie wspominam.
• ~. yJest to zgrubienie od ywektora, kopiami usunięte. Na przykład ~. adaje 1 2 3 4.
• x # y( kopiuj ) wybiera ypozycje z indeksów, w których xzawiera 1.
• W ten sposób (1 = y #/. y) # (~. y)tworzy wektor tych elementów, yktóre pojawiają się tylko raz. W milczącej notacji czasownik ten zapisano jako ~. #~ 1 = #/.~; nazwijmy to wyrażenie unqsdo końca wyjaśnienia.

• x ]\ ystwarza obraz xprzez 1 + y - xtablicę wszystkich wrostków wektora ydługości x. Na przykład 3 ]\ 'asdfasdfddaje

  asd
  sdf
  dfa
  fas
  asd
  sdf
  dfd
  

• # yjest tally of y, czyli liczba elementów y.

• u\ yodnosi usię do każdego prefiksu z y. Nawiasem mówiąc, #\ ytworzy wektor liczb całkowitych od 1do #y.
• < ywkłada ydo pudełka. Jest to konieczne, ponieważ tablice nie mogą być obdarte i obliczamy tablicę sufiksów o różnych długościach; tablica w pudełku liczy się jako skalar.

• W ten sposób (i. # y) <@:unqs@(]\) ygeneruje wektor #ytablic w ramkach o długości k (dla wszystkich 0 ≤ k < #y) przedrostków y, które występują dokładnie raz. Milcząca forma tego czasownika to i.@# <@unqs@(]\) ]lub i.@# <@(~. #~ 1 = #/.~)@(]\) ]jeśli nie używamy unqsnazwy. Nazwijmy to wyrażenie allsbsqresztą tego wyjaśnienia. Na przykład allsbsq 'asdfasdfd'daje:

  ┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┐
  ││ │fa│dfa│sdfa│asdfa│asdfas│asdfasd│asdfasdf│
  ││ │fd│fas│dfas│sdfas│sdfasd│sdfasdf│sdfasdfd│
  ││ │  │dfd│fasd│dfasd│dfasdf│dfasdfd│        │
  ││ │  │   │sdfd│fasdf│fasdfd│       │        │
  ││ │  │   │    │asdfd│      │       │        │
  └┴─┴──┴───┴────┴─────┴──────┴───────┴────────┘
  

• (#@> y) # ypobiera z wektora tablic pudełkowych yte, które nie są puste.

• {. ybierze pierwszy element wektora y.
• > yusuwa pudełko z y.
• W ten sposób > {. (#@> y) # yuzyskuje się rozpakowaną pierwszą niepustą tablicę z wektora tablic pudełkowych y. To wyrażenie jest zapisane >@{.@(#~ #@>)w sposób milczący.

• Na koniec [: >@{.@(#~ #@>) allsbsqskłada się z poprzedniej frazy, allsbsqaby stworzyć rozwiązanie naszego problemu. Oto pełna fraza ze spacjami:

  [: >@{.@(#~ #@>) i.@# <@(~. #~ 1 = #/.~)@(]\) ]
  

Haskell, 135 bajtów

import Data.List
f ""=[""]
f g=map(snd)$head$groupBy(\a b->fst a==fst b)$sort[(length y,y)|[y]<-group$sort[x|x@(_:_)<-tails g>>=inits]]

PHP, 171 152 134 125

function f($s){while(!$a&&++$i<strlen($s))for($j=0;$b=substr($s,$j++,$i);)strpos($s,$b)==strrpos($s,$b)&&($a[]=$b);return$a;}

http://3v4l.org/RaWTN

Groovy (regex Java na implementacji Oracle), 124

c={m=it=~/(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))/;o=m.collect({it[1]});o.findAll({it.size()==o.min({it.size()}).size()});}

Testowane na Groovy 2.4 + Oracle JRE 1.7. Wyrażenie regularne powinno działać dla Java 6 do Java 8, ponieważ błąd, który pozwala na działanie powyższego kodu, nie został naprawiony. Nie jestem pewien co do poprzedniej wersji, ponieważ w Javie 5 występuje błąd, który został naprawiony w Javie 6.

Wyrażenie regularne znajduje najkrótszy ciąg, który nie ma zduplikowanego podłańcucha w innym miejscu, w każdej pozycji ciągu wejściowego. Kod na zewnątrz zajmuje się filtrowaniem.

(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))

• Ponieważ struny mogą się nakładać, otaczam to wszystko z wyprzedzeniem (?=...).
• (.*?) wyszukuje od najkrótszego podłańcucha
• (?=(.*)) przechwytuje resztę ciągu, aby zaznaczyć bieżącą pozycję.
• (?<=^(?!.*\1(?!\2$)).*)to emulacja z tyłu o zmiennej długości, która wykorzystuje błąd implementacji, który pozwala (?<=.*)przejść kontrolę długości.

• (?!.*\1(?!\2$))po prostu sprawdza, czy nie można znaleźć tego samego podciągu w innym miejscu. (?!\2$)Odrzuca pierwotnego położenia, gdzie podciąg jest dopasowana.

  Limit zewnętrznej konstrukcji rozglądającej się nie dotyczy zagnieżdżonej konstrukcji rozglądającej się. Dlatego zagnieżdżone negatywne spojrzenie w przyszłość (?!.*\1(?!\2$))sprawdza cały ciąg, a nie tylko do prawej granicy z tyłu.

Rebol, 136 bajtów

f: func[s][repeat n length? b: copy s[unless empty? x: collect[forall s[unless find next find b t: copy/part s n t[keep t]]][return x]]]

Nie golfowany:

f: func [s] [
    repeat n length? b: copy s [
        unless empty? x: collect [
            forall s [
                unless find next find b t: copy/part s n t [keep t]
            ]
        ][return x]
    ]
]

Przykład użycia:

>> f ""       
== none

>> f "abcaa"
== ["b" "c"]

>> f "rererere"
== ["ererer"]

>> f "asdfasdfd"
== ["fa" "fd"]

>> f "ffffhhhhfffffhhhhhfffhhh"
== ["hffff" "fffff" "hhhhh" "hfffh"]

>> f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"
== ["fas" "fad" "add" "fds"]

NB. Przypuszczam, że sednem kodu jest sposób działania tej findczęści. Mam nadzieję, że pomoże to wyjaśnić ...

>> find "asdfasdfd" "df"
== "dfasdfd"

>> next find "asdfasdfd" "df"
== "fasdfd"

>> find next find "asdfasdfd" "df" "df"
== "dfd"

>> ;; so above shows that "df" is present more than once - so not unique
>> ;; whereas below returns NONE because "fa" found only once - ie. bingo!

>> find next find "asdfasdfd" "fa" "fa"
== none

Haskell, 119

f s=[r|n<-[1..length s],l<-[map(take n)$take(length s-n+1)$iterate(drop 1)s],r<-[[j|j<-l,[j]==[r|r<-l,r==j]]],r/=[]]!!0

Brachylog , 10 bajtów

sᶠ≡ᵍ~gˢlᵍt

Wypróbuj online!

sᶠ            The list of every substring of the input
  ≡ᵍ          grouped by identity,
    ~gˢ       with length-1 groups converted to their elements and other groups discarded,
       lᵍ     and grouped by their length,
         t    has the output as its last group.

Chociaż w ᵍnaturalny sposób nie sortuje według wartości, którą grupuje, zamiast tego porządkuje grupy według pierwszego wystąpienia każdej wartości, pierwsze wystąpienia każdej długości są malejące. Nie jestem w 100% pewien, że filtrowanie unikatowości nie może tego zepsuć, ale nie wpadłem na przypadek testowy, który zawodzi.

05AB1E , 10 bajtów

Œʒ¢}é.γg}н

Nie wyświetla niczego dla pustego ciągu.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Π          # Get all substrings of the (implicit) input-String
 ʒ          # Filter it by:
  ¢         #  Count how many times the current substring occurs in the (implicit) input-String
            #  (only 1 is truthy in 05AB1E, so the filter will leave unique substrings)
   }é       # After the filter: sort the remaining substrings by length
     .γg}   # Then group them by length as well
         н  # And only leave the first group containing the shortest substrings
            # (which is output implicitly as result)

Wykorzystuje to fakt, że 05AB1E ma tylko 1tak prawdziwą wartość, a wszystko inne jako falsey. Gwarantujemy, że najkrótsze unikalne podciąg wystąpi dokładnie raz dla wszystkich możliwych ciągów wejściowych. (W przypadku łańcucha wejściowego zawierającego tylko te same znaki (tj. aaaaa) Łańcuchy wejściowe same jako podłańcuch występują tylko raz, więc wynik jest taki ["aaaaa"]. W przypadku łańcucha wejściowego z powtarzalnym wzorcem (tj. "abcabc") Nadal istnieją unikatowe podciągi, które tylko występuje raz ( ["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]), więc spowoduje to ["ca"].)

Python 2, 150

import re
a=input()
r=range
l=len(a)
d=0
for i in r(l):
 if d:break
 for j in r(l-i):
  k=a[j:i+j+1]
  if len(re.findall("(?="+k+")",a))<2:d=1;print k

Perl 5 -a , 114 87 bajtów

map{//;(grep$' eq$_,@q)-1||($l||=y///c)-y///c||say}@q=map{"@F"=~/(?=(.{$_}))/g}1..y///c

Wypróbuj online!

Stara metoda: 114 bajtów