title: Can It Be Faster to Find the Minimum Periodic String Inside Another String in Terms of Time Complexity
body: <p>I'm trying to solve this ACM problem (<code>10298 - Power Strings</code>): <a href="http://uva.onlinejudge.org/external/102/10298.html" rel="nofollow">http://uva.onlinejudge.org/external/102/10298.html</a></p>
  
  <p>The problem is to find the minimum periodic string inside of another string.  For example:</p>
  
  <p>Test Input:</p>
  
  <pre><code>abcd
  aaaa
  ababab
  </code></pre>
  
  <p>Test Output:</p>
  
  <pre><code>1
  4
  3
  </code></pre>
  
  <p>My idea is:</p>
  
  <ol>
  <li>Let <code>s</code> be the input string;</li>
  <li>Make a string <code>ss</code> from <code>s+s</code>, and shift the first character;</li>
  <li>Find the first occurrence of <code>s</code> in string <code>ss</code>.</li>
  </ol>
  
  <p>Below is my code:</p>
  
  <pre><code>inline int GetLargestN(const char* cs)
  {
      string s(cs);
      string ss(s, 1); ss += s; ss += s[0];
  
      int len = s.length();
      int pos = ss.find(s);
  
      return len/(pos+1);
  }
  </code></pre>
  
  <p><a href="http://www.cplusplus.com/reference/string/string/find/" rel="nofollow">http://www.cplusplus.com/reference/string/string/find/</a> string::find should be O(n)</p>
  
  <p>However, I keep getting Time Limitation Exceeds</p>
  
  <p>NOTES:</p>
  
  <ol>
  <li><p>I also tried my own <code>find</code> substring match using Sunday Search, whose time complexity is also O(n), but still TLE.</p></li>
  <li><p>I am NOT a student, so I am NOT asking for home assignment help. I'm a working professional. Solving ACM problems is just my hobby.</p></li>
  </ol>
  
  <p>Please help.</p>