title: Given string s, find the shortest string t, such that, t^m=s
body: <p>Given string s, find the shortest string t, such that, t^m=s.</p>
  
  <p>Examples:</p>
  
  <pre><code>s="aabbb" =&gt; t="aabbb"
  s="abab"  =&gt; t = "ab"
  </code></pre>
  
  <p>How fast can it be done? </p>
  
  <p>Of course naively, for every m divides |s|, I can try if substring(s,0,|s|/m)^m = s. </p>
  
  <p>One can figure out the solution in O(d(|s|)n) time, where d(x) is the number of divisors of s. Can it be done more efficiently?</p>