Chaîne de génération la plus courte et lexicographiquement la plus petite

Une chaîne x génère une chaîne ysi yest une sous-chaîne d'une répétition infinie de x. Par exemple abcgénère bcabcab.

Écrivez un programme pour trouver la chaîne la plus courte et lexicographiquement la plus petite qui générera l'entrée. On vous donne en entrée standard une seule ligne de texte. Vous devez imprimer la chaîne de génération sur la sortie standard. Par exemple:

contribution

bcabcabca

production

abc

Le code le plus court gagne. Vous pouvez supposer que l'entrée ne contient que les caractères az (et un retour à la ligne si vous le souhaitez).

Ruby 1.9, 40 caractères

gets;a=?a;a.next!until(a*~/$/)[$_];$><<a

Suppose que l'entrée n'est pas terminée par une nouvelle ligne. De plus, c'est probablement ridiculement lent pour des résultats plus importants.

$ echo -n "bcabcabca" | ruby genlex.rb 
abc
$ echo -n "barfoobarfoobarfoo" | ruby1.9 genlex.rb 
arfoob

Python 88 185 caractères

import re
s=raw_input()
m=s.index(min(s))
s=s[m:]+s[:m]
i=0
while s.replace(s[:i],''):i+=1
m=min(s[:i])
s=re.findall('%s[\w]*?(?=%s|$)'%(m,m),s[:i])
m=s.index(min(s))
print ''.join(s[m:]+s[:m])

Production:

bcabcabca
abc

aaa
a

abc
abc

cccbbcccbbcccbb
bbccc

barfoofoobarfoofoo
arfoofoob

bacabac
abacbac

Haskell, 299 128 caractères

import Data.List
main=interact(\z->minimum$filter(\w->isInfixOf z$concat$replicate(length z)w) $filter((/=)"")$inits=<<tails z)

Merci à jloy! Maintenant, la version est à la fois beaucoup plus courte et je crois correcte.

Python, 121 137 129 129 caractères

s=raw_input()
n=len(s)
l=[(s+s)[i/n:i/n+i%n+1]for i in range(n*n)]
print min(filter(lambda x:(x*len(s)).find(s)+1,sorted(l)),key=len)

EDIT: correction du bug repéré par JiminP

Rubis 1.9, 36

$><<(?a..gets).find{|s|(s*~/$/)[$_]}

Utilise la même approche que la solution de Ventero.

Python, 161 159 166 140 141 134 132 caractères

y=raw_input();i=n=l=len(y)
while i:
 if (y[:i]*l)[:l]==y:n=i
 i-=1
x=y[:n];y=x*2
while i<n:
 x=min(x,y[i:i+n])
 i+=1
print x

EDIT : Golfé le code après avoir lu le commentaire de Jules Olléon. Suppression d'un «bug» qui se bcdabcdabtraduit par abbc.

EDIT2 : Correction du bug ( abaarésultats dans aaa) repéré par Jules Olléon.

Je ne connais pas bien Python, donc ce code n'est probablement pas «joué au golf».

J'adore cette règle:

Vous pouvez supposer que l'entrée ne contient que les caractères az ...

Entrées et sorties

bcdabcd
abcd

bcabcabca
abc


abcdabcd
abcd

bcdabcdab
abcd

barfoofoobarfoofoobar
arfoofoob

cccbbcccbbcccbb
bbccc

aaaaaaaaaaaaaaaa
a

thequickbrownfox
brownfoxthequick

ababa
ab

abaa
aab

Mathematica 124 octets

x = StringLength@(y = "");
For[i = 1, ! (s = y~StringTake~i)~StringRepeat~x~StringContainsQ~y,i++];
First@Sort@StringPartition[s <> s, i, 1]

Les espaces et les retours à la ligne (en présence de points-virgules à la fin des lignes) n'ont aucune signification dans Mathematica et sont inclus ici pour plus de lisibilité.

L'entrée passe entre les guillemets de la première ligne. Si la refonte est une fonction, cela prend une entrée de chaîne comme ceci:

f=(x=StringLength@(y=#);For[i=1,!(s=y~StringTake~i)~StringRepeat~x~StringContainsQ~y,i++];First@Sort@StringPartition[s<>s,i,1])&

f@"bca"

(* "abc" *)

f@"abaa"

(* "aab" *)

alors c'est 128 octets.

La Forboucle prend les premiers icaractères de l'entrée et les répète au moins jusqu'à la longueur de l'entrée, puis vérifie si l'entrée est une sous-chaîne du résultat. Après avoir trouvé la longueur de la période de la chaîne, la StringPartitioncommande concatène deux copies de cette période et en prend toutes les sous-chaînes (obtient essentiellement toutes les permutations cycliques), puis First@Sorttrouve la première d'entre elles lorsqu'elle est ordonnée lexicographiquement.

javascript 96 caractères.

var temp = {},len = str.length;
for(i in str) 
temp[str[i]] = true;
Object.keys(temp).join(""); 

Plunkr de travail