214.
最短帕林捉 :
給你一個字串
從頭加字進去 讓他變成帕林捉
回傳最短的那種
==================== ======
絲路：
嗎的原本9.要去睡了
想說看一下今天daily
嗎呀怎麼是hard
還給不給人睡ㄚ
============== == ========
真的思路：
扣掉從頭開始的最大回文
剩下的翻過來加到頭上
kmp掃到一半
逆向回來找
長度剛好跟剩下的字數一樣的話
就找到最大回文
剩下的就內褲套頭
class Solution {
public:
string shortestPalindrome(string s) {
int len = s.length();
int half = len / 2 + 1;
//KMP half from s[0] to s[half]
vector<int> dp;
dp.push_back(0);
int idx = 0;
for(int i = 1; i < half; i++){
while(idx != 0 and s[i] != s[idx]){
idx = dp[idx-1];
}
if(s[i] == s[idx]){
idx++;
}
dp.push_back(idx);
}
idx = 0;
string res;
for(int i = len - 1; i >= 0; i