title: Shortest Repeating Sub-String
body: <p>I am looking for an efficient way to extract the shortest repeating substring.
  For example:</p>
  
  <pre><code>input1 = 'dabcdbcdbcdd'
  ouput1 = 'bcd'
  
  input2 = 'cbabababac'
  output2 = 'ba'
  </code></pre>
  
  <p>I would appreciate any answer or information related to the problem. </p>
  
  <p>Also, in <a href="https://stackoverflow.com/questions/7883688/smallest-repeating-substring">this post</a>, people suggest that we can use the regular expression like</p>
  
  <pre><code>re=^(.*?)\1+$
  </code></pre>
  
  <p>to find the smallest repeating pattern in the string. But such expression does not work in Python and always return me a non-match (I am new to Python and perhaps I miss something?).</p>
  
  <p>--- follow up ---</p>
  
  <p>Here the criterion is to look for shortest non-overlap pattern whose length is greater than one and has the longest overall length.</p>