<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){
        if(s.empty()) return s;

        string rev_s =s;
        reverse(rev_s.begin(),rev_s.end());

        string combined =s+"#" +rev_s;

        int n=combined.length();

        vector<int> kmp(n,0);

        buildKMP(combined,n,kmp);

        int palindrome_suffix_length =kmp[n-1];
        string non_palindrome_suffix= s.substr(palindrome_suffix_length);

        reverse(non_palindrome_suffix.begin(),non_palindrome_suffix.end());

        return non_palindrome_suffix + s;


    }

    private:
    void buildKMP(string combined,int n, vector<int>&kmp){
        int j=0;
        kmp[0]=0;

        for(int i=1; i<n;i++){
            if(combined[i]==combined[j]){
                j++;
                kmp[i]=j;
            }
            else{
                if(j!=0){
                    j=kmp[j-1];
                    i--;//to stay at same index
                }
                else{
                    kmp[i]=0;
                }
            }
        }
    }

};
11900