<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>

class Solution {
public:
    string shortestPalindrome(string s) {
        ios_base::sync_with_stdio(false);
        int n=s.size();
        vector<int> lps(2*n+1);
        int c=0;
        for(int i=0;i<2*n+1;i++)
        {
            int m=2*c-i;
            if(c+lps[c]>i) lps[i]=min(lps[m],c+lps[c]-i);
            int a=i+(lps[i]+1),b=i-(lps[i]+1);
            while(b>=0&&a<2*n+1&&((a%2==0&&b%2==0)||(s[a/2]==s[b/2])))
            {
                b--;
                a++;
                lps[i]++;
            }
            if(i+lps[i]>c+lps[c]) c=i;
        }
        int cen=0;
        for(int i=1;i<2*n+1;i++)
        {
            if(lps[i]==i)
            {
                cen=i;
            }
            cout<<lps[i]<<" ";
        }
        string r=s.substr(lps[cen]);
        reverse(r.begin(),r.end());
        return r+s;
    }
};
11000