The concatenation of \(S\) and reversed \(S\) is obviously a palindrome, so the length of a sought string is at most \(2 \times |S|\).

Consider the property of a palindrome of length \(|S|+k\) (\(0 \le k \le |S|\)) that has a prefix \(S\).
Let \(S_1S_2 \dots S_{|S|}T_1T_2 \dots T_k\) be the resulting palindrome; then by definition of palindrome, we obtain the following equations:

• \(S_1 = T_k\)
• \(S_2 = T_{k-1}\)
• \(\dots\)
• \(S_k = T_1\)
• \(S_{k+1} = S_{|S|}\)
• \(\dots\)
• \(S_{ \lfloor (|S|+k+1)/2 \rfloor}=S_{\lfloor (|S|+k+2)/2 \rfloor}\)

In other words, the last \((|S|-k)\) characters of \(S\) must form a palindrome, and \(T_1,T_2,\dots,T_k\) are uniquely determined by \(S\).
Now the problem has been boiled down to the following:

Find the longest suffix of \(S\) that is a palindrome.

There are various ways to solve this problem. One of the most direct ones is to use Manacher’s algorithm (translator’s note: English article can be found e.g. here.

All that left is to reconstruct the answer to the original problem from the result. Using Manacher’s algorithm, the problem can be solved in \(O(N)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

vector<int> manacher(string &S){
  vector<int> R(S.size());
  int i = 0, j = 0;
  while (i < S.size()) {
    while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
    R[i] = j;
    int k = 1;
    while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
    i += k; j -= k;
  }
  return R;
}

int main(){
  string s;
  cin >> s;
  string ms="$";
  for(auto &nx : s){
    ms.push_back(nx);
    ms.push_back('$');
  }
  auto r=manacher(ms);
  int k=0;
  for(int i=s.size();;i++){
    if(r[i]>=s.size()-k){break;}
    k++;
  }

  cout << s;
  for(int i=0;i<k;i++){
    cout << s[k-1-i];
  }cout << "\n";
  return 0;
}