Entrada

Una cadena alfanumérica s.

Salida

La cadena más corta que aparece exactamente una vez como una subcadena (contigua) s. Los sucesos superpuestos se cuentan como distintos. Si hay varios candidatos de la misma longitud, debe mostrarlos todos en el orden de aparición. En este desafío, la cadena vacía ocurre n + 1veces en una cadena de longitud n.

Ejemplo

Considera la cuerda

"asdfasdfd"

La cadena vacía aparece 10 veces en ella, por lo que no es un candidato para una ocurrencia única. Cada una de las letras "a", "s", "d", y "f"tiene lugar al menos dos veces, así que no son candidatos tampoco. Las subcadenas "fa"y "fd"aparecen solo una vez y en este orden, mientras que todas las demás subcadenas de longitud 2 aparecen dos veces. Por lo tanto, la salida correcta es

["fa","fd"]

Reglas

Ambas funciones y programas completos están permitidos, y las lagunas estándar no. El formato exacto de la salida es flexible, dentro de lo razonable. En particular, no se permite producir ningún resultado para la cadena vacía, pero arrojar un error no. El conteo de bytes más bajo gana.

Casos de prueba

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

Tabla de clasificación

Aquí está la tabla de clasificación por idioma que prometí.

Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

&zhfTmf!/>zhxzYYm<>zkdUzUz

Pruébalo aquí.

Tenga en cuenta que debido a un error en el compilador en línea, el caso de cadena vacía solo funciona correctamente en la versión de línea de comandos, que se puede encontrar aquí.

También puede curar el error dando una nueva línea como entrada para el compilador en línea.

Explicación:

                                   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 bytes

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)

Busca cadenas de modo que la primera aparición desde la izquierda sea la misma que la primera desde la derecha. El +1en el rangees para acomodar el caso de cadena vacía.

Ahora bien, si sólo se tenía una pitón .count()que contó con la superposición de partidos, a continuación, esto habría sido una feria poco más corto.

Mathematica, 95 94 79 bytes

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

StringCasesme proporciona todas las subcadenas posibles, Tallyy Casesfiltra las que aparecen más de una vez y MinimalByencuentra las que son más cortas.

GolfScript, 44 bytes

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

Toma de entrada como una cadena en la entrada estándar y las salidas en una sintaxis de doble matriz: por ejemplo [["b"] ["c"]].Demostración en línea

Disección

: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

Esto se organiza de modo que no se requiera un caso especial para la cadena vacía (que he incluido como caso de prueba en la demostración en línea vinculada anteriormente).

CJam, 52 43 40 bytes

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

La entrada es la cadena sin comillas

Explicacion :

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

Ejemplo:

asdfdfasddfdfaddsasadsasadsddsddfdsasdf

Salida

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

Pruébalo en línea aquí

Scala, 120 bytes

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

Comencé con 140, que al menos ya cabe en 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

Edite la búsqueda en lugar de indexOf, ya que la cadena de entrada es alfanumérica. Gracias @IsmaelMiguel

Función recursiva, buscando subcadenas que comienzan con longitud 1 y suben.

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]

Desengañado y explicado

 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
 }

Prueba en la consola FireFox / FireBug

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

Salida

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

Java, 168 176 233

Aquí hay un ejemplo de bucle anidado bastante básico.

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

O un poco más legible:

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)

Para usarlo:

f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"

Lo que da:

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

Por cierto. Odio la última línea de mi código (repetición de h y). ¿Alguien sugiere deshacerse de él?

J, 61 58 44 42 40 38 37 bytes

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

Aquí hay una versión dividida en los componentes individuales de la solución:

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

• x #/. ycalcula para cada elemento distinto con xqué frecuencia ocurre en y. Si usamos esto como y #/. y, obtenemos el para cada elemento distinto en ysu recuento. Por ejemplo, a #/. apara a =. 1 2 2 3 4 4rendimientos 1 2 1 2.
• 1 = ycomprueba a qué elementos de yson iguales 1. Por ejemplo, 1 = a #/. arendimientos 1 0 1 0.
• u~Es el reflejo de un verbo monádico u. Esto es, u~ yes lo mismo que y u y. Por lo tanto, #/.~ yes lo mismo que #/.~ y. Cuando se aplica a un verbo diádico, u~es el pasivo de u. Es decir, x u~ yes lo mismo que y u x. Estos se utilizan en muchos otros lugares que no menciono explícitamente.
• ~. yes la protuberancia de yun vector con duplicados eliminados. Por ejemplo, ~. arendimientos 1 2 3 4.
• x # y( copia ) selecciona de ylos elementos en los índices donde xcontiene a 1.
• Por lo tanto, (1 = y #/. y) # (~. y)crea un vector de aquellos elementos de los ycuales aparecen solo una vez. En notación tácita, este verbo se escribe como ~. #~ 1 = #/.~; llamemos a esta fraseunqs para el resto de la explicación.

• x ]\ ycrea una xpor 1 + y - xmatriz de todos los infijos del vector yde longitud x. Por ejemplo, 3 ]\ 'asdfasdfdrendimientos

  asd
  sdf
  dfa
  fas
  asd
  sdf
  dfd
  

• # yes el recuento de y, es decir, el número de elementos en y.

• u\ yse aplica ua cada prefijo de y. Por cierto, #\ ycrea un vector de enteros desde 1hasta#y .
• < y pone y en una caja. Esto es necesario porque las matrices no pueden ser desiguales y calculamos una matriz de sufijos de diferentes longitudes; una matriz en caja cuenta como un escalar.

• Por lo tanto, (i. # y) <@:unqs@(]\) ygenera un vector de #ymatrices en caja de la longitud k (para todos los infijos de 0 ≤ k < #y) de y que ocurren exactamente una vez. La forma tácita de este verbo es i.@# <@unqs@(]\) ]o i.@# <@(~. #~ 1 = #/.~)@(]\) ]si no usamos el unqsnombre. Llamemos a esta frase allsbsqpara el resto de esta explicación. Por ejemplo, allsbsq 'asdfasdfd'produce:

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

• (#@> y) # ytoma del vector de matrices en caja ylas que no están vacías.

• {. y toma el primer elemento del vector y .
• > y quita la caja de y .
• Por lo tanto, > {. (#@> y) # yproduce la primera matriz no vacía sin caja del vector de matrices en caja y. Esta frase esta escrita>@{.@(#~ #@>) en notación tácita.

• Finalmente, [: >@{.@(#~ #@>) allsbsqensambla la frase anterior con allsbsqpara crear una solución al problema que tenemos. Aquí está la frase completa con espacios:

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

Haskell, 135 bytes

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 (expresión regular de Java en la implementación de Oracle), 124

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

Probado en Groovy 2.4 + Oracle JRE 1.7. La expresión regular debería funcionar para Java 6 a Java 8, ya que el error que permite que funcione el código anterior no está solucionado. No estoy seguro de la versión anterior, ya que hay un error retrospectivo en Java 5 que se corrigió en Java 6.

La expresión regular encuentra la cadena más corta que no tiene una subcadena duplicada en otro lugar, en cada posición de la cadena de entrada. El código externo se encarga del filtrado.

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

• Como las cuerdas pueden superponerse, rodeo todo el asunto con anticipación (?=...).
• (.*?) búsquedas desde la subcadena más corta
• (?=(.*)) captura el resto de la cadena para marcar la posición actual.
• (?<=^(?!.*\1(?!\2$)).*)es una emulación de retrospectiva de longitud variable, que aprovecha el error de implementación que permite (?<=.*)pasar la verificación de longitud.

• (?!.*\1(?!\2$))simplemente verifica que no puedas encontrar la misma subcadena en otro lugar. los(?!\2$) rechaza la posición original donde se empareja la subcadena.

  El límite de la construcción de búsqueda externa no se aplica a la construcción de búsqueda anidada. Por lo tanto, la vista anticipada negativa anidada (?!.*\1(?!\2$))realmente comprueba la cadena completa, no solo hasta el límite derecho de la vista posterior.

Rebol, 136 bytes

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

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

Ejemplo de uso:

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

NÓTESE BIEN. Supongo que el corazón del código es cómo funciona la findpieza. Esperemos que esto ayude a explicar ...

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

sᶠ≡ᵍ~gˢlᵍt

Pruébalo en línea!

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.

Aunque ᵍnaturalmente no se ordena por el valor por el que agrupa, en su lugar ordena los grupos por la primera aparición de cada valor, las primeras ocurrencias de cada longitud están en orden decreciente. No estoy 100% seguro de que el filtrado de singularidad no pueda estropear esto, pero aún no he encontrado un caso de prueba que falle.

05AB1E , 10 bytes

Œʒ¢}é.γg}н

No genera nada para una cadena vacía.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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

Esto aprovecha que 05AB1E solo tiene 1un valor tan verdadero y todo lo demás como falsey. Siempre se garantiza que la subcadena única más corta se produce exactamente una vez para todas las cadenas de entrada posibles. (Para una cadena de entrada que contiene solo los mismos caracteres (es decir aaaaa), las cadenas de entrada en sí como subcadena ocurren solo una vez, por lo que el resultado es ["aaaaa"]. Para una cadena de entrada con patrón repetitivo (es decir "abcabc"), todavía hay subcadenas únicas que solo ocurrir una vez ( ["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]), por lo que esto resultará en ["ca"])

Pitón 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 bytes

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

Pruébalo en línea!

Método antiguo: 114 bytes