Shortest, lexicographically smallest generating string 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).
Ruby 1.9, 40 characters

gets;a=?a;a.next!until(a*~/$/)[$_];$&gt;&lt;&lt;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