title
给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa"
输出："aaacecaaa"
示例 2：
输入：s = "abcd"
输出："dcbabcd"
提示：
0 <= s.length <= 5 * 104s仅由小写英文字母组成
solution
Kmp, 求最长公共前后缀。
class Solution:
def getNext(self, s):
n = len(s)
next = [-1 for _ in range(n+1)]
next[0] = -1
i, j = 0, -1
while i < len(s):
if j == -1 or s[i] == s[j]:
i, j = i + 1, j + 1
next[i] = j
else:
j = next[j]
return next
def shortestPalindrome(self, s: str) -> str:
s1 = s+"*"+s[::-1]
next = self.getNext(s1)
print(next == get_next(s1))
hl = next[-1]
return s[hl:][::-1] + s