title: Find the prefix which is also a suffix
body: <p>I'm looking for an optimal solution for this problem.</p>
  
  <p>Given a <code>string s of length n</code>, find a prefix left-to-right equivalent to a suffix right-to-left.</p>
  
  <p>The prefix and suffix can overlap.</p>
  
  <p>Example: given <code>abababa</code>, prefix is <code>[ababa]ba</code>, suffix is <code>ab[ababa]</code>.</p>
  
  <p>I am able to go till this</p>
  
  <ol>
  <li><p>for each <code>i = 0 to n-1</code>, take the prefix ending at i and find if we have an appropriate suffix. It's time is <code>O(n^2)</code> time and <code>O(1)</code> space.</p></li>
  <li><p>I came up with an optimization where we index the positions of all the characters. This way, we can eliminate set of sample spaces from 1/. Again, the worst case complexity is <code>O(n^2)</code> with <code>O(n)</code> additional space.</p></li>
  </ol>
  
  <p>Are there any better algorithm for this ? </p>