题目
解法1:
第一种解法是直接找到从这个字符串开始往后的最长回文子字符串，然后剩下的子字符串直接reverse之后加到前面就可以了
class Solution:def shortestPalindrome(self, s: str) -> str:n = len(s)end = 0for i in range(n+1):if s[:i] == s[:i][::-1]:end = iif end == n:return sans = sfor i in range(end,n):ans = s[i] + ansreturn ans
但这可能不是面试官最想看到的答案，这种解法是O(n*n)的。标准答案有可能是解法2，
解法2：kmp算法
详细的如何利用kmp算法的解释看这里。就确实比较难以理解，本身kmp算法就很难理解，如何应用在这也很难理解。kmp算法的详细解释看这里
class Solution:def shortestPalindrome(self, s: str) -> str:def create_LPS(w):LPS = [0] * len(w)tp = 0bp = 1 while bp < len(w):if w[tp] == w[bp]:LPS[bp] = tp + 1tp += 1 bp += 1 else:if tp == 0:LPS[bp] = 0bp += 1 else:tp = LPS[tp-1]return LPSrev_s = s[::-1]palin_s = s + '#' + rev_sLPS = create_LPS(palin_s)return rev_s[:len(rev_s)-LPS[-1]] + s