Najkrótszy, najmniejszy leksykograficznie ciąg generujący

Łańcuch x generuje łańcuch, yjeśli yjest podciągiem nieskończonego powtórzenia x. Na przykład abcgeneruje bcabcab.

Napisz program, aby znaleźć najkrótszy, najmniejszy leksykograficznie ciąg znaków, który wygeneruje dane wejściowe. Przy standardowym wprowadzaniu podawany jest pojedynczy wiersz tekstu. Powinieneś wydrukować ciąg generujący na standardowe wyjście. Na przykład:

Wejście

bcabcabca

wynik

abc

Najkrótszy kod wygrywa. Możesz założyć, że dane wejściowe zawierają tylko znaki az (i końcowy znak nowej linii, jeśli chcesz).

Ruby 1.9, 40 znaków

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

Zakłada, że ​​wejście nie jest zakończone znakiem nowej linii. Prawdopodobnie jest też absurdalnie powolny dla większych wyników.

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

Python 88 185 znaków

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

Wynik:

bcabcabca
abc

aaa
a

abc
abc

cccbbcccbbcccbb
bbccc

barfoofoobarfoofoo
arfoofoob

bacabac
abacbac

Haskell, 299 128 znaków

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

Dzięki jloy! Teraz wersja jest znacznie krótsza i uważam, że jest poprawna.

Python, 121 137 129 znaków

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)

EDYCJA: naprawiono błąd wykryty przez JiminP

Ruby 1.9, 36

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

Stosuje to samo podejście, co rozwiązanie Ventero.

Pyton, 161 159 166 140 141 141 134 132 znaki

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

EDYCJA : Odczytałem kod po przeczytaniu komentarza Julesa Olléona. Usunięto błąd, który bcdabcdabpowoduje abbc.

EDYCJA 2 : Naprawiono błąd ( abaawyniki w aaa) zauważony przez Julesa Olléona.

Nie znam dobrze Pythona, więc ten kod prawdopodobnie nie jest „golfem”.

Uwielbiam tę zasadę:

Możesz założyć, że dane wejściowe zawierają tylko znaki az ...

Wejścia wyjścia

bcdabcd
abcd

bcabcabca
abc


abcdabcd
abcd

bcdabcdab
abcd

barfoofoobarfoofoobar
arfoofoob

cccbbcccbbcccbb
bbccc

aaaaaaaaaaaaaaaa
a

thequickbrownfox
brownfoxthequick

ababa
ab

abaa
aab

Matematyka 124 bajty

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

Białe znaki i znaki nowej linii (w obecności średników na końcach wierszy) nie mają znaczenia w Mathematica i zostały tutaj uwzględnione dla czytelności.

Dane wejściowe znajdują się między znakami cudzysłowu w pierwszym wierszu. W przypadku przekształcenia jako funkcji, pobiera ciąg znaków w następujący sposób:

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

to jest 128 bajtów.

ForPętla zajmuje pierwsze iznaki wejścia i powtarza je co najmniej do długości wejściowych, a następnie sprawdza, czy wejście jest podciąg wyniku. Po znalezieniu długości okresu łańcucha, StringPartitionpolecenie konkatenuje dwie kopie tego okresu i pobiera z niego wszystkie podciągi o tej długości (w zasadzie pobiera wszystkie permutacje cykliczne), a następnie First@Sortwyszukuje pierwszy z nich, gdy jest uporządkowany leksykograficznie.

javascript 96 znaków.

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

Working Plunkr