<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:
    def shortestPalindrome(self, s: str) -> str:
        def build(s):
            l = 0
            table = [0 for _ in range(len(s))]

            for r in range(1, len(s)):
                if s[l] == s[r]:
                    l += 1
                    table[r] = table[r - 1] + 1
                else:
                    l = table[r - 1]
                    while l > 0:
                        if s[l] == s[r]:
                            table[r] = l + 1
                            l += 1
                            break
                        else:
                            l = table[l - 1]
                    else:
                        if s[l] == s[r]:
                            table[r] = 1
                            l += 1
            return table
        
        if s == '': return s
        table = build(s + '*' + s[::-1])
        return s[table[-1]:][::-1] + s
        

20600