214. Shortest Palindrome ## 思路 找從頭開始最長的回文 再把後段reverse補到前面 ex. abac -> 開頭最長回文3 (aba), 前面補c -> cabac abcdc -> 開頭最長回文1 (a), 前面補cdcb -> cdcbabcdc 用KMP建表, 再從後面掃回來 最後j就是最長回文的長度 -- 原本是用Manacher找回文結果TLE = = ## Code ```python class Solution: def shortestPalindrome(self, s: str) -> str: n = len(s) lps = [0] * n j = 0 for i in range(1, n): while j and s[i] != s[j]: j = lps[j-1] if s[i] == s[j]: j += 1 lps[i] = j j = 0 for i in range(n): while j and s[~i] != s[j]: j = lps[j-1] if s[~i] == s[j]: j += 1 return s[j:][::-1] + s ``` -- https://i.imgur.com/kyBhy6o.jpeg -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.171 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726803306.A.DB6.html