title: Algorithm to extend to shortest palindrome by only adding characters at the end of the string
body: <p>I found one algorithm problem. I solved that problem, but I want to optimize that. I ask the same problem here.</p>
  
  <p><strong>Problem</strong></p>
  
  <p>One String is given and the length of that string is <strong>N &lt;= 10000000</strong>. All characters of that string is from <strong>'a' to 'z'</strong>. Now we have to calculate smallest palindrome that we can make from given string by adding characters the end.</p>
  
  <p><strong>Example</strong></p>
  
  <p>Given String = 'abab'</p>
  
  <p>Output = 'ababa'</p>
  
  <p>Reasoning:  the string <code>ababa</code> contains the string <code>abab</code> starting from both the beginning and end of the string, with only 1 extra character on each end.</p>
  
  <p><strong>Edited</strong></p>
  
  <p>String = 'abbcd'
  Output = 'abbcdcbba'</p>
  
  <p><strong>My attemp</strong></p>
  
  <p>I can solve this problem in O(N^2) complexity.</p>
  
  <p><strong>My question</strong></p>
  
  <p>Can I solve this problem in less than O(N^2) time ? , If yes, than what is the algorithm? (Give me a hint)</p>