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