给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa" 输出："aaacecaaa" 示例 2：
输入：s = "abcd" 输出："dcbabcd"
方法一：
很容易想到的是，将字符串 s 翻转过来，加到 s 的开头，但这并不是最短的，如下图：
这是因为，a 本身就自成回文串，它不需要有镜像。
再比如：s：ananab，rev_s：banana：
anana是回文的，它翻转还是anana，这是回文的特点，所以 rev_s：banana要砍掉相同的部分（anana），变成 b，再加上去。
class Solution:
def shortestPalindrome(self, s: str) -> str:
res_s = s[::-1]
for i in range(len(s), 0, -1):
if s[0:i]==res_s[len(s)-i:]:
return res_s[:len(s)-i]+s
return res_s+s
if __name__ == '__main__':
s = "ababb"
res_s = Solution().shortestPalindrome(s)
print(res_s)
方法二： KMP算法
class Solution:
def shortestPalindrome(self, s: str) -> str:
def prefix_function(s):
nxt = []
nxt.append(0)
now = 0
x = 1
while x < len(s):
if s[now] == s[x]:
now = now + 1
x = x + 1
nxt.append(now)
elif now:
now = nxt[now - 1]
else:
nxt.append(0)
x = x + 1
return nxt
res_s = s + "#" + s[::-1]
pi = prefix_function(res_s)
if pi[-1] == len(s):
return s
else:
return s[pi[-1]:][::-1] + s
if __name__ == '__main__':
s = "ababb"
res_s = Solution().shortestPalindrome(s)
print(res_s)