<p>You are given a string <code>s</code>. You can convert <code>s</code> to a <span data-keyword="palindrome-string">palindrome</span> by adding characters in front of it.</p>

<p>Return <em>the shortest palindrome you can find by performing this transformation</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aacecaaa"
<strong>Output:</strong> "aaacecaaa"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> "dcbabcd"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters only.</li>
</ul>

using ll = long long ;
class Solution {
public:
    string shortestPalindrome(string s) {
          ll n = s.length();
          if(n < 2) return s;
          string t = s;   
          reverse(t.begin(),t.end());
        
        string l = s + "#" + t;
        
        
//         int end = 0;
//         for(int i=n-1;i>=0;i--){
//             string subs = s.substr(0,i+1);
//             string revsub = subs;
//             reverse(revsub.begin(),revsub.end());
//             if(subs == revsub){
//                 end = i;   
//                 break ;
//             }   
//         }
//         for(int i=end+1;i<n;i++){
//             s.insert(s.begin(),t[i]);
//         }
//         return s;  
//     }
    
//         vector<ll>hashs(n,0);
//         vector<ll>hasht(n,0);
//         vector<ll>power(n,0);
//         ll mod = 1e9 + 7;
//         ll p = 31;
//         power[0] = 1;
//         for(int i=1;i<n;i++){
//             power[i] = (power[i-1]*p)%mod;
//         }
//         hashs[0] = (s[0]-'a'+1);
//         hasht[0] = (t[0] - 'a' + 1);
//         for(int i=1;i<n;i++){
//             hashs[i] = (hashs[i-1] + ((s[i]-'a'-1)*power[i])%mod)%mod;
//             hasht[i] = (hasht[i-1] + ((t[i]-'a'-1)*power[i])%mod)%mod;
//         }
     
        vector<ll>lps(l.size(),0);
        
        // int i = 0; int j = 1;
        int lsize = l.size();
        int j = 1;
        int i = 0;
        cout<<lsize<<" ";
        while(j < lsize){
            if(l[i] == l[j]){
                lps[j] = i+1;
                i++; j++;
            }
            else{
                if(i==0){
                    j++;
                }
                else{
                    i = lps[i-1];
                }
            }
        }
        cout<<endl;
        for(int k=0;k<lsize;k++){
            cout<<lps[k]<<" ";
        }
        cout<<endl;
        string lpsoffull = l.substr(0,lps[l.size()-1]);
        int palsize = lpsoffull.length();
        cout<<lpsoffull<<" "<<lps[lsize-1];
        string topush = l.substr(palsize,n-palsize);
        // lpsoffull += topush;
        reverse(topush.begin(),topush.end());
        string ans = topush;
        ans += lpsoffull;
        reverse(topush.begin(),topush.end());
        ans += topush;
        return ans;
    }
};
13300