Contribution

Une chaîne alphanumérique s.

Sortie

La chaîne la plus courte qui apparaît exactement une fois en tant que sous-chaîne (contiguë) dans s. Les occurrences qui se chevauchent sont comptées comme distinctes. S'il y a plusieurs candidats de la même longueur, vous devez tous les afficher dans l'ordre d'apparition. Dans ce défi, la chaîne vide se produit n + 1fois dans une chaîne de longueur n.

Exemple

Considérez la chaîne

"asdfasdfd"

La chaîne vide y apparaît 10 fois, elle n'est donc pas candidate à une occurrence unique. Chacune des lettres "a", "s", "d"et "f"se produit au moins deux fois, donc ils ne sont pas candidats non plus . Les sous "fa"- chaînes et "fd"n'apparaissent qu'une seule fois et dans cet ordre, tandis que toutes les autres sous-chaînes de longueur 2 se produisent deux fois. Ainsi, la sortie correcte est

["fa","fd"]

Règles

Les fonctions et les programmes complets sont autorisés, mais les failles standard ne le sont pas. Le formatage exact de la sortie est flexible, dans des limites raisonnables. En particulier, la production d'aucune sortie pour la chaîne vide est autorisée, mais le lancement d'une erreur ne l'est pas. Le nombre d'octets le plus bas gagne.

Cas de test

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

Classement

Voici le classement par langue que j'ai promis.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

# 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 octets

&zhfTmf!/>zhxzYYm<>zkdUzUz

Essayez-le ici.

Notez qu'en raison d'un bogue dans le compilateur en ligne, le cas de chaîne vide ne fonctionne correctement que sur la version en ligne de commande, qui peut être trouvée ici.

Vous pouvez également corriger le bogue en donnant une nouvelle ligne comme entrée pour le compilateur en ligne.

Explication:

                                   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 111 96 octets

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)

Recherche des chaînes telles que la première occurrence de gauche est la même que la première occurrence de droite. Le +1dans le rangeest destiné à accueillir le boîtier de chaîne vide.

Maintenant, si seulement Python avait un .count()qui comptait les correspondances qui se chevauchaient , cela aurait été un peu plus court.

Mathematica, 95 94 79 octets

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

StringCasesrécupère toutes les sous-chaînes possibles, filtre Tallyet Casesfiltre celles qui apparaissent plus d'une fois et MinimalBytrouve celles qui sont les plus courtes.

GolfScript, 44 octets

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

Prend les entrées sous forme de chaîne sur stdin et les sorties dans une syntaxe à double tableau: par exemple [["b"] ["c"]]. Démo en ligne

Dissection

: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

Ceci est organisé de telle sorte qu'aucun cas spécial n'est requis pour la chaîne vide (que j'ai inclus comme cas de test dans la démo en ligne liée ci-dessus).

CJam, 52 43 40 octets

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

L'entrée est la chaîne sans guillemets

Explication :

]]                                       "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";

Exemple:

asdfdfasddfdfaddsasadsasadsddsddfdsasdf

Sortie

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

Essayez-le en ligne ici

Scala, 120 octets

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

J'ai commencé avec 140 qui s'inscrit au moins déjà dans un tweet.

(                                        // 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

Modifiez la recherche au lieu de indexOf, car la chaîne d'entrée est alphanumérique. Merci @IsmaelMiguel

Fonction récursive, recherche de sous-chaînes commençant par la longueur 1 et remontant.

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]

Non golfé et expliqué

 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
 }

Test dans la console FireFox / FireBug

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

Sortie

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

Java, 168 176 233

Voici un exemple de boucle imbriquée assez basique.

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++;}}

Ou un peu plus lisible:

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 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)

Pour l'utiliser:

f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"

Qui donne:

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

Btw. Je déteste la dernière ligne de mon code (répétition de h y). Quelqu'un suggère de s'en débarrasser?

J, 61 58 44 42 40 38 37 octets

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

Voici une version divisée en composants individuels de la solution:

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

• x #/. ycalcule pour chaque élément distinct xla fréquence à laquelle se produit dans y. Si nous utilisons cela comme y #/. y, nous obtenons le pour chaque élément distinct dansy son décompte. Par exemple, a #/. apour les a =. 1 2 2 3 4 4rendements 1 2 1 2.
• 1 = y vérifie quels éléments de y sont égaux 1. Par exemple, les 1 = a #/. arendements1 0 1 0 .
• u~est le réflexe d'un verbe monadique u. C'est, u~ yest le même que y u y. Ainsi,#/.~ y est le même que #/.~ y. Appliqué à un verbe dyadique, u~est le passif de u. Autrement dit, x u~ yest le même que y u x. Ceux-ci sont utilisés dans de nombreux autres endroits que je ne mentionne pas explicitement.
• ~. yest le nœud de y, un vecteur dont les doublons ont été supprimés. Par exemple, les ~. arendements 1 2 3 4.
• x # y( copier ) sélectionne parmi yles éléments aux indices où xcontient a 1.
• Ainsi, (1 = y #/. y) # (~. y) crée un vecteur dont les éléments yn'apparaissent qu'une seule fois. En notation tacite, ce verbe s'écrit ~. #~ 1 = #/.~; appelons cette phrase unqspour le reste de l'explication.

• x ]\ ycrée un tableau xpar 1 + y - xde tous les infixes du vecteur yde longueurx . Par exemple,3 ]\ 'asdfasdfd rendements

  asd
  sdf
  dfa
  fas
  asd
  sdf
  dfd
  

• # y est le décompte de y, qui est, le nombre d'éléments y.

• u\ ys'applique uà chaque préfixe de y. Incidemment,#\ y crée un vecteur d'entiers de 1à#y .
• < y met y dans une boîte. Cela est nécessaire car les tableaux ne peuvent pas être irréguliers et nous calculons un tableau de suffixes de différentes longueurs; un tableau encadré compte comme un scalaire.

• Ainsi, (i. # y) <@:unqs@(]\) ygénère un vecteur de #ytableaux encadrés de la longueur k (pour tous les 0 ≤ k < #y) infixes de y qui se produisent exactement une fois. La forme tacite de ce verbe est i.@# <@unqs@(]\) ]ou i.@# <@(~. #~ 1 = #/.~)@(]\) ]si nous n'utilisons pas le unqsnom. Appelons cette phrase allsbsqpour le reste de cette explication. Par exemple, allsbsq 'asdfasdfd'donne:

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

• (#@> y) # yprend du vecteur de tableaux en boîte yceux qui ne sont pas vides.

• {. yprend le premier élément du vecteur y.
• > ysupprime la boîte de y.
• Ainsi, > {. (#@> y) # ydonne le premier tableau non vide non mis en boîte à partir du vecteur de tableaux mis en boîte y. Cette phrase est écrite>@{.@(#~ #@>) en notation tacite.

• Enfin, [: >@{.@(#~ #@>) allsbsqassemble la phrase précédente avec allsbsqpour créer une solution au problème que nous avons. Voici la phrase complète avec des espaces:

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

Haskell, 135 octets

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 sur implémentation Oracle), 124

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

Testé sur Groovy 2.4 + Oracle JRE 1.7. L'expression régulière devrait fonctionner pour Java 6 à Java 8, car le bogue qui permet au code ci-dessus de fonctionner n'est pas corrigé. Pas sûr pour la version précédente, car il y a un bogue dans Java 5 qui a été corrigé dans Java 6.

L'expression régulière trouve la chaîne la plus courte qui n'a pas de sous-chaîne en double ailleurs, à chaque position de la chaîne d'entrée. Le code extérieur prend en charge le filtrage.

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

• Étant donné que les cordes peuvent se chevaucher, j'entoure le tout dans la perspective (?=...).
• (.*?) recherche à partir de la sous-chaîne la plus courte
• (?=(.*)) capture le reste de la chaîne pour marquer la position actuelle.
• (?<=^(?!.*\1(?!\2$)).*) est une émulation de look-back de longueur variable, qui tire parti du bogue d'implémentation qui permet (?<=.*) de passer le contrôle de longueur.

• (?!.*\1(?!\2$))vérifie simplement que vous ne pouvez pas trouver la même sous-chaîne ailleurs. Le (?!\2$)rejette la position d'origine où la sous-chaîne est mise en correspondance.

  La limite de la construction de contour externe ne s'applique pas à la construction de contour imbriquée. Par conséquent, l'anticipation négative imbriquée (?!.*\1(?!\2$))vérifie en fait la chaîne entière, et pas seulement jusqu'à la limite droite de l'observation.

Rebol, 136 octets

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]]]

Non golfé:

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]
    ]
]

Exemple d'utilisation:

>> 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. Je suppose que le cœur du code est le fonctionnement de la findpièce. J'espère que cela vous aidera à expliquer ...

>> 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 octets

sᶠ≡ᵍ~gˢlᵍt

Essayez-le en ligne!

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.

Bien que ᵍne trie pas naturellement en fonction de la valeur par laquelle il est groupé, au lieu de classer les groupes par la première occurrence de chaque valeur, les premières occurrences de chaque longueur sont décroissantes. Je ne suis pas sûr à 100% que le filtrage d'unicité ne puisse pas gâcher cela, mais je n'ai pas encore trouvé de cas de test qui échoue encore.

05AB1E , 10 octets

Œʒ¢}é.γg}н

N'affiche rien pour une chaîne vide.

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

Π          # 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)

Cela profite du fait que 05AB1E n'a 1que la valeur véridique, et tout le reste comme falsey. La sous-chaîne unique la plus courte est toujours garantie de se produire exactement une fois pour toutes les chaînes d'entrée possibles. (Pour une chaîne d'entrée contenant uniquement les mêmes caractères (c.-à-d. aaaaa), Les chaînes d'entrée elles-mêmes en tant que sous-chaîne ne se produisent qu'une seule fois, donc le résultat est ["aaaaa"]. Pour une chaîne d'entrée avec un motif répétitif (c.-à-d. "abcabc"), Il existe encore des sous-chaînes uniques qui ne se produire une fois ( ["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]), donc cela se traduira par ["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 octets

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

Essayez-le en ligne!

Ancienne méthode: 114 octets