Shortest, lexicographically smallest generating string

Question

A string x generates a string y if y is a substring of an infinite repeat of x. For example abc generates bcabcab.

Write a program to find the shortest, lexicographically smallest string that will generate the input. You are given on standard input a single line of text. You should print the generating string to standard output. For example:

input

bcabcabca

output

abc

Shortest code wins. You may assume the input contains only the characters a-z (and a trailing newline if you want).

Answer 1

Ruby 1.9, 40 characters

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

Assumes the input is not terminated by a newline. Also it's probably ridiculously slow for larger results.

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

Answer 2

Python 88 185 chars

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

Output:

bcabcabca
abc

aaa
a

abc
abc

cccbbcccbbcccbb
bbccc

barfoofoobarfoofoo
arfoofoob

bacabac
abacbac

Answer 3

Haskell, 299 128 characters

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

Thanks to jloy! Now the version is both far shorter and I believe correct.

Answer 4

Python, 161 159 166 140 141 134 132 chars

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 : Golfed the code after reading Jules Olléon's comment. Removed a 'bug' that bcdabcdab results in abbc.

EDIT2 : Fixed the bug (abaa results in aaa) spotted by Jules Olléon.

I don't know about Python well, so this code is probably 'not golfed'.

I love this rule:

You may assume the input contains only the characters a-z...

Inputs & Outputs

bcdabcd
abcd

bcabcabca
abc


abcdabcd
abcd

bcdabcdab
abcd

barfoofoobarfoofoobar
arfoofoob

cccbbcccbbcccbb
bbccc

aaaaaaaaaaaaaaaa
a

thequickbrownfox
brownfoxthequick

ababa
ab

abaa
aab

Answer 5

Python, 121 137 129 chars

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: fixed the bug spotted by JiminP

Answer 6

Ruby 1.9, 36

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

Uses the same approach as Ventero's solution.

Answer 7

Mathematica 124 bytes

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

Whitespace and newlines (in the presence of semicolons at the ends of lines) have no meaning in Mathematica and are included here for readability.

Input goes in between the quotation marks in the first line. If recast as a function, that takes string input like so:

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

then it's 128 bytes.

The For loop takes the first i characters of the input and repeats them at least up to the length of the input, then checks if the input is a substring of the result. Having found the length of the period of the string, the StringPartition command concatenates two copies of that period and takes all substrings of that length from it (basically gets all cyclic permutations), then First@Sort finds the first one of them when lexicographically ordered.

Answer 8

PowerShell, 23 bytes

-join($args|group|% N*)

Try it online!

Answer 9

javascript 96 Chars.

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

Working Plunkr