CodeForces.1326D2 Prefix-Suffix Palindrome (Hard version)

1.Problem
https://codeforces.com/contest/1326/problem/D2

2.Idea
KMP algorithm

3.Source

 string s;  
 int n;  
 //kmp algorithm: returns len of the longest pre==suf   
 int longest_palindrome_prefix(const string s)  
 {  
      string kmprev = s;  
      reverse(kmprev.begin(), kmprev.end());  
      string kmp = s + "#" + kmprev;  
      vector<int> lps(kmp.size(), 0);  
      for (int i = 1; i < (int)lps.size(); ++i)  
      {  
           int prev_idx = lps[i - 1];  
           while (prev_idx > 0 && kmp[i] != kmp[prev_idx])  
           {  
                prev_idx = lps[prev_idx - 1];  
           }  
           lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);  
      }  
      return lps[lps.size() - 1];  
 }  
 int32_t main()  
 {  
      int t;  
      cin >> t;  
      while(t--)  
      {  
           cin >> s;  
           n = s.length();  
           int ln = 0;  
           for (int i = 0, j = n - 1; i < j; ++i, --j)  
                if (s[i] == s[j])  
                     ln++;  
                else  
                     break;  
           int rem = n - 2 * ln;  
           string ans;  
           if (ln)     ans = s.substr(0, ln);  
           if (rem > 0)  
           {  
                string st = s.substr(ln, rem);  
                int pre = longest_palindrome_prefix(st);  
                reverse(st.begin(), st.end());  
                int suf = longest_palindrome_prefix(st);  
                if (pre > suf) {  
                     reverse(st.begin(), st.end());  
                     ans += st.substr(0, pre);  
                }  
                else {  
                     ans += st.substr(0, suf);  
                }  
           }  
           if (ln) ans += s.substr(n - ln, ln);  
           std::cout << ans << '\n';  
      }  
      return 0;  
 }