À partir d'une chaîne en tant qu'entrée, trouvez la plus longue sous-chaîne contiguë ne comportant aucun caractère deux fois ou plus. S'il existe plusieurs sous-chaînes de ce type, vous pouvez générer l'un ou l'autre. Vous pouvez supposer que l’entrée se situe sur la plage imprimable ASCII si vous le souhaitez.

Notation

Les réponses seront d'abord classées en fonction de la longueur de leur plus longue sous-chaîne non répétée, puis de leur longueur totale. Des scores plus bas seront meilleurs pour les deux critères. En fonction de la langue, cela ressemblera probablement à un défi de code-golf avec une restriction de source.

Banalité

Obtenir des notes de 1, x (lenguage) ou 2, x (Brain-flak et autres tarpits) est assez facile dans certaines langues , mais il existe d’autres langues dans lesquelles réduire au minimum la plus longue sous-chaîne non répétitive est un défi. J'ai eu beaucoup de plaisir à obtenir un score de 2 à Haskell, je vous encourage donc à rechercher des langues où cette tâche est amusante.

Cas de test

"Good morning, Green orb!" -> "ing, Gre"
"fffffffffff" -> "f"
"oiiiiioiiii" -> "io", "oi"
"1234567890"  -> "1234567890"
"11122324455" -> "324"

Soumission de scoring

Vous pouvez évaluer vos programmes en utilisant l'extrait suivant:

input.addEventListener("input", change);

// note: intentionally verbose :)
function isUnique(str) {
  var maxCount = 0;
  var counts = {};
  for(var i = 0; i < str.length; i++) {
    var c = str.charAt(i);
    counts[c] |= 0;
    counts[c]++;
    if(maxCount < counts[c]) {
      maxCount = counts[c];
    }
  }
  return maxCount <= 1;
}

function maximizeSubstring(str, pred, cost) {
  var mostExpensive = -1;
  // iterate over substrings
  function iterate(start, end) {
    var slice = str.slice(start, end);
    if(pred(slice)) {
      var profit = cost(slice);
      if(profit > mostExpensive) {
        mostExpensive = profit;
      }
    }
    end++;
    if(start >= str.length) {
      return;
    }
    else if(end > str.length) {
      start++;
      iterate(start, start);
    }
    else {
      iterate(start, end);
    }
  }
  iterate(0, 0);
  return mostExpensive;
}

function size(x) {
  return x.length;
}

function longestNonRepeatingSize(str) {
  return maximizeSubstring(str, isUnique, size);
}

function change() {
  var code = input.value;
  output.value = "Your score is: " + longestNonRepeatingSize(code);
}

change();

* {
  font-family: monospace;
}

Input code here:
<br>
<textarea id="input"></textarea>
<br>
<textarea id="output"></textarea>

C, score 2,  747   720  662 octets

L  [  1  <<  7  ]  ,  *  q  ,  *  r  ,  l  ,  d  ,  i  ,  c  ,  j  ,  s  ,  t  ,  k  =  1  <<  7  ;  h  (  )  {  q  =  s  +  i  +  j  ++  ;  *  q  %  k  &&  !  L  [  *  q  %  k  ]  ++  &&  h  (  ++  c  )  ;  }  g  (  )  {  q  =  s  +  i  ;  *  q  %  k  ?  z  (  k  )  ,  h  (  j  =  c  =  0  )  ,  c  >  d  &&  (  d  =  c  )  &&  (  l  =  i  )  ,  g  (  ++  i  )  :  0  ;  }  f  (  S  ,  T  )  {  s  =  S  ;  l  =  i  =  d  =  0  ;  g  (  t  =  T  )  ;  p  (  i  =  0  )  ;  }  p  (  )  {  q  =  s  +  l  +  i  ;  r  =  t  +  i  ;  i  ++  <  d  ?  p  (  *  r  =  *  q  )  :  (  *  r  =  0  )  ;  }  z  (  i  )  {  L  [  --  i  ]  =  0  ;  i  &&  z  (  i  )  ;  }

Fonctionne au moins sur MinGW 32 bits (avec optimisations désactivées). N'utilise pas un mot clé unique.

Fonctionne apparemment sur TIO avec gcc et clang aussi: essayez-le en ligne! (Merci @Dennis!)

Appeler avec:

int main()
{
    char str[1024];

    f("Good morning, Green orb!", str);
    puts(str);

    f("fffffffffff", str);
    puts(str);

    f("oiiiiioiiii", str);
    puts(str);

    f("1234567890", str);
    puts(str);

    f("L  [  1  <<  7  ]  ,  *  q  ,  *  r  ,  l  ,  d  ,  i  ,  c  ,  j  ,  s  ,  t  ,  k  =  1  <<  7  ;  h  (  )  {  q  =  s  +  i  +  j  ++  ;  *  q  %  k  &&  !  L  [  *  q  %  k  ]  ++  &&  h  (  ++  c  )  ;  }  g  (  )  {  q  =  s  +  i  ;  *  q  %  k  ?  z  (  k  )  ,  h  (  j  =  c  =  0  )  ,  c  >  d  &&  (  d  =  c  )  &&  (  l  =  i  )  ,  g  (  ++  i  )  :  0  ;  }  f  (  S  ,  T  )  {  s  =  S  ;  l  =  i  =  d  =  0  ;  g  (  t  =  T  )  ;  p  (  i  =  0  )  ;  }  p  (  )  {  q  =  s  +  l  +  i  ;  r  =  t  +  i  ;  i  ++  <  d  ?  p  (  *  r  =  *  q  )  :  (  *  r  =  0  )  ;  }  z  (  i  )  {  L  [  --  i  ]  =  0  ;  i  &&  z  (  i  )  ;  }");
    puts(str);
}

Sortie:

Le code avec un format légèrement plus lisible:

L[1<<7],
*q, *r, l, d, i, c, j, s, t, k=1<<7;

h()
{
    q = s+i+j++;
    *q%k && !L[*q%k]++ && h(++c);
}

g()
{
    q = s+i;
    *q%k ? z(k), h(j=c=0), c>d && (d=c) && (l=i), g(++i) : 0;
}

f(S, T)
{
    s = S;
    l = i = d = 0;
    g(t=T);
    p(i=0);
}

p()
{
    q = s+l+i;
    r = t+i;
    i++<d ? p(*r=*q) : (*r=0);
}

z(i)
{
    L[--i] = 0;
    i && z(i);
}

Et cela peut être utilisé pour générer un espacement correct pour arriver au formatage avec le score 2: Essayez-le en ligne!

C, score 3, 309 octets

i
,
j
,
l
,
c
,
d
;
f
(
\
c\
\
h\
\
a\
\
r
*
s
)
{
\
f\
\
o\
\
r
\
(
i
=
l
=
d
=
0
;
s
[
i
]
;
c
>
d
&&
(
d
=
c
)
&&
(
l
=
i
)
,
++
i
)
\
f\
\
o\
\
r
(
\
c\
\
h\
\
a\
\
r

L
[
\
1\
\
2\
\
8
\
]
=
{
j
=
c
=
0
}
;
s
[
i
+
j
]
&&
!
L
[
s
[
i
+
j
++
]
]
++
;
++
c
)
;
\
w\
\
r\
\
i\
\
t\
\
e
(
1
,
s
+
l
,
d
)
;
}

Essayez-le en ligne!

Haskell , score 2, 492 ... 307 224 212 209 207 octets

((yy:yyy))??ss|ss==yy  =  ""  |  yy==yy=yy:yyy??ss
ss??sss=ss
ss""=""

ss((ff:fff))  =  ff  :  ss  fff??ff
ff""=""

ff((xxx:xx))  =  ss((xxx:xx))##ff  xx
xx##xxx  |  ((((xx>>xx))<))  $  xxx>>xx=xxx|xx==xx=xx

Essayez-le en ligne!

Golfé littéralement des centaines d'octets grâce à WW et Ørjan Johansen !

Explication

La fonction (??)prend un caractère cet une chaîne set renvoie le préfixe le plus long de scelui que ne contient pas c. Non golfé et non optimisé pour le score:

c ?? (y:s)  
    | c==y = ""
    | True = y : c ?? s
c ?? s = s

La fonction ssutilise (??)pour trouver le préfixe le plus long des caractères uniques d'une chaîne donnée:

ss (x:r) = x : (x ?? ss r)
ss "" = ""

(##)est une fonction qui prend deux chaînes et renvoie la plus longue. La comparaison de longueur fonctionne en répétant la chaîne xaussi souvent que xlong ( x>>y) et ylong ( y>>x), et en vérifiant laquelle des chaînes résultantes est lexicographiquement plus grande.

x ## y
  | (x>>x) < (y>>x) = y
  | True = x

Finalement, ffrécursive sur la chaîne d'entrée, génère le préfixe le plus long avec ss, détermine de manière récursive la sous-chaîne non répétée la plus longue de la fin de la chaîne et renvoie le plus long des deux avec (##):

ff "" = ""
ff (x:r) = ss(x:r) ## ff r

Lua, score 3, 274 octets

g='g'..'s'..'u'..'b'  _G  [  'l'..'o'..'a'..'d'  ](  g[g  ](  "s  =...f  o  r d = # s - 1 , 0 , - 1 d  o f  or r = 1 , # s - d d  o t = s :s  ub  (r  ,r  +d  )i  f n  ot t:  fi  nd  '(  .)  .*  %1  't  he  n p  ri  nt  (t  )r  et  ur  n en  d e  n  d e  nd  ","  ",""))(...)

Note: Lua 5.2 ou Lua 5.3 est requis

Usage:

$ lua lnrs.lua "Good morning, Green orb!"
ing, Gre
$ lua lnrs.lua "fffffffffff"
f
$ lua lnrs.lua "oiiiiioiiii"
oi
$ lua lnrs.lua "1234567890"
1234567890
$ lua lnrs.lua "11122324455"
324

Idée principale: tout entrelacer d'espaces, insérer " "(deux espaces) pour diviser des identifiants longs

Code non golfé:

g = "gsub"
_G["load"](
   g[g](      -- g[g] == string.gsub - a function for substitution of substrings
      "The source of actual program, but two-space sequences were inserted in some places", 
      "  ",   -- we are replacing all two-space substrings
      ""      -- with an empty string
   )
)(...)

Programme actuel (après suppression de toutes les paires d'espaces):

s = ...
for d = #s - 1, 0, -1 do
   for r = 1, #s - d do
      t = s:sub(r, r+d)
      if not t:find"(.).*%1" then
         print(t)
         return
      end
   end
end

BTW, l'extrait de code JS pour calculer le score échoue sur mon code.

Retina 0.8.2 , 37 octets, score 9

.
$&$'¶
(.)(?<=\1.+).*

O#$^`
$.&
1G`

Essayez-le en ligne! La traduction directe de cette réponse sur Retina 1 enregistre un octet en utilisant à la Nplace de O#. Cependant, si vous golfez naïvement la réponse de Retina 1 à 28 octets, son score passe à 10! Explication:

.
$&$'¶

Génère tous les suffixes de l'entrée.

(.)(?<=\1.+).*

Pour chaque suffixe, prenez le préfixe jusqu'au premier caractère dupliqué.

O#$^`
$.&

Triez les chaînes restantes dans l'ordre inverse de la longueur (c'est-à-dire la plus longue en premier).

1G`

Prends le plus long.

Gelée , score 2, 14 octets

Ẇµµff  Q  €  Ṫ

Merci à @JonathanAllan pour le score -1, +7 octets et pour avoir remarqué un bogue.

Essayez-le en ligne!

Comment ça marche

Ẇµµff  Q  €  Ṫ  Main link. Argument: s (string)

Ẇ               Window; yield all substrings of s, sorted by length.
 µ              Begin a new chain. Argument: A (array of substrings)
  µ             Begin a new chain. Argument: A (array of substrings)
   f            Filter A by presence in itself. Does nothing.
       Q  €     Unique each; deduplicate all strings in A.
    f           Filter A by presence in the array of deduplicated substrings,
                keeping only substrings composed of unique characters.
             Ṫ  Tail; take the last (longest) kept substring.

Nettoyer , marquer 7 5, 276 octets

@[ss:s]=rr(pp[][ss:s])((@s))
@s=s
ee x[rr:xx]|e x rr=True=ee x xx
ee x xx=f
f=e'e'' '
e::!  Char  !  Char  ->Bool
e  _ _=  code  {

eqC
}
pp p[r:rr]|ee r p=p=pp(a r p)rr
pp a _=a
a  x[ll:l]=[ll:a x  l]
a l ll=[l]
l[]rr=e'l''l'
l ff[]=f

l[r:rr][ss:ll]=l rr ll
rr x y|l x y=y=x

Essayez-le en ligne! Merci à @ Οurous de m'avoir montré qu'il est possible d'appeler le code machine ABC directement à partir de Clean. Cela permet de se débarrasser du goulot précédentimport qui fixait le score minimal à 7, mais nécessite le mot-clé codefixant le score minimal à 5 ​​pour cette approche.

Une version non golfée et non optimisée du score du code ci-dessus peut être trouvée ici: Essayez-le en ligne!

Version précédente avec note 7, 158 154 130 octets

import  StdEnv  
@[xx:rr]=c(%[][xx:rr])(@rr)
@e=e
c s b|  length  s<  length  b=b=s
%s[xx:r]|  isMember xx s=s= %(s++[xx])r
%r _=r

Essayez-le en ligne!

Avec le importscore, on ne peut pas descendre en dessous de 7. Sans l'importation, il serait nécessaire d'implémenter l'égalité sur les chaînes ou les caractères sans aucune fonction de bibliothèque, ce qui n'est probablement pas possible, comme on peut le voir dans la nouvelle version ci-dessus.

Python 3 , score 4, 155 octets

exec(('l=la''mbd''a f'',e=en''ume''rat''e:m''ax''([f[ j  :k]  for  j,i in e ( f)f''or  k,i in e ( f )if  len  ( { *''f[j'':k]''})==k-''j],''key''=le''n)'))

Ceci définit une fonction l.

Merci à @xnor pour avoir signalé que des chaînes de longueur 3 ne soulèvent pas le score, ce qui permet d'économiser 32 octets.

Essayez-le en ligne!

Brachylog , score 2, 19 octets

s  ᶠ  l  ᵒ  ≠  ˢ  t

Essayez-le en ligne!

Juste un vieux ennuyeux "espace tout" réponse. Au moins, j’ai appris que les métaprédicats peuvent être espacés des prédicats et fonctionnent toujours (et que les sous-scripts et les exposants (paramétriques) ne le peuvent pas).

s ᶠ - trouver toutes les sous-chaînes de la chaîne donnée

l ᵒ - les classer par longueur (croissant par défaut)

≠ ˢ - sélectionnez ceux qui ont tous les éléments distincts

t - récupère la queue (dernier élément) de celui-ci - celui qui a la plus grande longueur

Pyth , 11 octets, score 4

-4 score grâce à Dennis

e lD {I# .:

elD{I#.:Q      Full program, inputs "string" from stdin and outputs to stdout
e              The last element of the list generated by taking
      .:Q      All substrings of the input
     #         Filtered for
   {I          Being invariant over deduplicate i.e. being "non-repeating"
 lD            and sorted by length

Essayez-le en ligne!

Husk , score 2, 10 octets

►IIËII≠IIQ

Essayez-le en ligne!

Explication

Le programme est équivalent à ceci:

►Ë≠Q  Implicit input.
   Q  List of substrings.
►     Find one that maximizes:
 Ë    all ordered pairs
  ≠   are inequal.

L'intégré Ëévalue ≠toutes les paires ordonnées de son argument xet retourne length(x)+1si tous les résultats sont vrais, sinon 0. Lorsque nous maximisons cela, nous trouvons la chaîne la plus longue qui ne contient pas de caractères répétés.

Dans la soumission, je viens d'insérer la fonction d'identité Ientre chaque fonction, deux fois. Puisque IËest le même que Ë, I≠est le même que ≠et ainsi de suite, cela ne change pas la sémantique. Le seul danger est qu'une fonction d'ordre supérieur puisse décider d'utiliser l'un des Is comme argument, mais heureusement, cela conduit à une erreur de type dans notre programme, de sorte que cela ne se produit pas.

Clojure, score 4

#(  let  [N  (fn  [[_ & r]] r) R  (fn  R [f v c]  (if  c (R f (f v (  nth  c 0))  ( N  c)) v)) C  (fn  C  (  [i]  (C (  seq  i) 0)) ( [i  n]  (if i (C ( N  i )  (  inc n)) n)))  J  (fn  [c  i]  (assoc c (C  c) i)) I  (fn  F [f i n R]  (if ( =  (C  R) n) R (F f (f  i) n ( J  R (f  i)))))] ( apply  str  (R ( fn  [a  b] ( if  (< (C  a)  (C  b)) b a )) "" (  for  [k  (I N % (C  % ) [])]  (R  ( fn [ t  c ] ( if ( or ( = t (  str t) ) ((  set t)c))(apply  str t) ( J  t c)))[]k)))))

Oh mec c'était douloureux! Nimplémente next, Rest reduce, Cest count, Jest conj(ne fonctionne que pour les vecteurs) et Iest iterate.apply strexiste-t-il deux fois, sinon l'entrée "aaaa" ne renverrait pas une chaîne mais un vecteur [\a]. Heureusement, j'ai eu l'occasion de l'utiliser applyet assocje ne savais pas que vous pouviez associer un indice au-delà du dernier élément d'un vecteur: o

Gelée , score 5, 10 octets

ẆµQQ⁼µÐfµṪ

Essayez-le en ligne!

Python 3 , score 4, 317 octets

exec(('%s'  *58  %(  's=','in','pu','t(',');','pr','in','t(','so','rt','ed','((s','[i',':j',']f','or',' j',' i','n ','ra','ng','e(','1,','le','n(','s)','+1',')f','or',' i',' i','n ','ra','ng','e(','j)','if',' l','en','(s','et','(s','[i',':j',']))','==l','en','(s','[i',':j',']))',',k','ey','=l','en',')[','-1','])')))

Essayez-le en ligne!

Code non spécifié:

s=input();print(sorted((s[i:j]for j in range(1,len(s)+1)for i in range(j)if len(set(s[i:j]))==len(s[i:j])),key=len)[-1])

lambda acontient mbda ce qui a un score de 5, et une fonction returnqui ne peut apparemment pas être execmodifiée (il faut donc un score d'au moins 5 pour eturn), donc un programme complet était nécessaire. Il est probablement possible de jouer un peu plus bas sur la taille du code non spécifié, mais je ne vois pas d'amélioration rapide.

Alice , 40 octets

/ii..nn$$@@BBww..DD~~FF..!!nn$$KK??oo@@

(Retour à la ligne)

Essayez-le en ligne!

Le pointeur d'instruction se déplaçant diagonalement en mode ordinal, seul un autre caractère est exécuté.

[email protected]~F.!n$K?o@

i     take input
.n$@  terminate if empty
B     push all nonempty substrings, with the longest on the top of the stack
w     push return address (start main loop)
.     make copy of current substring
D     deduplicate characters
~     swap: this places the original above the deduplicated copy
F     Push the original string if it is a substring of the deduplicated copy
      (which can only happen if they're equal); otherwise push empty string
.!    place a copy on the tape
n$K   if the empty string was pushed, return to start of loop
o     output
@     terminate

Perl 6 , score: 15 10 8, longueur: 46 55 62 octets

{~m:ov/(.+)<!{$0.comb.repeated}>/.max(&chars)}

Essaye-le

{~m:ov/(..*)<!{(($0)).comb.repeated}>{{}}/.max(&chars)}

Essaye-le

{m:ov:i/(..*)<!{(($0)).comb.repeated}>{{}}/.max((&chars)).Str}

Essaye-le

Étendu:

{    # bare block lambda with implicit parameter ｢$_｣

    m                          # match (implicitly against ｢$_｣)
    :overlap                   # in every single way possible
    :ignorecase                # add a ｢:｣ to break up substring
    /

      (..*)                    # match at least one character

      <!{
        (($0)).comb.repeated  # backtrack if there were repeats
      }>

      {{}}                    # anon hash in code block (no-op)
    /

    .max((&chars))            # get the longest

    .Str                      # coerce to a Str (from a Match object)
}

Java 8, score 9 (384 B) 7 (401 B)

S -> { int s = 0 , e = 0 , l = 0 , x = 0 , y = 0 , b [ ] = new int [ 256 ] ; for ( ; x <S.  length  & y <S.  length  & l <S.  length  - x ; x ++ ) { b [S[x]] = 1 ; for ( y ++ ; y <S.  length  && b [S[y]] < 1 ; b [S[y ++]] = 1 ) ; if ( l < y - x ) { s = x ; e = y ; l = y - x ; } for ( ; y <S.  length  && x < y & S[x] != S[y  ];)b [S[x ++]] = 0 ; }  String g=""; for( ; s<e ; g+= S[s++]);  return  g;}

• Version initiale. Va descendre d'ici. Le score est de 9 en raison de "ubstring ", ce substringsera donc la première partie à remplacer.
• Le score est maintenant de 7 " length", ce que je ne pourrai probablement pas réduire davantage. Je doute qu'il soit possible de supprimer les quatre utilisations delength . Si cela est possible, " eturn"(6) pourrait réduire le score de 1 en amélioration finale, mais je suppose que c'est le cas (sauf peut-être une petite réduction du nombre d'octets ..)

Essayez-le en ligne.

Haskell , score 7

-4 Merci à Laikoni.

import  Data.List  
f s=snd $ maximum [ (0<$i ,i)|i<-  tails  =<<inits s, nub i==i]

Essayez-le en ligne!

Mathematica, partition 11 9

Length@Last@Select[Subsequences[Characters@#],#==DeleteDuplicates  @#&]&

Raser quelques octets de la plus longue chaîne non répétée en masquant le nom de la fonction:

Length@Last@Select[Subsequences[Characters  @#],#==(  ToExpression@ 
StringJoin@@FromCharacterCode@{{68},{101},{108},{101},{116},{101},{68},{117},
{112},{108},{105},{99},{97},{116},{101},{115}}))@#&]&

Kotlin , score: 11 10 9 octets, longueur: 227 246 245 octets

indices
  .flatMap { p -> indices . map { p to p + it } }
  .  filter { (r,i) -> i < length  }
  .map { ( s , a )->substring  (  s,  a  ) }
  .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
  .maxBy { it.length }

Le plus long est ubstring , qui est de 9 caractères

Cela s'appelle comme ça:

val c = "Good morning, Green orb!"

fun String.c(): String? = indices
    .flatMap { p -> indices . map { p to p + it } }
    .  filter { (r,i) -> i < length  }
    .map { ( s , a )->substring  (  s,  a  ) }
    .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
    .maxBy { it.length }

fun main(args: Array<String>) {
    val text = """indices
    .flatMap { p -> indices . map { p to p + it } }
    .  filter { (r,i) -> i < length  }
    .map { ( s , a )->substring  (  s,  a  ) }
    .  filter { it  .  groupBy  { it } .  none { ( k , v )->v . size>1 } }
    .maxBy { it.length }"""
    val message = text.c()!!
    println(message)
    println(text.length)
    println(message.length)
    println(c.c())
}

Pyth , score 3 (  18 à  14 octets)

e  fq  T{T  .:

Essayez-le en ligne!

La plus longue sous-chaîne non répétée est  .:.

05AB1E , 22 octets | Score: 2

Œ  ʒ  D  Ù  Q  }  é  ¤

-1 score + 7 octets grâce à HeebyJeeby

Essayez-le en ligne!

05AB1E , 15 octets | Score: 3

Œ ʒ D Ù Q } é ¤

Essayez-le en ligne!

05AB1E , 8 octets | Score: 8

ŒʒDÙQ}é¤

Essayez-le en ligne!

05AB1E peut réellement faire quelque chose d'assez bon marché ... ajouter des espaces dans 05AB1E ne fait rien.

S'il y a une règle contre cela, je peux aussi utiliser ´et aimer 7 autres caractères.